Connections between nonlinearity and restrictions, terms and hypergraphs of Boolean functions

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