Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension

arXiv:2610.21169 · math.NT, cs.CR, cs.IT, math.IT · Submitted 2026-10-15 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension".

Elias: The gist The Main Theorem states that every quadratic almost perfect nonlinear permutation in odd dimension n ≥ 5 has an optimal linear equivalent,

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: We started by looking at the paper "Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension." The core thesis here is that for every quadratic almost perfect nonlinear permutation Q in an odd dimension n greater than or equal to five there exist invertible F2-linear maps L and A <ref:2610.21169#pg1,every quadratic almost perfect nonlinear permutation Q>.

Elias: And these maps L and A allow us to create a new permutation P, which is the result of L composed with Q composed with A. The crucial property they establish is that the derivative of the reduced polynomial representative of this new permutation P has no zero on F2n.

Priya: So, it's about finding a specific transformation—L and A—that makes the resulting permutation P have a nice derivative structure when we look at it over the field F2n. What is that structure supposed to mean for the overall behavior of this permutation?

Nadia: It means that this new representation P is optimal in some sense, which they call linear equivalence. They're not just finding *a* permutation; they are finding a specific form of it that satisfies these derivative conditions.

Elias: And they specify what optimality means here: the EA class of every quadratic APN permutation in odd dimension n greater than or equal to five contains an optimal representative <ref:2610.21169#pg1>. This is stronger than just saying one exists; it says *every* class has one with these properties.

Priya: That sounds like a very strong statement about the space of these permutations. Does this mean we can't have a whole family of permutations that all avoid having this nice derivative property?

Nadia: It suggests that for odd dimensions n greater than or equal to five you can always find at least one representative in any given class that has this optimal structure <ref:2610.21169#pg1>. That’s a huge structural guarantee for these specific nonlinear functions.

Elias: And they specify the condition on the derivative itself. They say that if there is some non-zero element r, then the derivative of red(P) evaluated at x equals the derivative evaluated at y if and only if y is x plus r. This pins down exactly what kind of structure that derivative has.

Priya: So, it's not just that the derivative isn't zero; it has to be very specific, tied to a single non-zero difference between inputs. That specificity is what makes this representation "optimal."

Nadia: Right. It’s about moving from a general quadratic almost perfect nonlinear permutation Q to this highly structured form P through these linear maps L and A. This paper shows that the structure isn't entirely arbitrary for dimensions five and up.

Elias: And they also address the edge cases they found earlier: for n equals three this statement fails, and for even n, there are no such permutations to consider at all because the class is empty <ref:2610.21169#pg1,and for even n, there are no such permutations>.

Conclusion: Priya: So if we wrap up what we've heard about "Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension," what's the big picture? What does it mean for someone just listening who doesn't know all the math jargon?

Nadia: Basically, this paper guarantees that if you take a quadratic almost perfect nonlinear permutation Q in an odd dimension five or higher, there is always a way to transform it using linear maps L and A into a version P where its formal derivative has no zero and has exactly two elements in its non-empty fibers.

Elias: And this means for those dimensions, we don't have to settle for any random representative; we can always find one that is structurally optimal according to these criteria. It’s about finding the best possible way to represent these functions within a certain mathematical framework.

Priya: So from a practical standpoint, it means there's this specific set of functions that are guaranteed to have this desirable derivative property for odd dimensions five and up, which is useful when we are trying to build systems or analyze their behavior over those finite fields.

Nadia: It gives us a definitive statement about the structure of these permutations in those dimensions. For n greater than or equal to nine they've even used formal verification tools to prove this existence claim holds rigorously in Lean four.

Elias: And the implication is that we have a very solid foundation for studying these functions when we consider lifting them to more complex rings, because we know the structure isn't arbitrary for these cases.

Priya: So, it boils down to confirming that for odd n greater than or equal to five there’s a specific type of representative that is optimal in terms of its derivative properties <ref:2610.21169#pg1>. That seems like a solid summary of what this paper achieves.

Hiroki Fukui

Research Institute of Criminal Psychiatry / Sex Offender Medical Center · Kyoto University

math.NT, cs.CR, cs.IT, math.IT

Submitted: 2026-10-15

Updated: 2026-10-15

Comments: 22 pages. Submitted to IEEE Transactions on Information Theory. Code, certificates and Lean 4 formalization: https://github.com/hirokifukui/apnlift (Zenodo: https://doi.org/10.5281/zenodo.23055799)

Code: https://github.com/hirokifukui/apnlift

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

The gist: The gist The Main Theorem states that every quadratic almost perfect nonlinear permutation in odd dimension n ≥ 5 has an optimal linear equivalent, meaning there are invertible F2-linear maps L and

Key concepts

Quadratic Almost Perfect Nonlinear Permutation (Q): This refers to a specific type of nonlinear function defined over the finite field $\mathbb{F}_{2^n}$. It is a polynomial whose structure is constrained by being quadratic and almost perfect, which are properties related to how the function behaves when viewed through its reduced representative in binary fields.
Optimal Linear Equivalent: This means finding invertible linear maps L and A that transform the permutation Q into a new form (L◦Q◦A) where its derivative has no zeros and all non-empty fibers have exactly two elements. This is considered an 'optimal' representative because it possesses these desirable properties related to differential uniformity.
Reduced Critical-Point Conjecture: This conjecture posits that for any APN permutation, its reduced representative must have a zero in the field. The paper shows that for odd $n \text{ ≥ } 5$, every quadratic APN permutation is linearly equivalent to a map that violates this conjecture, meaning it has no zero of its formal derivative.
Galois Ring (GR): A Galois ring is an algebraic structure used to study permutations over fields with specific characteristics. The paper connects the properties of these permutations to their behavior when lifted from the base field $\mathbb{F}_{2^n}$ to a Galois ring of characteristic $a^k$, which is crucial for understanding lifting theorems.

