Connections between nonlinearity and restrictions, terms and hypergraphs of Boolean functions
Xian-Mo Zhang, Yuliang Zheng, Hirotaka Imai · 2002
This paper studies nonlinear characteristics of (Boolean) functions which are important in cryptography. The main contributions of this paper are: (1) we show that the restriction of a function on a coset has significant influence on cryptographic properties of the function, (2) we identify relationships between the nonlinearity of a function and the distribution of terms in the polynomial representation of the function, (3) we prove that cycles of odd length in the terms, as well as quadratic terms, in a function play an important role in determining the nonlinearity of the function. Results in this paper will contribute to the study of new cryptanalytic attacks on encryption algorithms, and counter-measures against such attacks.