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

Available format(s)
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
Short URL
https://ia.cr/2010/417

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.