Paper 2010/417
Distinguishing Properties of Higher Order Derivatives of Boolean Functions
Ming Duan and Xuejia Lai and Mohan Yang and 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)
- 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
-
CC BY