Cryptology ePrint Archive: Report 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$.

Category / Keywords: foundations / Algebraic Degree, Boolean Function, Higher Order Derivative, Higher Order Differential, Linear Structure.

Publication Info: submitted to IEEE Transactions on Information Theory

Date: received 26 Jul 2010

Contact author: mduan at sjtu edu cn; lai-xj@cs sjtu edu cn; mh yang sjtu@gmail com; sunsirius@sjtu edu cn; zhubo03@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20100727:152604 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]