Paper 2010/417

Distinguishing Properties of Higher Order Derivatives of Boolean Functions

Ming Duan, Xuejia Lai, Mohan Yang, Xiaorui Sun, and Bo Zhu


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$.

Available format(s)
Publication info
Published elsewhere. submitted to IEEE Transactions on Information Theory
Algebraic DegreeBoolean FunctionHigher Order DerivativeHigher Order DifferentialLinear Structure.
Contact author(s)
mduan @ sjtu edu cn
lai-xj @ cs sjtu edu cn
mh yang sjtu @ gmail com
sunsirius @ sjtu edu cn
zhubo03 @ gmail com
2010-07-27: received
Short URL
Creative Commons Attribution


      author = {Ming Duan and Xuejia Lai and Mohan Yang and Xiaorui Sun and Bo Zhu},
      title = {Distinguishing Properties of Higher Order Derivatives of Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2010/417},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.