International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Distinguishing Properties of Higher Order Derivatives of Boolean Functions

Authors:
Ming Duan
Xuejia Lai
Mohan Yang
Xiaorui Sun
Bo Zhu
Download:
URL: http://eprint.iacr.org/2010/417
Search ePrint
Search Google
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$.
BibTeX
@misc{eprint-2010-23318,
  title={Distinguishing Properties of Higher Order Derivatives of Boolean Functions},
  booktitle={IACR Eprint archive},
  keywords={foundations / Algebraic Degree, Boolean Function, Higher Order Derivative, Higher Order Differential, Linear Structure.},
  url={http://eprint.iacr.org/2010/417},
  note={submitted to IEEE Transactions on Information Theory mduan@sjtu.edu.cn; lai-xj@cs.sjtu.edu.cn; mh.yang.sjtu@gmail.com; sunsirius@sjtu.edu.cn; zhubo03@gmail.com 14817 received 26 Jul 2010},
  author={Ming Duan and Xuejia Lai and Mohan Yang and Xiaorui Sun and Bo Zhu},
  year=2010
}