CS Paper Radar

Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension

Hiroki Fukui

cs.CR math.NTcs.IT ·submitted 2026-10-15 03:26 UTC · v1
theorycode/data

Abstract

The formal derivative of the reduced polynomial representative of a map on a binary finite field depends on the coordinates, although its differential uniformity does not. This matters for lifting permutations to Galois rings: a polynomial over a Galois ring of characteristic a power of two greater than two permutes the ring exactly when its reduction permutes the residue field and the derivative of the reduction has no zero there. We prove that for every odd $n\ge5$, every quadratic almost perfect nonlinear permutation $Q$ of $\mathbb{F}_{2^n}$ admits invertible binary-linear maps $L$ and $A$ such that the derivative of the reduced representative of $L\circ Q\circ A$ has no zero and each of its nonempty fibres has exactly two elements. The range is exact: this fails for $n=3$, as computed earlier, and for even $n$ there are no such permutations. For $n\ge9$, a linearization and a projectively injective cofactor map reduce the problem to counting binary matrices: more than 5% of the invertible inputs $A$ succeed, more than half for $n\ge15$, without any classification. For $n=5,7$ we use two independent classifications and finite certificates. Consequently every such permutation is linearly equivalent to a counterexample to the reduced critical-point conjecture of Bartoli and Stănică that lifts to permutation polynomials of optimal differential uniformity over every Galois ring with this residue field. For odd $n\ge9$ the existence proof is checked in the Lean 4 proof assistant.

Comment
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)

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT math.NT ·2026-08-31 ·Daniele Bartoli, Pantelimon Stanica
similarity 0.76
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\ge5$ 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.

0.45

Coefficient choice in Galois-ring lifts of APN permutations: sharp unit-direction spectra and one-term optimal lifts

cs.CR math.NTcs.IT ·2026-10-15 ·Hiroki Fukui
code/data similarity 0.73
Abstract · 25 pages. Version 2 is a substantially revised and extended paper with a new title. Lean 4 formalization, blueprint and finite computations:…

Permutation polynomials over the Galois ring $\mathrm{GR}(2^k,m)$ are nonlinear components for symmetric primitives that add keys in the ring, as in secure computation modulo $2^k$. Rønjom and Sandrib showed that their differential uniformity is at least $2q^{k-1}$, where $q=2^m$. For the class studied here it is attained on top-layer differences, while almost all differences are units. We ask how small the difference table can be on unit differences when the residue permutation is fixed and only higher coefficient digits of its lift are chosen. Let $m\ge5$ be odd, $k\ge3$, and let $p$ be a reduced quadratic almost perfect nonlinear (APN) permutation of $\mathbb{F}_q$ whose derivative is nowhere zero and two-to-one. Over all lifts of $p$, the least possible maximum on unit differences is $q$ or $2q$, decided by two invariants of $p$ and the level $k$. We describe every lift attaining it and show that the coefficients modulo $8$ decide optimality at every level. For every odd $m\ge5$, residue permutations with at most $16$ monomials attain $q$ after one $2$-adic digit of one coefficient of the natural lift is changed. For an explicit infinite family, one added monomial lowers the maximum on unit differences from $4q$, or from at least $q^2$, to $2q$ at every level without raising the degree. Under a uniform starting state and independent uniform round keys, valuation preservation yields layerwise bounds for characteristics and two-round differentials that distinguish lifts with the same global uniformity. Core results are formalized in Lean 4.

0.33

Quadratic APN Functions of $\mathbb{F}_2^{10}$ with a Self-Equivalence of Prime Order

cs.IT cs.CRmath.CO ·2026-11-13 ·Emanuele Bellini
similarity 0.69
Abstract

