Algebraic nonlinearity and its applications to cryptography

The algebraic nonlinearity of an n-bit boolean function is defined as the degree of the polynomial f(X) Z₂[x₁, x₂,..., x_n] that represents f. We prove that the average degree of an ANF polynomial for an n-bit function is n+o(1). Further, for a balanced n-bit function, any subfunction obtained by holding less than n-[log n]- 1 bits constant is also expected to be nonaffine. A function is partially linear if f(X) has some indeterminates that only occur in terms bounded by degree 1. Boolean functions which can be mapped to partially linear functions via a linear transformation are said to have a linear structure, and are a potentially weak class of functions for cryptography. We prove that the number of n-bit functions that have a linear structure is asymptotic .The author is presently employed by the Distributed System Technology Center, Brisbane, Australia.Project sponsored in part by NSERC operating Grant OGP0121648, and the National Security Agency under Grant Number MDA904-91-H-0012. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.