PaperlayerView exact revision on arXiv

Source-linked AI summary

Three Infinite Classes of APN Permutations on $Z_n$

Deng Tang

arXiv:2609.05917v1math.COcs.ITmath.IT

TL;DR

Since 2011, reported APN classes on Z_n had not included infinitely many composite orders outside standard forms. This paper constructs three infinite classes and reports infinitely many such composite orders.

  • Problem

    Reported APN classes on Z_n had not included infinitely many composite orders outside the standard forms r−1, r−2, r−3, and r−4.

    Source: §1 · p. 4

  • Method

    The paper constructs three infinite classes of APN permutations on Z_n, including a completed-reciprocal family parameterized by parity and quadratic character.

    Source: §1 · p. 4

  • Results

    The classes provide APN permutations on infinitely many composite orders outside the standard forms r−1, r−2, r−3, and r−4 for prime-power r.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The permutations are combinatorial candidates for further investigation, not a proposed cryptographic primitive or threshold protocol.

    Source: §1 · p. 3

    Changing k only precomposes with a group automorphism and is not claimed to yield a new equivalence class; the same-spectrum observation is computational, not a general theorem.

    Source: §4.2 · p. 17, §4.3 · p. 18

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces three infinite classes of APN permutations on cyclic groups and reports infinitely many composite orders outside the standard forms of earlier constructions.

APN background

  • Every permutation of a nontrivial finite abelian group has differential uniformity at least two, and attaining that bound defines APN.For a fixed nonzero input difference, injectivity makes every output difference nonzero; the pigeonhole principle then forces a repeated output difference.Source: §1 · p. 2

Motivation and scope

  • Ring arithmetic appears in cryptography, proof systems, and secure computation, making cyclic-group APN permutations candidates for further investigation.The paper establishes combinatorial properties only; it proposes no primitive or protocol and evaluates neither implementation nor circuit costs.Source: §1 · p. 3

Novelty

  • The classes provide APN permutations on infinitely many composite orders outside r−1, r−2, r−3, and r−4 for prime-power r, a reported first since 2011.The order comparison distinguishes these constructions under input/output relabeling and compositional inversion, but does not establish inequivalence under broader notions.Source: §1 · pp. 4–5

First construction

  • Singer-cycle orbits label the projective line cyclically to produce APN permutations on Z_(q+1) for odd prime powers q.For a fixed Singer cycle and base point, q(q^2−1)−2(q+1) admissible projectivities induce distinct permutations.Source: §1 · p. 4

Second construction

  • Projective-space binomials yield APN permutations on Z_((3^d−1)/2) when q=3 and the stated exponent condition holds.More generally, the theorem gives differential uniformity at most q−1 when gcd(r−t, q^d−1)=q−1; invertible ternary linearized polynomials give an explicit infinite subfamily.Source: §1 · p. 4

Third construction

  • The completed-reciprocal construction combines parity and the quadratic character to define a parametrized family on Z_(2p).For p>5 with p≡5 (mod 6), the family is APN exactly when χ(a)=χ(−3)=χ(1−4a)=χ(1−4/a)=−1, independently of translation parameter c.Source: §1 · p. 4

2 Preliminaries

The preliminaries define APN behavior through cyclic differences and provide the number-theoretic and projective tools used in the constructions. They also explain how projective actions and completed reciprocals are represented on cyclic groups.

2.1 Differential uniformity, difference distribution tables, and differential spectra

  • APN means differential uniformity 2, the minimum possible for a permutation; the DDT records difference counts and the differential spectrum records its entry multiplicities.At the S-box level, this minimizes the maximum probability of a differential transition, though full-cipher resistance also depends on cipher structure.Source: §2.1 · p. 6

2.2 Number-theoretic preliminaries

  • The number-theoretic toolkit includes valuations, lifting-the-exponent, Dirichlet’s theorem, and quadratic-character sums; a Weil-bound estimate ensures multipliers exist for the third construction when p ≡ 5 (mod 6).For square-free cubics over Fp, the estimate follows from the Hasse–Weil bound for a genus-one curve.Source: §2.2 · pp. 6–7