Almost perfect nonlinear (APN) functions of $\mathbb{F}_2^n$ have the lowest possible differential uniformity. The only known APN permutation in even dimension, in dimension six, is equivalent to a quadratic APN function with a nontrivial linear self-equivalence; no APN permutation is known for even $n \geq 8$. In a published collection of about 3.8 million quadratic APN classes of dimension eight, at most 0.34% have a nontrivial linear self-equivalence. In dimension ten, the 25 literature classes considered here all have one. We study all quadratic APN functions of $\mathbb{F}_2^{10}$ with such a self-equivalence, which usually confines them to a much smaller linear space. Up to conjugacy and power similarity, self-equivalences of prime order have 299 types. We settle 298 of them. Elementary lemmas exclude 280 types, and exhaustive searches confirm this for 242 of them. The other 18 types are settled by exhaustive searches with exact equivalence certificates. Up to extended affine equivalence, the 298 types contain 29 classes of quadratic APN functions, four of them new. This also classifies the quadratic APN functions with coefficients in a subfield. Exactly 24 classes contain one with coefficients in $\mathbb{F}_4$, and all 3 that contain one with coefficients in $\mathbb{F}_{32}$ are among them. The open type consists of the quadratic canonical triplicate functions. They correspond to maximum additive Hermitian rank-distance codes. Three different searches find only the invariants of 16 classes, all among the 29. We conjecture there are no others. No quadratic APN function in the 298 settled types is Carlet-Charpin-Zinoviev equivalent to a permutation.

0.24

Constructions of complete permutations over $\mathbb{F}_q^n$

cs.CR cs.IT ·2026-09-03 ·Sartaj Ul Hasan, Ramandeep Kaur, Hridesh Kumar, Daniel Panario, Qiang Wang
similarity 0.66
Abstract

Complete permutation polynomials play an important role in cryptography, particularly in the design of cryptographic primitives such as the Lai--Massey scheme and S-boxes. We generalize a result of Sun, Li, Guo, and Qu (2021) by characterizing the complete permutation behavior of the mapping $Ψ(X)=M(X+ψ(AX))$ over $\mathbb{F}_q^n$, where $\mathbb{F}_q$ is a finite field of $q$ elements with $q$ being a prime power, $M\in GL(n, \mathbb{F}_q)$, $GL(n, \mathbb{F}_q)$ is the general linear group of order $n$ over $\mathbb{F}_q$, $A_{m \times n}$ is a full-rank matrix over $\mathbb{F}_q$, and $ψ=(ψ_1,ψ_2,\ldots,ψ_n)$ with each component function $ψ_i:\mathbb{F}_q^m\to\mathbb{F}_q$. Furthermore, we establish criteria for the permutation and complete permutation properties of the mapping $F(X)=T(X+B^tf(AX))$ over $\mathbb{F}_{q}^n$, $f: \mathbb{F}_{q}^{m} \rightarrow \mathbb{F}_{q}^{n-m}$, $T \in GL(n, \mathbb{F}_q)$, $A_{m \times n}$ and $B_{(n-m)\times n}$ are full-rank matrices over $\mathbb{F}_q$, $B^t$ represents the transpose of the matrix $B$, and $0<m<n$ are integers. These results also generalize an earlier result of Gravel and Panario (2023), who showed that any arbitrary function $f$ from $\mathbb{F}_q^m$ to $\mathbb{F}_q^{\,n-m}$ can be extended to a bijection over $\mathbb{F}_{q}^n$ through the mapping $F(X)=T(X+B^tf(AX))$, under the condition $AB^t=0$. Here we do not impose the restriction that $AB^t=0$.

0.38

Three Infinite Classes of APN Permutations on $Z_n$

cs.IT math.CO ·2026-09-05 ·Deng Tang
similarity 0.64
Abstract

