CryptoDB
Distinguishing Properties of Higher Order Derivatives of Boolean Functions
Authors: | |
---|---|
Download: | |
Abstract: | Higher order differential cryptanalysis is based on the property of higher order derivatives of Boolean functions that the degree of a Boolean function can be reduced by at least 1 by taking a derivative on the function at any point. We define \emph{fast point} as the point at which the degree can be reduced by at least 2. In this paper, we show that the fast points of a $n$-variable Boolean function form a linear subspace and its dimension plus the algebraic degree of the function is at most $n$. We also show that non-trivial fast point exists in every $n$-variable Boolean function of degree $n-1$, every symmetric Boolean function of degree $d$ where $n \not\equiv d \pmod{2}$ and every quadratic Boolean function of odd number variables. Moreover we show the property of fast points for $n$-variable Boolean functions of degree $n-2$. |
BibTeX
@misc{eprint-2010-23318, title={Distinguishing Properties of Higher Order Derivatives of Boolean Functions}, booktitle={IACR Eprint archive}, keywords={foundations / Algebraic Degree, Boolean Function, Higher Order Derivative, Higher Order Differential, Linear Structure.}, url={http://eprint.iacr.org/2010/417}, note={submitted to IEEE Transactions on Information Theory mduan@sjtu.edu.cn; lai-xj@cs.sjtu.edu.cn; mh.yang.sjtu@gmail.com; sunsirius@sjtu.edu.cn; zhubo03@gmail.com 14817 received 26 Jul 2010}, author={Ming Duan and Xuejia Lai and Mohan Yang and Xiaorui Sun and Bo Zhu}, year=2010 }