Paper 2010/417

Distinguishing Properties of Higher Order Derivatives of Boolean Functions

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

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. submitted to IEEE Transactions on Information Theory
Keywords
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
History
2010-07-27: received
Short URL
https://ia.cr/2010/417
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/417,
      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{https://eprint.iacr.org/2010/417}},
      url = {https://eprint.iacr.org/2010/417}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.