Algebraic nonlinearity and its applications to cryptography

✍ Scribed by Luke O'Connor; Andrew Klapper

• Publisher: Springer
• Year: 1994
• Tongue: English
• Weight: 723 KB
• Volume: 7
• Category: Article
• ISSN: 0933-2790
• DOI: 10.1007/bf00203964

✦ Synopsis

The algebraic nonlinearity of an n-bit boolean function is defined as tbe degree of the polynomial f(X) e Z2 [xl, x2,..., x,] 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] -I bits constant is also expected to be nonaltine. 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 (2" -1). 22"-1+t.