Authors:
Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science,
University of Kentucky, Lexington, KY, 40506-0046, klapper at cs.uky.edu.
www.cs.uky.edu/~klapper/andy.html
Luke O'Connor, University of Waterloo
Abstract The algebraic nonlinearity of an $n$-bit boolean function is defined as the degree of the polynomial $f(X) \in Z_2[x_1, x_2, \ldots, 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- \lceil \log n \rceil - 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 structures, 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 asymptotically $(2^n-1) \cdot 2^{2^{n-1}+1}$.
Index Terms -- linearity, partial linearity, linear structures.