zbMATH — the first resource for mathematics

An APN permutation in dimension six. (English) Zbl 1206.94026
McGuire, Gary (ed.) et al., Finite fields. Theory and applications. Proceedings of the 9th international conference on finite fields and applications, Dublin, Ireland, July 13–17, 2009. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4786-2/pbk). Contemporary Mathematics 518, 33-42 (2010).
Summary: A map \(f:\text{GF}(2^m)\to \text{GF}(2^m)\) is almost perfect nonlinear, abbreviated APN, if \(x\mapsto f(x+a)-f(x)\) is 2-to-1 for all nonzero a in \(\text{GF}(2^m)\). If \(f(0)=0\), then this condition is equivalent to the condition that the binary code \({\mathcal C}_f\) of length \(2^m-1\) with parity-check matrix
\[ H_f:=\begin{bmatrix} \cdots &\omega^j &\cdots\\ \cdots &f(\omega^j) &\cdots \end{bmatrix} \]
is double-error-correcting, where \(\omega\) is primitive in \(\text{GF}(2^m)\).
A commonly held belief is that, if the dimension \(m\) is even, then an APN map on \(\text{GF}(2^m)\) cannot be a permutation. We give a counterexample in dimension \(m=6\).
For the entire collection see [Zbl 1193.11003].

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94B05 Linear codes, general