### Algebraic nonlinearity and its applications to cryptography

Journal of Cryptology ** 7 ** (1994) 213-228.
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.