CS Paper Radar

Three Infinite Classes of APN Permutations on $Z_n$

Deng Tang

cs.IT math.CO ·submitted 2026-09-05 06:26 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.66
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

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.65
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

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.64
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

Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension

cs.CR math.NTcs.IT ·2026-10-15 ·Hiroki Fukui
theorycode/data similarity 0.64
Abstract · 22 pages. Submitted to IEEE Transactions on Information Theory. Code, certificates and Lean 4 formalization: https://github.com/hirokifukui/…

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.

0.47

New Classes of CCZ-Inequivalent APN Functions with Boomerang Uniformity One in Odd Characteristic: Differential and Boomerang Spectra

cs.IT cs.CR ·2026-11-07 ·Namhun Koo, Soonhak Kwon
similarity 0.58
Abstract

Let $q=p^n>3$ be an odd prime power and let $g:\F_q\to\F_q$ be an even perfect nonlinear (PN) function with $g(0)=0$. We construct almost perfect nonlinear (APN) functions $G_{λ,M}(x)=g(x)+M(x)+λ(x^{q-1}-1)$, where $λ\in\F_q^*$, $-λ\notin g(\F_q)$, and $M$ is an $\F_p$-linearized permutation polynomial. These one-point modifications of $g+M$ have boomerang uniformity one, the smallest possible value for APN functions in odd characteristic. We give complete differential and boomerang spectrum formulas and obtain closed-form evaluations for selected constructions based on Coulter--Matthews monomials and Dembowski--Ostrom polynomials. For $q>7$, comparison of differential spectra establishes CCZ-inequivalence to all APN monomial families listed in the paper and every APN binomial in the original Ness--Helleseth family or its extension by Zeng et al. We characterize CCZ-equivalence within our construction, showing that any two linearly inequivalent even PN functions over the same field yield CCZ-inequivalent APN functions. We obtain three pairwise CCZ-inequivalent APN functions with boomerang uniformity one over $\F_{p^{15\ell}}$ for every $\ell\ge1$, six over $\F_{p^{120r}}$ for every $r\ge1$, and unbounded numbers of such classes in characteristic three. We further prove that CCZ-equivalence and EA-equivalence coincide for functions at Hamming distance at most $m$ from a PN function, provided that $m(m+1)<q-q/p$. We also show that all our APN functions have the maximal possible algebraic degree $n(p-1)$. Finally, we exhibit both CCZ-equivalent and CCZ-inequivalent APN pairs with boomerang uniformity one at Hamming distance one.

0.17

Explicit permutations of $(\mathbb{Z}/4\mathbb{Z})^m$ with uniformly bounded differential uniformity

cs.CR math.NTcs.IT ·2026-11-02 ·Hiroki Fukui
similarity 0.57
Abstract · 8 pages. Source, verification scripts and recorded outputs: https://doi.org/10.5281/zenodo.23876071

Symmetric primitives over Galois rings need nonlinear components whose differentials with respect to ring addition are controlled. Let $R=\mathrm{GR}(4,m)$ and $q=2^m$, so that $(R,+)\cong(\mathbb{Z}/4\mathbb{Z})^m$ has order $N=q^2$. For every $m\ge1$ we construct an explicit permutation $G_c$ of $R$ all of whose differentials with a nonzero input difference have probability at most $36/N$, whereas every permutation polynomial of $R$ has such a differential of probability at least $2/\sqrt{N}$ (Ronjom--Sandrib). The bound holds for the fixed permutation itself, not on average over keys. Equivalently, $Δ(G_c)\le36$ against $Δ\ge2\sqrt{N}$ for permutation polynomials; since every permutation has $Δ\ge2$, the least differential uniformity of a permutation of $(\mathbb{Z}/4\mathbb{Z})^m$ lies between $2$ and $36$ for every $m$. In Teichmuller digits $(a,b)\in\mathbb{F}_q^2$ and for $c\in\mathbb{F}_q$ of absolute trace $1$, $G_c(a,b)=(L,(L^2+L+c)a)$ with $L=(a^2+a+c)b$. The map is $F_c\circ J\circ F_c$, where $F_c(a,b)=(a,(a^2+a+c)b)$ is induced by a polynomial over $R$ and $J$ exchanges the digits: a single digit exchange between two polynomial layers yields a bound independent of $m$. The proof reduces the difference equations, in each of three types of directions, to one-variable polynomials whose degrees do not depend on $m$. For general maps $F\circ J\circ F$ with $F(a,b)=(p(a),h(a)+d(a)b)$, where $p,d,h$ have degrees bounded independently of $m$, $p'\ne0$ and $d$ has no zeros, a Jacobian identity in characteristic $2$ bounds the differentials with nonzero low input and output differences independently of $m$; the remaining directions need a separate argument, which we give for an explicit family ($Δ\le440$, resp. $510$, for odd $m$).

0.31

A density theorem for non-standard irreducible cyclic codes

cs.IT math.CO ·2026-10-31 ·Tao Feng, Henk D. L. Hollmann, Weicong Li, Qing Xiang
theory similarity 0.56
Abstract · 13 pages

We prove a fixed-characteristic density form of the Berger-Charpin conjecture for non-degenerate irreducible cyclic codes: for each prime $p$, the lengths admitting such a non-standard code over some finite field of characteristic $p$ have natural density zero. Thus, for almost every length coprime to $p$, every such code over every finite field of characteristic $p$ has only the permutation automorphisms generated by the cyclic shift and the Frobenius map. The proof uses the Feng--Hollmann--Li--Xiang classification for non-standard irreducible cyclic codes, a normal form for the deriving constructions in that paper, and a theorem by Wiertelak on multiplicative orders, in the form recalled by Moree.

0.21

CCZ-Equivalence and Enumeration of Triprojective APN Functions

cs.CR ·2026-08-12 ·Jingchuan Ma, Yanhua Liu, Qiaoyun Huang
similarity 0.55
Abstract · 17 pages

We classify all admissible parameters of the G"ologlu--K"olsch triprojective construction of almost perfect nonlinear (APN) functions up to Carlet--Charpin--Zinoviev (CCZ) equivalence. The construction has three coefficients in $K=\mathbb{F}_{2^m}$ and a Frobenius exponent $k$ coprime to $m$. For every $m>1$, we give a necessary-and-sufficient criterion that includes changes of both the coefficients and the exponent. Each parameter choice determines one of the two irreducible cubic polynomials over $\mathbb{F}_2$. Two functions are equivalent precisely when their exponents and cubics agree, or when the exponents are negatives modulo $m$ and the cubics are reciprocal. When $7\nmid m$, every admissible member is equivalent to a Li--Kaleyski representative: the larger coefficient space adds no CCZ classes. When $7\mid m$, those representatives are inadmissible; we construct replacements and classify the full family. There are exactly $\varphi(m)$ CCZ classes, extending the previously known count for the older subfamilies to all admissible coefficients and all degrees. We also count the parameter triples and compute canonical representatives and explicit equivalence maps in deterministic polynomial time for every degree, including degrees divisible by seven. The proof combines a reduction to classical semilinear conjugacy with an intrinsic recovery of the scalar field from the polar bilinear map. The reduction from arbitrary EL equivalence is algebraic in every degree, including degrees three and six.

0.10