Summary

The gist The Main Theorem states that every quadratic almost perfect nonlinear permutation in odd dimension n ≥ 5 has an optimal linear equivalent, meaning there are invertible F2-linear maps L and A such that the derivative of the reduced representative of L ◦ Q ◦ A has no zero and each of its nonempty fibres has exactly two elements

Main Result

The Main Theorem establishes that for every odd n ≥ 5, every quadratic almost perfect nonlinear permutation Q of F2n admits invertible F2-linear maps L and A such that the derivative of the reduced representative of L ◦ Q ◦ A has no zero and each of its nonempty fibres has exactly two elements The conclusion is stated for linear equivalence, which is finer than EA-equivalence; in particular the EA class of every quadratic APN permutation in odd dimension n ≥ 5 contains an optimal representative

Key Findings and Conditions

The existence proof is checked in the Lean 4 proof assistant for odd n ≥ 9 The range of n is exact; the statement fails for n = 3, as computed earlier, and for even n there are no such permutations For even n there is nothing to prove

Related Conjectures and Bounds

Bartoli and Stanic ˘ a showed that a reduced form of the lifting conjecture of [5] is equivalent to the following statement, known as the Reduced Critical-Point Conjecture [8, Conjecture 2], which posits that for every n, the reduced representative of every APN permutation of F2n has a zero of its formal derivative in F2n Corollary I.1 states that for every odd n ≥ 5, every quadratic APN permutation of F2n is linearly equivalent to a counterexample to the Reduced Critical-Point Conjecture Corollary I.2 further asserts that for every odd n ≥ 5, every quadratic APN permutation of F2n is linearly equivalent to a map whose reduced representative lifts to such a permutation polynomial of every GR(2k, n)

Methodology and Invariants

The method involves fixing Q and an invertible F2-linear input A, setting g = Q ◦ A, and analyzing the invariants s(A) (the dimension of the common kernel of maps L for which red(L ◦ g)′ is constant) and η(A) (which records whether the constant can be nonzero) The existence proof for n ≥ 9 shows that a suitable input always exists For n = 5, 7 the argument relies on two independent classifications and finite certificates

Formal Verification and Extensions

The Main Theorem for odd n ≥ 9 is formalized in the Lean 4 proof assistant with the Mathlib library and checked by the Lean kernel For n = 5, 7, the formal proof rests on cited classifications and finite certificates The work is not formalized for n = 3, where no such permutation exists

Conclusion and Effectiveness

Every quadratic APN permutation in odd dimension n ≥ 5 has an optimal representative L ◦ Q ◦ A with L, A invertible F2-linear For n ≥ 9 at least a fixed fraction of all invertible inputs works (more than half for n ≥ 15), so an optimal representative can be found by independent uniform sampling of inputs The range is exact: the statement fails for n = 3 and is empty for even n

Appendix Details

Appendix B gives closed-form optimal representatives in every Gold class, with no estimate and no search, by an input shear Appendix A provides a sharper degree bound using the Pfaffian route The formal proof uses the count of Theorem VI.1 with the degree En = n(n − 1) and the inequality of Theorem VI.3 for all odd n ≥ 9 The work is not formalized for n = 5, 7 The data and code are available at https://github.com/hirokifukui/apnlift (release v1.0.3) and are archived at Zenodo under https://doi.org/10.5281/zenodo.23053113 The work is not formalized for n = 5, 7 The formal proof follows Sections III–VI The final theorem and its main lemmas depend only on the axioms propext, Classical.choice and Quot.

Improvements for AI systems

Improved AI system can perform formal verification of Main Theorem for odd n ≥ 9 in Lean 4 with a no axioms beyond the three standard ones scope, as described in Section IX. This allows for automated checking of the actual objects (quadratic APN bijections of a finite field of order 2n and their Lagrange representatives) against the formal statement.
Improved AI system can execute randomized construction for n ≥ 9 by drawing inputs independently and uniformly from GLn(F2) and repeatedly checking the criterion, as detailed in Remark VI.7. This allows for an expected number of draws fewer than 2 for n ≥ 15 to find an optimal representative without relying on explicit input searches.
Improved AI system can perform rigorous counting of Fail(Q) inputs using the bound from Theorem VI.1, which states Fail(Q) ≤ ρn(≤ n − 2) − 1 + En qn−1. This allows for a quantitative assessment of the failure rate based on the pigeonhole comparison between invertible matrices and rank-≤ n−2 matrices.
Improved AI system can leverage the projective injectivity of the cofactor map outside an explicit hypersurface (Lemma V.7) to reduce the search space from all invertible inputs to a count of binary matrices by rank, as described in Section III-C–III-D and Theorem VI.1's proof structure.
Improved AI system can identify specific input witnesses for n = 5 and n = 7 by utilizing the classifications of quadratic APN functions and explicit witnesses mentioned in Section VII, ensuring that the formal verification process is grounded in known mathematical results for those dimensions.