Explicit reduced APN permutations: ramification and optimal Galois-ring lifts
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: Today's paper: "Explicit reduced APN permutations".
Elias: The gist: The authors provide an explicit family of reduced APN permutations, denoted as Pm,r, and determine their ramification properties over Galois rings and coefficient lifts.
Nadia: First, who's behind it and why it matters.
Paper summary: Nadia: So, wrapping up this discussion on "Explicit reduced APN permutations: ramification and optimal Galois-ring lifts". The authors provided an explicit construction for P m,r based on odd m five and odd r with (r, m) = one <ref:2610.21178#pg1>.
Elias: They gave us the formula using T r, which is a sum of powers of X. It has coefficients in F two and exactly 3r - two terms <ref:2610.21178#pg1,and exactly $3r - 2$ terms>. This construction yields an APN permutation of F q.
Priya: The paper focused heavily on the explicit details: they mapped out the ramification points, noting there are two m-r finite ramification points all wild, with index and different exponent two r-two all over a single finite branch value of one <ref:2610.21178#pg1,there are $2^{m-r}$ finite ramification points all wild, with index>.
Nadia: And they didn't stop there; they connected this construction to the zero/one lift identity in ZX that works over every Galois ring GR(two k, m) for any k two with m-one squarings and r+five additions or subtractions <ref:2610.21178#pg1,and $r+5$ additions or subtractions>.
Elias: It’s also key that they analyzed the differential uniformity for quadratic optimal APN permutations, determining differential rows in specific directions related to the kernel of the linear part of p'.
Priya: The implication is that by providing this explicit family P m,r, we can get precise information about both its ramification and its lifting properties over these rings.
Nadia: For someone just listening, this means we have a concrete tool to study complex polynomial functions in a very specific algebraic setting. It moves the discussion from existence theorems to actual explicit construction and data on how things behave under lifts.
Conclusion: Nadia: So we've seen the technical details on these P m,r polynomials, and now we're wrapping up 'Explicit reduced APN permutations: ramification and optimal Galois-ring lifts'.
Elias: Yeah, it’s about taking these specific APN maps—the quadratic ones—and showing you exactly how they behave when you lift them to these Galois rings.
Priya: So what does that actually mean for the data we're looking at? Is this just another way to count stuff?
Nadia: It means we have a concrete way to predict where the "bad" behavior, like zeros or non-uniformity, is going to show up in these larger algebraic structures.
Elias: Exactly. The authors gave us the explicit ramification data for every single case of m and r. They showed exactly how many points are ramified and what their behavior is like at those points.
Priya: And that maps it to these lifts in GR(two k, m), which sounds a bit abstract. Does this give us any real security insight?
Nadia: It gives us the tools to analyze the structure of the zero/one lift itself. It tells us how many things we need to check—like those r+five additions or subtractions mentioned in the identity they found.
Elias: The authors also proved something important about why these maps aren't just simple monomial functions, which is a structural thing that matters for cryptography and coding theory.
Priya: So, what's the big picture here? What does this specific family of polynomials tell us about the limits of these permutation types?
Nadia: It shows that even with these complex structures, we can get down to the explicit arithmetic rules governing them in a way that works for any size k.
Elias: It confirms that the analysis they did on quadratic optimal maps holds up when you look at coefficient lifts. We still have to figure out how this applies to larger dimensions, though.
Hiroki Fukui
Research Institute of Criminal Psychiatry / Sex Offender Medical Center · Department of Neuropsychiatry, Kyoto University
math.NT, cs.CR, cs.IT, math.IT
Submitted: 2026-10-15
Updated: 2026-10-15
Comments: 15 pages. Submitted to Finite Fields and Their Applications. Code, Lean 4 formalization and blueprint: https://doi.org/10.5281/zenodo.23233173 (version 1.0.1; https://github.com/hirokifukui/residue-apn)
Code: https://github.com/hirokifukui/residue-apn
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
The gist: The gist: The authors provide an explicit family of reduced APN permutations, denoted as Pm,r, and determine their ramification properties over Galois rings and coefficient lifts.
Key concepts
- APN Permutation
- An APN permutation is a special type of permutation polynomial where the difference between any two distinct elements in the image set can only take on a limited number of values. These polynomials are important in cryptography and have been studied for their structure over finite fields.
- Galois Ring $\mathrm{GR}(2^k,m)$
- A Galois ring is an algebraic structure used to study polynomial behavior over rings that are not fields. In this context, $\mathrm{GR}(2^k,m)$ represents a specific ring related to the field size $q=2^m$, allowing the authors to analyze polynomial lifts beyond standard finite fields.
- Ramification
- Ramification describes how a map behaves when viewed as a cover of the projective line. The paper shows that for $P_{m,r}$, there are specific finite points where the map is highly branched (wild ramification), providing detailed geometric information about the polynomial's structure.
- Li-Wang Criterion
- This criterion is used to prove structural properties of certain functions, specifically those involving Gold functions and linearised polynomials. The paper uses a self-contained proof of this criterion to explain why the inner map of $P_{m,r}$ cannot be a simple monomial.
Summary
The gist: The authors provide an explicit family of reduced APN permutations, denoted as Pm,r, and determine their ramification properties over Galois rings and coefficient lifts.
Explicit Construction and Properties
The paper introduces a specific family of polynomials Pm,r defined for odd m ≥ 5 and admissible odd r with gcd(r, m) = 1 by the formula Pm,r = red(T3r)2m−2 It is explicitly stated that this polynomial has coefficients in F2 and exactly 3r − 2 terms. This construction yields an APN permutation of Fq. Furthermore, its formal derivative 1 + X2r−2 + X2m−2 has no zero on Fq and is two-to-one.
Ramification Analysis
The authors determine the ramification of Pm,r as a map of the projective line for all admissible (m, r). Specifically, there are 2m−r finite ramification points, all wild, with index and different exponent 2r−2. All these points lie over the single finite branch value 1. The contribution of this ramification data is described as explicit control of the reduced polynomial as a cover of the projective line and as the source of coefficient lifts
Lifts and Differential Uniformity
The paper investigates the 0/1 lift of Pm,r, noting that it satisfies an identity in Z[X] that evaluates it over every Galois ring GR(2k, m) with m−1 squarings, one general multiplication and r + 5 additions or subtractions. For every quadratic optimal APN permutation p of Fq (in particular Pm,r), the authors determine the differential rows of F exactly in two classes of directions. Specifically, in unit directions off ρ, the number of solutions is at most 2 for every β ∈ R. In the top ideal direction over 2k−1 GR(2k, m) excluding 0, every nonzero entry equals 2q k−1.
Structural Insights
The paper provides a self-contained proof of the Li–Wang criterion for a Gold function plus a linearised polynomial. This proof explains why the inner map of Pm,r is not a monomial. The analysis shows that for every quadratic optimal APN permutation, the ring statements in Section 6 are proved directly and hold for every coefficient lift.
Ramification Details and Non-Monotonicity
The ramification data reveals that the finite ramification points are the 2s roots of g, each having eα = l and dα = l. The point at infinity has e∞ = n and d∞ = 5q/4 − 2. The analysis of Lemma 3.2 shows that an optimal APN permutation in the extended-affine class of G, written N ◦ G ◦ B + L + const, has an inner map B that is not a monomial. This demonstrates that simple linear layers forbid certain structures at the residue level.
Lifting Identity
The natural 0/1 lift is fixed by the identity Pˆ = DˆEˆ − 1 − 2(Yˆ + Zˆ) in Z[X]. Over every Galois ring GR(2k, m), this lift can be evaluated with m−1 squarings, one general multiplication and r + 5 additions or subtractions.
Relation to Prior Work
The work refutes Conjecture 2 of [8] by showing that Theorem 3.1(2) and (3) together with Proposition 6.1 refute it for every odd m ≥ 5 and every k ≥ 2. The explicit family Pm,r provides a new construction, combining the full list of ramification data and the integer product form of the natural lift. The results confirm that neither existence nor a single branch value alone is claimed as new.
Methods and Reproducibility
The authors use script run quick.sh to recompute every finite computation quoted above and calibrate the general identities on finite parameter ranges for admissible (m, r) with m ≤ 101. The formal proofs are formalized in Lean 4 with Mathlib, covering key statements such as Theorem 3.1 and Proposition 5.1. The code and logs are deposited at Zenodo.
Funding and AI Use
This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors. The authors utilized Claude Opus 5.5 (Anthropic; Claude application and agentic tool Claude Code) and GPT5.5 Pro (OpenAI; ChatGPT) in proof exploration, drafting, revising arguments, writing scripts, and writing the Lean formalization. The general results rest on the proofs given in the text. The paper is supported by references [1] through [10].
References
[1] D. Bartoli and P. Stănică, Reduced polynomial lifts of APN permutations over Galois rings and effective non-APN bounds, preprint, 14
[2] D. Bartoli and P. Stănică, Reduced polynomial lifts of APN permutations over Galois rings and effective non-APN bounds, revised preprint, arXiv:2608.30808v2, 4 October 2026
[3] C. Beierle and G. Leander, New instances of quadratic APN functions, IEEE Trans. Inf. Theory 68(1) (2022) 670–678, https://doi.org/10.1109/TIT.2021.3120698; arXiv:2009.07204v4
[4] R. Chen, A general approach to permutation polynomials from quadratic forms, preprint, arXiv:2506.24012v1, 2025, https://doi.org/10.48550/arXiv.2506.24012
[5] H. Fukui, Optimal reduced representatives of quadratic APN permutations in odd dimension, submitted to IEEE Trans. Inf. Theory (IT-26-1499); preprint, Zenodo, https://doi.org/10.5281/zenodo.23074611
[6] C. Kaspers and Y. Zhou, A lower bound on the number of inequivalent APN functions, J. Combin. Theory Ser. A 186 (2022) 105554, https://doi.org/10.1016/j.jcta.2021.105554; cited by the numbering of arXiv:2002.00673v2
[7] Y. Li and M. Wang, On EA-equivalence of certain permutations to power mappings, Des. Codes Cryptogr. 58(3) (2011) 259–269, https://doi.org/10.1007/s10623-010-9406-8
[8] S. Rønjom and A. Sandrib, On the differential uniformity of polynomials over Galois rings, Cryptogr. Commun. 18(6) (2026) 2057–2077, https://doi.org/10.1007/s12095-026-00895-x
[9] D. Stone, apn-critical-point-counterexample, GitHub repository, created 27 September 2026, https://github.com/drewstone/apn-critical-point-counterexample (accessed 7 October 2026)
[10] Y. Yu, N. Kaleyski, L. Budaghyan and Y. Li, Classification of quadratic APN functions with coefficients in F2 for dimensions up to 9, Finite Fields Appl. 68 (2020) 101733, https://doi.org/10.1016/j.ffa.2020.101733
[arXiv:2610.21178v4] arXiv:2610.
Improvements for AI systems
-
This system can perform exact differential row determination for quadratic optimal APN permutations over Galois rings, as described in Theorem 6.2. Specifically, it can compute
exact differential rows in two classes of directions
by utilizing the residue-level statement:If α / ¯ ∈ 2R, then every nonzero entry δF (α, β) equals 2q k−1.
-
The system can verify the non-monomial nature of inner maps for quadratic optimal APN permutations using Lemma 3.2 and Corollary 3.3. This allows it to prove that "an optimal APN permutation in the extended-affine class of G, written N ◦ G ◦ B + L + const with B an F2-linear bijection (an inner translation only adds an affine map, as G is quadratic), has an inner map B that is not a monomial."
-
The system can provide explicit computational verification of ring evaluation identities for coefficient lifts. It can evaluate the
natural 0/1 lift
using the identity:Pˆ = DˆEˆ − 1 − 2(Yˆ + Zˆ) in Z[X],
which allows it to check computations over every Galois ring GR(2k, m) with specified operations. -
The system can determine the ramification data for explicit polynomial families. It can calculate
the number of critical points, local indices, different exponents
for the family Pm,r by applying Theorem 4.1 and verifying thateach has eα = l and dα = l.
Sources
- New Instances of Quadratic APN Functions
- A general approach to permutation polynomials from quadratic forms
- A lower bound on the number of inequivalent APN functions