Reduced polynomial lifts of APN permutations over Galois rings and effective non-APN bounds
2026-08-31 • Information Theory
Information Theory
AI summaryⓘ
The authors clarify a previous conjecture about special functions called APN permutations over certain rings by showing that it only holds when using a specific normalized form of these functions. They prove that lifting such a function to a larger ring is possible if and only if its derivative never vanishes, connecting the problem to a condition about critical points over finite fields. They also use geometric tools related to surfaces to establish explicit limits for when polynomials of certain degrees can be APN, providing concrete thresholds instead of just qualitative results. Lastly, they show that all cubic permutation polynomials meet their corrected criteria by having a rational critical point.
APN permutationsGalois ringsfinite fieldspermutation polynomialsreduced representativecritical pointsJanwa-Wilson-Rodier surfacesdifferential uniformityGold and Kasami-Welch exponentsCafure-Matera estimate
Authors
Daniele Bartoli, Pantelimon Stanica
Abstract
We clarify the APN lifting conjecture over Galois rings of Rønjom and Sandrib (CCDS, 2026). A function on $\F_q$ has many polynomial representatives, whose formal derivatives may differ, so the conjecture must use the unique reduced representative of degree less than $q$; without this normalization, it is false. The standard permutation-polynomial criterion over Galois rings then gives an exact reduction: the reduced representative $f$ of an APN permutation lifts to a permutation of $\GR(2^k,m)$, $k>1$, if and only if $f'(x)\ne0$ for every $x\in\F_{2^m}$. Thus the corrected lifting conjecture is equivalent to a finite-field critical-point conjecture. We next use Janwa--Wilson--Rodier surfaces, which encode the APN condition by rational points off the diagonal arrangement, to prove an effective nonexistence result. For every odd degree $d\ge5$ outside the Gold exponents $2^r+1$ and Kasami--Welch exponents $2^{2r}-2^r+1$, results of Hernando--McGuire and Aubry--McGuire--Rodier provide an absolutely irreducible factor in the hyperplane section at infinity. This yields an absolutely irreducible component of the surface, defined over the ground field and not contained in the diagonal arrangement. The explicit Cafure--Matera estimate then gives a computable number $\APNmzero{d}$ such that no polynomial of degree $d$ over $\F_{2^m}$ is APN when $m\ge\APNmzero{d}$. The qualitative eventual non-APN result is due to Aubry--McGuire--Rodier; our contribution is the explicit threshold. A direct identity for difference tables also gives an even-degree consequence: if $g$ has such an odd degree, then $ax+g(x^2)+c$, with $a\ne0$, has the same differential uniformity as $g$ and is therefore not APN in the same explicit range. Finally, we prove directly that every cubic permutation polynomial has a rational critical point and hence satisfies the corrected lifting conjecture.