2.3 Projective spaces, projectivities, and Singer cycles

  • Projective points are one-dimensional subspaces, and a Singer cycle acts regularly on them; on the projective line, a nonidentity Möbius transformation has at most two fixed points.For d = 2, a Singer group has order q + 1 and is also called a nonsplit torus.Source: §2.3 · pp. 7–8

2.4 Labeling the points of PG(d −1, q) by exponents

  • The labeling i ↦ [α^i] bijects cyclic labels with projective points, transferring projective permutations to cyclic groups; suitable homogeneous polynomials and invertible linear maps induce such projective actions.The binomial u x^r + v x^t has the required scalar compatibility when r ≡ t (mod q − 1).Source: §2.4 · pp. 8–9

2.5 Completed reciprocals

  • The completed reciprocal fixes zero and maps each nonzero x ∈ Fp to x^-1; it is an involution that preserves quadratic character.It is represented by x^(p−2), and differs from projective inversion, which interchanges zero and infinity.Source: §2.5 · p. 9

3 APN Permutations from Singer Cycles

The first construction labels the projective line by a Singer-cycle orbit and transfers projectivities to permutations of Z_(q+1). A noncommutation condition yields APN permutations, including infinitely many orders outside the listed standard forms.

3.1 The construction

  • For odd prime powers q, a Singer-cycle orbit labels the q + 1 projective points by Z_(q+1), and each projectivity M induces a permutation F_M through this bijection.The construction uses the unique involution J in the Singer group and requires M J ≠ J M for the APN result.Source: §3.1 · p. 9, §3 · p. 9

3.2 The APN property

  • The condition M J ≠ J M makes the projectivity arising from each nonzero input and output difference nonidentity, so it fixes at most two projective points and the induced permutation is APN.The compositional inverse is also APN under the same construction.Source: §3.2 · pp. 10–11

3.3 Parameters and orders

  • Distinct projectivities satisfying the noncommutation condition induce distinct APN permutations for fixed Singer-cycle and base-point choices.The paper’s parameter count is given by Proposition 1, though the supplied passage omits the count itself.Source: §3.3 · pp. 11–12
  • Composition satisfies F_M ◦ F_L = F_ML, and the composition is APN exactly when ML does not centralize J.If ML centralizes J, a DDT entry equals n, so that composition is not APN.Source: §3.3 · pp. 12–13
  • Infinitely many primes q in the stated progression give n = q + 1 with none of n + 1, n + 2, n + 3, or n + 4 a prime power, excluding the standard r−1 through r−4 forms.These orders are composite and are not of the form 2p for prime p.Source: §3.3 · pp. 13–14
  • For q = 257, the construction gives an APN permutation on Z258.The example’s Singer-cycle matrix induces a 258-cycle on the projective line.Source: §3.3 · p. 14

4 APN Permutations Induced by Binomials

Binomials inducing permutations of projective points yield cyclic APN permutations when their exponent difference satisfies a gcd condition. Over F3^d, an explicit family provides APN permutations of order (3^d−1)/2, including infinitely many orders outside the earlier prime-power forms.

4.1 A general condition on the exponents

  • For q = 3, the exponent gcd condition bounds differential uniformity by two, so every qualifying projective binomial permutation is APN.The general bound is δ(FH) ≤ q−1, and the projective permutation hypothesis does not require H to be linearized.Source: §4.1 · pp. 15–16
  • The binomial criterion counts at most one projective solution per scalar, yielding at most q−1 solutions to each differential equation.When q = 3, this gives the bound of two, which equals the general lower bound for permutations.Source: §4.1 · p. 16

4.2 An explicit family over F3d

  • For d ≥ 2, gcd(s,d)=1, nonsquare −c, and unit k, the family Hk,c,s(x)=x^(k3^s)+cx^k induces an APN permutation on order n=(3^d−1)/2.Taking c=−α gives an explicit member for every such d, s, and k.Source: §4.2 · p. 16
  • Changing k only precomposes the permutation with a group automorphism, so it does not produce a new equivalence class.This precomposition preserves the differential spectrum up to a permutation of input differences.Source: §4.2 · p. 17

