Optimal structure found for special binary field permutations in odd dimensions
Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension
Cryptography and SecurityInformation Theory
Summary
This paper studies special kinds of mathematical functions called quadratic almost perfect nonlinear (APN) permutations on binary fields with an odd number of dimensions. The authors show that for these functions, it is always possible to find ways to re-label input and output so their simplified polynomial form behaves nicely when extended over certain rings. This helps understand how these functions work and disproves a previous conjecture for many cases. Their findings are also confirmed using a formal proof assistant.
What this means in practice
- •For cryptography engineers: Determine secure permutation functions on binary fields for designing cryptographic primitives with optimal resistance to differential attacks.
- •For hardware encryption designers: Use linear transformations identified by the paper to implement efficient and secure nonlinear S-boxes in hardware modules.
A theory result. No direct application yet.
Authors
Hiroki Fukui
Abstract
The formal derivative of the reduced polynomial representative of a map on a binary finite field depends on the coordinates, although its differential uniformity does not. This matters for lifting permutations to Galois rings: a polynomial over a Galois ring of characteristic a power of two greater than two permutes the ring exactly when its reduction permutes the residue field and the derivative of the reduction has no zero there. We prove that for every odd $n\ge5$, every quadratic almost perfect nonlinear permutation $Q$ of $\mathbb{F}_{2^n}$ admits invertible binary-linear maps $L$ and $A$ such that the derivative of the reduced representative of $L\circ Q\circ A$ has no zero and each of its nonempty fibres has exactly two elements. The range is exact: this fails for $n=3$, as computed earlier, and for even $n$ there are no such permutations. For $n\ge9$, a linearization and a projectively injective cofactor map reduce the problem to counting binary matrices: more than 5% of the invertible inputs $A$ succeed, more than half for $n\ge15$, without any classification. For $n=5,7$ we use two independent classifications and finite certificates. Consequently every such permutation is linearly equivalent to a counterexample to the reduced critical-point conjecture of Bartoli and Stănică that lifts to permutation polynomials of optimal differential uniformity over every Galois ring with this residue field. For odd $n\ge9$ the existence proof is checked in the Lean 4 proof assistant.