Reduced APN permutations and a disproof of the Galois-ring lifting conjecture

Abstract

We construct infinite families of reduced almost perfect nonlinear (APN) permutations of ${\mathbb{F}}_{2^m}$ that admit coefficientwise permutation lifts to $\mathrm{GR}(2^k,m)$ for every $k>1$. These families disprove Conjecture~2 of Rønjom and Sandrib (Cryptogr. Commun., 2026), even for reduced polynomial representatives. For every odd $m\ge 5$ with $3\nmid m$, we obtain explicit seven-term polynomials over ${\mathbb{F}}_2$ with formal derivative identically one. We derive them from a complete criterion for the reduced representative of $A(x{)}^{2^s+1}$ to have no critical point in ${\mathbb{F}}_{2^m}$, where $A$ is an invertible linearized polynomial and $\gcd (s,m)=1$. We then apply the cube case to construct a second family of degree $2^{m-1}+2$, whose nonconstant derivatives avoid zero by an explicit trace identity. A fixed parameter in ${\mathbb{F}}_{32}$ gives this family in every dimension $m=5r$ with $r$ odd, including a degree-$18$ example over ${\mathbb{F}}_{32}$. Both constructions remain in Gold linear equivalence classes, so liftability of reduced representatives is not invariant under invertible ${\mathbb{F}}_2$-linear input changes. We obtain the lifting conclusions from the standard Galois-ring permutation criterion. We also verify a degree-$24$ example supplied by Zhang and Haobo, prove a trace-adjoint criterion for reduced quadratic functions, and interpret the derivative condition through ramification at rational points.