4.3 Examples and orders

  • For d=3, s=1, c=−α, and k=5, the construction gives an APN permutation of order 13 with differential spectrum (36, 84, 36).Its exponent difference is 10, with gcd(10,26)=2.Source: §4.3 · p. 17
  • Among the listed parameter ranges, all k=1 permutations at a fixed order have the same differential spectrum; this is computational, not a general theorem.Table 4 reports differential spectra for ternary-binomial permutations with k=1.Source: §4.3 · p. 18, Table 4 · p. 18
  • For d ≥ 14 with d ≡ 14 (mod 4620), the resulting orders avoid the prime-power conditions for n−1 through n+4, yielding infinitely many orders outside the earlier forms.The stated order is n=(3^d−1)/2.Source: §4.3 · p. 18

5 APN Permutations from Completed Reciprocals

This section develops a parity-aware completed-reciprocal map on \(\mathbb{Z}_{2p}\), characterizing when it is an APN permutation and establishing parameter counts and structural properties. It also gives an infinite prime progression producing such permutations outside standard nearby-prime-power forms, distinguishes the construction from polynomial functions, and provides an explicit order-22054 example.

5.1 The construction

  • For χ(a)=−1, the completed-reciprocal map is a permutation of Z_2p; its output parity uses the Legendre symbol, and paired quadratic roots have different output parities.The construction requires neither a discrete logarithm nor a labeling of projective points.Source: §5 · p. 19, §5.1 · p. 19

5.2 The APN property

  • B_a,c,p is APN exactly when χ(a)=χ(−3)=χ(1−4a)=χ(1−4/a)=−1, independently of translation parameter c.The proof establishes both sufficiency and necessity of the character conditions.Source: §5.2 · pp. 23–25

5.3 Existence and parameter count

  • For p>5 with p≡5 (mod 6), each a∈A_p and c∈F_p yields an APN permutation, with exactly p(p+1+T_p)/8 distinct family members and at least p(p+1−2√p)/8.Here A_p is the parameter set defined by χ(a)=χ(1−4a)=χ(1−4/a)=−1.Source: §5.3 · p. 25
  • For primes p≥11 with p≡23 or 47 (mod 60), B_−1,c,p is an APN permutation for every c∈F_p.These congruences ensure the character conditions of the APN criterion hold for a=−1.Source: §5.3 · p. 26
  • When χ(a)=−1, B_a,c,p is neither a polynomial function over Z_2p nor a function P(z)Q(z)^−1 with Q(z) always a unit.The latter exclusion applies to P,Q∈Z_2p[X].Source: §5.3 · p. 26
  • For p ≡ 2 (mod 3), x^(p−2) is APN, while the parity- and quadratic-character-based completion is non-polynomial; a two-lift contradiction also rules out the stated function form.The contradiction uses two lifts of an input residue with different output residues modulo p.Source: §5.3 · p. 27

5.4 Orders different from those of the standard classes

  • For infinitely many primes p ≡ 11027 (mod 44100), B_-1,c,p is APN for every c ∈ F_p, and order n = 2p lies outside the forms r + 1 and r − j for 1 ≤ j ≤ 4.Theorem 8 states that none of n − 1 through n + 4 is a prime power.Source: §5.4 · p. 27
  • The modulus 44100 yields p ≡ 47 (mod 60), 2 (mod 9), 2 (mod 25), and 2 (mod 49), establishing APN and excluding prime-power status for n − 1 through n + 4.The proof uses Dirichlet’s theorem for infinitely many primes in the progression and divisibility arguments for the five neighboring integers.Source: §5.4 · p. 27
  • At p = 11027, Construction 3 gives an explicit APN permutation B_-1,0,11027 on Z_22054; Table 7 lists factorizations of the neighboring integers.The example sets n = 22054.Source: §5.4 · p. 28, Table 7 · p. 28

6 Comparison with Known Classes

