Proof of a conjecture on the sequence of exceptional numbers, classifying cyclic codes and APN functions (Q661896): Difference between revisions

Let \({ \mathbb F}_{2^{n}}\) be the finite field consisting of \(2^{n}\) elements, and \(w\) a primitive element of \({ \mathbb F}_{2^{n}}\). An integer \(t \geq 3\) is said to be exceptional if the binary cyclic code \(C_{n}^{t} \subset { \mathbb F}_{2^{n}}^{m}\) with two zeros \(w\), \(w^{t}\) has minimum distance \(5\) for infinitely many values of \(n\). It was conjectured by \textit{H. Janwa}, \textit{G. McGuire} and \textit{R. M. Wilson} [J. Algebra 178, No. 2, 665--676 (1995; Zbl 0853.94021)] that the only exceptional values for \(t\) are numbers of the form \(t=2^{i}+1\) (known in coding theory as Gold numbers) and \(t=4^{i}-2^{i}+1\) (known as Kasami-Welch numbers). In a second way this conjecture comes from cryptography as follows. One of the desired properties for an \(S\)-box used in a block cipher is to have the best possible resistance against differential attacks, i.e., any given plaintext difference \(a=y-x\) provides a ciphertext difference \(f(y)-f(x)=b\) with small probability. More formally, a function \(f: { \mathbb F}_{2^{n}} \rightarrow { \mathbb F}_{2^{n}}\) is said to be APN (almost perfect nonlinear) if for all \(a,b \in { \mathbb F}_{2^{n}}\) with \(a \neq 0\) we have \[ \sharp \{x \in { \mathbb F}_{2^{n}} \mid f(x+a)+f(x)=b \} \leq 2. \] Over a field of characteristic \(2\), APN functions provide optimal resistance to differential cryptanalysis. An integer \(t \geq 3\) is said to be exceptional if the monomial function \(f(x)=x^{t}\) from \({ \mathbb F}_{2^{n}}\) to \({ \mathbb F}_{2^{n}}\) is APN for infinitely many values of values of \(n\). The conjecture stated by \textit{J. F. Dillon} [Ohio State Univ. Math. Res. Inst. Publ. 10, 73--85 (2002; Zbl 1032.94013)] says that the only exceptional exponents are the Gold and Kasami-Welch numbers. The authors firstly explain the similarity of the two versions of the conjecture classifying exceptional numbers and then prove its validity. Moreover, the authors give a counterexample (found with MAGMA) to a conjecture posed earlier by Janwa-McGuire-Wilson.