Niho’s last conjecture (Daniel Katz, Cal State Northridge)

A power permutation of a finite field F is a permutation of F whose functional form is x -> x^d for some exponent d.  Power permutations are used in cryptography, and the exponent d must be chosen so that the permutation is highly nonlinear, that is, not easily approximated by linear functions.  The Walsh spectrum of a power permutation is a list of numbers measuring the correlation of our power permutation with the various linear functions. The last conjecture in Niho’s 1972 thesis considers a particular infinite family of highly nonlinear power permutations, and states that each permutation in this family has a Walsh spectrum with at most five distinct values. Niho’s own techniques show that there are at most eight distinct values. Each of the eight candidate values corresponds to a possible number of distinct roots of a seventh degree polynomial on a subset of the finite field F called the unit circle. We use symmetry arguments to show that it is impossible to have four, six, or seven roots on the unit circle: this proves Niho’s last conjecture. This is joint work with Tor Helleseth and Chunlei Li.