For any permutation of a nontrivial finite abelian group, the differential uniformity is at least two; permutations attaining this bound are called almost perfect nonlinear (APN). We construct three infinite classes of APN permutations on the cyclic group $\mathbb{Z}_n$ using Singer cycles, binomials inducing projective permutations, and completed reciprocals combined with parity and quadratic characters. The respective domain orders are $q+1$ for prime powers $q>2$, $(3^d-1)/2$ for integers $d\ge2$, and $2p$ for primes $p>5$ with $p\equiv5\pmod6$. Each class contains an infinite subclass of composite orders outside the standard forms $r-1$, $r-2$, $r-3$, and $r-4$, where $r$ is a prime power. These forms arise in the Welch--Costas, Panario--Sakzad--Stevens--Wang, and Golomb constructions. To the best of our knowledge, these are the first infinite APN constructions on $\mathbb{Z}_n$ reported since 2011 that yield infinitely many composite orders outside these standard forms.

0.37

A generalization of the map $χ$

cs.IT ·2026-09-17 ·Xiutao Feng, Qiang Wang, Jingyi Yu, Anpeng Zhang
similarity 0.62
Abstract · added a few remarks

The mapping $ χ_n:\mathbb{F}_2^n \to \mathbb{F}_2^n$ defined by $y=χ_n(x)$ with $y_i = x_i + x_{i+1}x_{i+2} + x_{i+2}$, where the indices are computed modulo $n$, has been widely studied for its application in lightweight cryptography. In this paper, we generalize this mapping and completely characterize all these shift-invariant permutations of the form $y_i=x_{i+u}+x_{i+v}(x_{i+w}+a_i)$, where $0\le u, v, w<n$ and $a_i\in \mathbb{F}_2$, $1\le i\le n$. We also determine their compositional inverses explicitly.

0.37

Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions

cs.CR cs.IT ·2026-11-06 ·Emanuele Bellini
similarity 0.62
Abstract

Whether almost perfect nonlinear (APN) permutations exist in even dimension $n\ge 8$ is a long-standing open question, the big APN problem. The only example known in even dimension, on six bits, was found from a quadratic APN function that is not itself a permutation, by Carlet--Charpin--Zinoviev (CCZ) equivalence. It is therefore natural to test APN functions for CCZ-equivalence to a permutation. This amounts to finding two complementary $n$-dimensional subspaces among the zeros of the Walsh transform, which lie in $\mathbb{F}_2^{2n}$. A known necessary condition only uses their projections to $\mathbb{F}_2^n$ and cannot decide every case. We give an exact test for functions whose Walsh supports are affine, including all quadratic functions. It reconstructs the subspaces from their projections, through searches for subspaces of $\mathbb{F}_2^n$ and for constrained bilinear maps. On the benchmarked functions in dimension twelve, it lists them $39$ to $55$ times faster than the generic search of the commonly used sboxU library. We then study the functions $x^3+a^{-1}\mathrm{Tr}(a^3x^9)$, which Göloğlu and Pavlů proved not to be CCZ-equivalent to permutations when $4$ divides $n$. With their result, our computations show that this holds for every even $n\le 24$. In dimension $18$ the necessary condition is satisfied, and the new test decides the case. We conjecture this for every even dimension. We also compile $25$ classes of quadratic APN functions in dimension ten from published instances, with equivalence certificates. No function in these classes or in their switching closure is CCZ-equivalent to a permutation. All code and data are public.

0.61

Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure

cs.IT ·2026-09-25 ·Cheng Lyu, Dabin Zheng, Mu Yuan, Lei Hu
theory similarity 0.62
Abstract

Shift-invariant permutations of $\mathbb F_2^n$ are particularly attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of $\mathbb F_2^n$ constructed from a recursively defined sequence of mappings $\{γ_j\}_{j\ge 0}$ associated with landscapes. First, we prove that, under an explicit dimension condition relating $n$ to the support of the landscape, the sequence $\{γ_j\}_{j\ge 0}$ has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on $\mathbb F_2^n$ with a nonzero special index. Then, we determine the eventual zero or periodic behavior of $\{γ_j\}_{j\ge0}$, including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring $\mathbb F_2[z]/\langle p(z)\rangle$, where $p(z)$ is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.

0.07