The comparison distinguishes the three constructions by their mechanisms and proof bounds, and shows that each yields infinitely many composite orders outside the standard order forms.

6 Comparison with Known Classes

  • The three constructions use fixed points of projectivities, binomials with at most one projective solution per scalar, and completed reciprocals distinguished by quadratic characters.Their parameters respectively satisfy noncommutation conditions, binomial permutation and gcd conditions, and the conditions in (17).Source: §6 · p. 28
  • Their proofs use different bounds—at most two fixed points, at most one projective solution per scalar, and at most two reciprocal-equation roots after character testing—so none is a specialization of another proof.This does not establish that the resulting families are disjoint at a common order.Source: §6 · p. 28
  • Each construction has an infinite subfamily of composite orders outside r−1, r−2, r−3, and r−4, the forms associated with the Welch–Costas, Panario–Sakzad–Stevens–Wang, and standard Golomb classes.The Sections 4 and 5 constructions also have infinitely many orders outside r+1; the Theorem 2 subfamily contains no order of the form 2p.Source: §6 · pp. 28–29

7 Conclusion

The paper constructs three infinite classes of APN permutations on cyclic groups using Singer cycles, binomials, and completed reciprocals. It reports infinite composite-order subfamilies beyond the standard forms, the first such classes reported since 2011 to the authors’ knowledge.

7 Conclusion

  • The paper presents three infinite classes of APN permutations on Zn, with composite-order subfamilies outside r−1, r−2, r−3, and r−4.The authors identify these as the first such infinite classes reported since the Panario–Sakzad–Stevens–Wang class appeared in 2011, to their knowledge.Source: §7 · p. 29
  • The Singer-cycle construction gives APN permutations on Zq+1 for every odd prime power q.For a fixed Singer-group generator and base point, q(q^2−1)−2(q+1) admissible projectivities induce distinct permutations.Source: §7 · p. 29
  • For q=3, invertible ternary linearized polynomials yield an explicit infinite APN subfamily on Z(3^d−1)/2.The binomial construction has differential uniformity at most q−1 under gcd(r−t, q^d−1)=q−1.Source: §7 · p. 29
  • The completed-reciprocal family on Z2p is APN exactly when χ(a), χ(−3), χ(1−4a), and χ(1−4/a) all equal −1.For every prime p>5 with p≡5 (mod 6), an associated character sum gives the exact number of APN permutations in the family.Source: §7 · p. 29
  • Small-order computations confirmed the theoretical results and determined differential spectra in the stated parameter ranges.The three proofs rely respectively on fixed points of projectivities, numbers of projective solutions, and quadratic characters.Source: §7 · p. 29

8 Appendix

The appendix gives moderate-order representatives of the three constructions, with truth tables and differential spectra. Each example reports a permutation with differential uniformity δ=2.

8.1 Truth Tables of Representative APN Permutations

  • The appendix presents a representative truth table and differential spectrum for each construction, with examples generated and verified in Magma V2.28-3.The spectrum is written (A0, A1, …, An), with Aj defined in equation (1).Source: §8.1 · p. 29

8.1.1 Example induced by a Singer cycle on Z258

  • The Singer-cycle example uses powers of α to enumerate the points of P1(F257), then maps each point through the specified matrix action; the resulting permutation has δ=2.The example reports spectrum (A0, A1, A2)=(33025, 256, 33025).Source: §8.1.1 · p. 30

8.1.2 Binomial example on Z364

  • The binomial example uses H(x)=x^3−αx and maps each vector R^i e0 to the index determined by its image under H, up to sign; the permutation has δ=2.Its reported differential spectrum is (A0, A1, A2)=(33124, 65884, 33124).Source: §8.1.2 · p. 30

8.1.3 Example from completed reciprocals on Z262

  • For p=131, a=2, and c=0, the completed-reciprocal example has four character values equal to −1 and produces a permutation with δ=2.The character arguments are 2, 128, 124, and 130; the reported spectrum is (33541, 1300, 33541).Source: §8.1.3 · p. 31
Loading 2609.05917v1…