Source-linked AI summary
Reduced polynomial lifts of APN permutations over Galois rings and effective non-APN bounds
Daniele Bartoli, Pantelimon Stanica
TL;DR
The paper resolves a normalization issue in the APN lifting conjecture and reduces the corrected question to rational critical points of reduced representatives. It then combines Janwa–Wilson–Rodier geometry with explicit point-counting estimates to obtain effective non-APN bounds, while identifying scope limits for the ramification interpretation.
Problem
The lifting conjecture is ambiguous for arbitrary polynomial representatives because equivalent representatives can have different derivatives and coefficientwise lifts.
Method
The paper fixes the reduced representative, applies the Galois-ring permutation criterion, and uses Janwa–Wilson–Rodier surfaces, hyperplane-section irreducibility, and the Cafure–Matera estimate.
Results
The corrected lifting conjecture is equivalent to the existence of a rational critical point, and explicit thresholds exclude APN polynomials in generic odd degrees and the stated even-degree family.
Takeaways & Limitations
The paper supplies a computable replacement for qualitative eventual non-APN results and clarifies the precise finite-field condition governing corrected lifting.
Takeaways & Limitations
The ramification observation does not force all ramification to lie at infinity and is not used in the effective argument.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames APN permutations as rare cryptographic objects and asks whether their permutation property survives lifting to Galois rings. It argues that this question requires reduced polynomial representatives because equivalent representatives can have different derivatives and lift behavior.
- Motivation: APN functions achieve optimal differential resistance in characteristic two and are especially useful when they are also permutations for S-box design.APN functions have differential uniformity 2, while APN permutations combine nonlinearity with invertibility.
- Motivation: APN permutations are remarkably rare and remain sparse and highly structured across known finite-field families.The introduction notes only Dillon’s example in even dimension and several monomial families in odd dimension.
- Lifting setup: Every function on Fq has a unique reduced representative of degree less than q, and this normalization is essential because equivalent polynomials can have different formal derivatives and lifts.The derivative and coefficientwise-lift behavior depends on the chosen polynomial representative.
- Lifting setup: The guiding problem is whether the reduced representative of an APN permutation remains a permutation after lifting from a finite field to a Galois ring.Galois rings provide richer local rings with residue field F2^m, and coefficientwise lifts reduce to the original polynomial modulo the maximal ideal.
- Lifting conjecture: The normalized conjecture asserts that no coefficientwise lift of a reduced APN permutation induces a permutation of GR(2^k,m) for k>1.The paper identifies this as the corrected form of the conjecture proposed by Rønjom and Sandrib.
- Lifting conjecture: Without normalization, the conjecture is false: an alternative representative can induce the same finite-field function while every coefficientwise lift is a permutation.The standard Galois-ring permutation criterion exposes why arbitrary representatives cannot be used.
- Contribution and scope: The paper distinguishes its explicit odd-degree threshold from the earlier qualitative result that generic odd-degree polynomials eventually cease to be APN.Aubry–McGuire–Rodier supplied eventual non-APN behavior, while this work extracts a computable threshold.
2 Our main results
The paper reduces APN lifting over Galois rings to rational critical points of reduced representatives, then proves explicit non-APN bounds in broad odd- and even-degree families and settles the cubic case.
- Lifting and critical points: The Galois-ring permutation criterion reduces the lifting conjecture to whether every reduced APN permutation has a rational critical point.This is equivalent to the finite-field reduced critical-point conjecture.
- Lifting and critical points: For a permutation polynomial, absence of rational critical points is equivalent to being étale at every finite rational point and to every fiber polynomial having a simple rational root.The geometric formulation identifies the finite ramification points over an algebraic closure with zeros of the derivative.
- Explicit non-APN bounds: For odd d≥5 outside Gold and Kasami–Welch degrees, an absolutely irreducible component over F2m yields an explicit threshold MCM(d) above which no degree-d polynomial is APN.The argument combines the geometric component with the Cafure–Matera point estimate; the qualitative eventual result was previously known.
- Explicit non-APN bounds: The odd-degree bound extends to polynomials of the form ax+g(x^2)+c, with a≠0, when deg g is an eligible odd degree.Such polynomials have constant nonzero derivative when they are permutations, and the theorem rules out APN behavior above the corresponding threshold.
- Cubic case: Every cubic permutation polynomial over F2m has a rational critical point, so its reduced representative has no permutation lift to GR(2k,m) for k>1.This cubic result is nonvacuous, unlike the high-degree conclusion obtained by eventual non-APN bounds.
- Scope: The geometric argument is restricted to odd degrees because Gold and Kasami–Welch exponents have additional symmetry and reducibility.Those exceptional families are not covered directly by the generic irreducibility argument.
3 Algebraic geometry background
This section establishes the algebraic-geometric framework for polynomial maps, their induced morphisms, and ramification. It relates finite rational-point étaleness to nonvanishing formal derivatives and records the corresponding function-field and projective-line facts.
- Polynomial maps: Polynomials induce regular maps A1_k → A1_k that extend uniquely to morphisms P1_k → P1_k.The associated function-field extension is K/L, where K = k(x) and L = k(f(x)).
- Étaleness and derivatives: At a k-rational finite point a, the induced morphism is étale exactly when f′(a) ≠ 0.Equivalently, the ramification index at a is one.
- Function fields: The extension k(x)/k(f(x)) is separable if and only if f′ is not identically zero.When f′ vanishes identically, the polynomial factors through a Frobenius power and the extension has a purely inseparable intermediate extension.
- Ramification: Over an algebraic closure, finite ramification points are precisely the zeros of f′, while the unique point above infinity has ramification index equal to deg(f).At finite points, the ramification index equals the multiplicity of the corresponding root of f(x) − b.
4 The reduction: From Galois rings to critical points
The section reduces Galois-ring lifting to the characteristic-four case and then to a derivative condition on the finite-field reduction. The result is an exact criterion: every polynomial lift permutes the Galois ring precisely when the reduced permutation has no rational critical point.
- Necessity: If a polynomial over GR(4,m) permutes the ring, its reduction f satisfies f′(a) ≠ 0 for every a ∈ F2^m.The exact first-order Taylor expansion over the square-zero ideal forces the derivative maps on every coset to be invertible.
- Galois-ring structure: Every element of GR(4,m) has a unique Teichmüller expansion t0 + 2t1 with t0,t1 in the Teichmüller system.The maximal ideal (2) is square-zero and is additively isomorphic to F2^m.
- Reduction to GR(4,m): A permutation lift over GR(2^k,m), k > 2, descends to a permutation over GR(4,m), so it suffices to analyze characteristic four.Polynomial maps respect congruences modulo powers of 2, and quotienting by (4) identifies the quotient with GR(4,m).
- Permutation criterion: A polynomial map on GR(4,m) is bijective exactly when its residue-field map is bijective and each induced map on a maximal-ideal coset is bijective.The coset maps are described by y ↦ F(t + y) − F(t).
5 Rational critical points and ramification
The section gives three equivalent descriptions of the rational critical-point condition for a permutation polynomial: derivative nonvanishing, finite-point étaleness, and simple roots of every fiber. It emphasizes that this is only a rational-point statement.
- Geometric reformulation: For a permutation polynomial, f′(a) ≠ 0 for every a ∈ F2^m exactly when the induced morphism is étale at every finite rational point.This follows from the local equivalence between étaleness and derivative nonvanishing.
- Fiberwise reformulation: The same condition holds exactly when every polynomial f(x) − b has a simple root in F2^m for each b ∈ F2^m.Permutation means each fiber has a unique rational root, whose simplicity is determined by f′.
- Scope: The criterion concerns rational points only and does not exclude zeros of f′ over the algebraic closure.Thus finite non-rational ramification may remain even when all finite rational points are unramified.
6 Effective non-APN bounds via Janwa-Wilson-Rodier surfaces
Janwa–Wilson–Rodier surfaces encode APN behavior through rational points outside a diagonal arrangement. An absolutely irreducible component defined over the ground field forces such a point over sufficiently large fields, and geometric results supply that component for generic odd degrees, producing an explicit non-APN threshold.
- Surface encoding: A function f is APN exactly when every Fq-rational point of its Janwa–Wilson–Rodier surface lies in the diagonal arrangement V.V is the union of the planes x = y, x = z, and y = z.
- Point forcing: An absolutely irreducible component S defined over Fq and not contained in V forces an Fq-rational point of Xf outside V once the Cafure–Matera inequality holds.The point estimate exceeds the rational points on the three diagonal plane sections.
- Geometric component: For odd degrees outside the Gold and Kasami–Welch families, the hyperplane section at infinity supplies an absolutely irreducible factor defined over F2.This yields a surface component defined over Fq that is not contained in the projective diagonal arrangement.
- Relation to prior work: The qualitative eventual non-APN result was already known; the paper's new contribution is an explicit threshold extracted from the geometric component and point estimate.The argument is therefore an effective refinement rather than a new qualitative mechanism.
- Effective bound: The resulting explicit threshold M_CM^(0)(d) gives that no polynomial of degree d is APN over F2^m for m ≥ M_CM^(0)(d).The bound applies for odd d ≥ 5 that are neither Gold nor Kasami–Welch numbers.
A constant-derivative family in even degree.
Polynomials of the form ax+g(x^2)+c provide an even-degree family whose differential uniformity equals that of g. This transfers explicit odd-degree non-APN bounds and separately establishes the cubic critical-point case.
- A polynomial has constant derivative exactly when it has the form f(x)=ax+g(x^2)+c; its derivative is nowhere zero precisely when a≠0.
- For f(x)=ax+g(x^2)+c, the difference-table substitution u=x^2 gives a fiber-count identity relating D_t f to D_{t^2}g.
- Consequently, f and g have the same differential uniformity, so f is APN if and only if g is APN.
- For odd e≥5 outside the Gold and Kasami–Welch families, degree d=2e polynomials of this form are not APN when m≥MCM_0(e).
- Every cubic permutation polynomial over Fq has a critical point in Fq.
7 Examples and exceptional families
The elementary monomial cases align with the corrected critical-point conjecture, while the cubic case is proved directly; other non-monomial and sporadic examples remain individual cases.
- For monomial APN permutations, the reduced representative has a derivative that either vanishes identically or at 0, covering the listed power families.
- Every cubic polynomial has a rational critical point, but non-monomial families and sporadic examples require separate examination of their reduced representatives.
8 Conclusion
The paper fixes the lifting conjecture by using reduced representatives and reduces it to rational critical points. It then gives explicit non-APN thresholds, an even-degree transfer, and a direct cubic result while identifying remaining scope limits.
- The lifting question must use the unique reduced representative, because arbitrary representatives can have different derivatives and yield a false literal statement.
- For reduced representatives, the Galois-ring lifting question is equivalent to asking whether every APN permutation has a rational critical point.
- Every cubic permutation polynomial has a rational critical point, while odd degrees d≥5 outside Gold and Kasami–Welch families are excluded from APN behavior above an explicit threshold.
- The Janwa–Wilson–Rodier surface and Cafure–Matera estimate convert eventual odd-degree nonexistence into an effective bound, without requiring the whole surface to be absolutely irreducible.
- The same threshold excludes degree 2e polynomials of the form ax+g(x^2)+c because their differential uniformity equals that of g.
- The reduced critical-point conjecture remains open for APN permutations outside the elementary monomial and cubic arguments, and the ramification discussion is limited to rational points.