PaperlayerView exact revision on arXiv

Source-linked AI summary

On APN Functions with Boomerang Uniformity One over $\mathbb F_{3^n}$: Differential and Boomerang Spectra and CCZ-Inequivalence

Namhun Koo, Soonhak Kwon, Minwoo Ko, Byunguk Kim

arXiv:2609.08968v1cs.CR

TL;DR

APN functions with boomerang uniformity one were previously known only as isolated small-field examples, while known infinite families did not provide APN functions at that value. The paper perturbs sign-switches of ternary DO PN functions and determines their spectra. It obtains infinite families attaining the optimal APN boomerang uniformity, along with CCZ-inequivalence results.

  • Problem

    APN functions with boomerang uniformity one were known only through isolated small-field examples, and earlier infinite families with uniformity at most one did not yield APN functions.

    Source: §1 · p. 3, §3.4 · p. 17

  • Method

    The paper perturbs sign-switches of DO PN functions over F_{3^n}, with odd n > 1, and analyzes their differential and boomerang spectra.

    Source: §1 · p. 3, §6 · p. 34

  • Results

    Exactly (q−3)/2 parameters yield APN functions with boomerang uniformity one, and the remaining (q+3)/2 yield uniformity two.

    Source: §6 · p. 34

  • Takeaways & Limitations

    The construction gives infinite families attaining the least possible boomerang uniformity for APN functions in odd characteristic.

    Source: §6 · p. 34

    The method relies essentially on the DO property, so its affine-perturbation argument does not directly apply to the generally non-DO Coulter–Matthews PN family.

    Source: §6 · p. 34

Abstract

from arXiv · show

Let $q=3^n$, where $n>1$ is odd, and let $g:\Fq\to\Fq$ be a perfect nonlinear (PN) function represented by a Dembowski--Ostrom (DO) polynomial. Put $\tau=g(1)$, let $\epsilon$ be the indicator of $\Fthree^*$, and, for $c\in\Fq$, define $\widetilde G_c(x):=g(x+c)+\tau\epsilon(x)$. We prove that every $\widetilde G_c$ is APN and has boomerang uniformity either one or two. More precisely, \[ \beta_{\widetilde G_c}=1 \quad\Longleftrightarrow\quad c\in\mathcal C_g :=\{c\in\Fq\setminus\Fthree:g(c)+\tau\notin g(\Fq)\}, \qquad |\mathcal C_g|=\frac{q-3}{2}, \] whereas $\beta_{\widetilde G_c}=2$ for the remaining $(q+3)/2$ parameters. We determine the common differential spectrum and complete boomerang spectra of all the functions $\widetilde G_c$. Since boomerang uniformity one is the least possible for an APN function over a finite field of odd characteristic, this gives, to the best of our knowledge, the first general construction yielding infinite families of APN functions attaining this optimum. This common differential spectrum rules out CCZ equivalence with every power function and every Ness--Helleseth-type binomial. We also prove that CCZ equivalence between sign-switches of DO PN functions forces EA equivalence between the original PN functions. Using the orders of the nuclei of the associated presemifields, we exhibit, for infinitely many odd $n$, three pairwise CCZ-inequivalent PN functions over $\F_{3^n}$, one from each of the Gold $f_1$, Ding--Yuan $f_3$, and Bierbrauer $f_5$ families. Consequently, over each such field, our construction produces three pairwise CCZ-inequivalent APN functions with boomerang uniformity one. The smallest extension degree obtained in this way is $n=45$.

1 Introduction

The paper introduces a perturbation of sign-switches of ternary DO PN functions that yields APN functions with boomerang uniformity one for a precise set of parameters. It determines their spectra and uses them to establish CCZ-inequivalence results.

1 Introduction

  • Earlier known infinite non-PN families with boomerang uniformity at most one did not yield APN functions; APN examples with uniformity one were known only over small fields.The paper presents its construction as filling this gap with infinite families.Source: §1 · p. 3

Main contributions of the paper

  • Exactly (q−3)/2 parameters give APN functions with boomerang uniformity one, while the remaining (q+3)/2 give boomerang uniformity two.Every function in the construction is APN, and boomerang uniformity one is optimal for APN functions in odd characteristic.Source: Main contributions of the paper · p. 4
  • The constructed family has a common exact differential spectrum and three or five possible complete boomerang spectra, according as boomerang uniformity is one or two.The sign-switch itself is APN with differential and boomerang uniformities both equal to two.Source: Main contributions of the paper · p. 4
  • The common differential spectrum separates the sign-switch from every power function and Ness–Helleseth-type binomial, establishing CCZ-inequivalence.The boomerang-spectrum comparison also distinguishes these classes, but is not used for CCZ-inequivalence because boomerang spectrum is not generally CCZ-invariant.Source: Main contributions of the paper · p. 4
  • CCZ equivalence between sign-switches of DO PN functions forces EA equivalence between their PN inputs.This switch-rigidity result transfers pairwise CCZ-inequivalence of suitable PN inputs to their associated APN functions.Source: Main contributions of the paper · pp. 4–5
  • For infinitely many odd extension degrees, the construction yields three pairwise CCZ-inequivalent APN functions with boomerang uniformity one, first at n = 45.The three inputs come from the Gold f1, Ding–Yuan f3, and Bierbrauer f5 families.Source: Main contributions of the paper · p. 5

2 Preliminaries for DO PN functions

The preliminaries establish structural properties of DO PN functions that support the later spectral arguments. They also record that the differential spectrum is invariant under CCZ equivalence.

2 Preliminaries for DO PN functions

  • A DO PN function over a field with q ≡ 3 (mod 4) is two-to-one, with every nonzero image value having exactly two preimages.The resulting partition of nonzero field elements implies that the image contains exactly one element from each pair {a, −a}.Source: §2 · pp. 5–6
  • For ternary DO PN g with τ = g(1), the preimages of 0, τ, and −τ are respectively {0}, {±1}, and empty.These preimage facts are used in the paper's differential-spectrum, boomerang-spectrum, and affine-criterion proofs.Source: §2 · pp. 6–7

Equivalence conventions and the differential spectrum

3 Exact differential and boomerang spectra and comparison

This section determines the exact differential and boomerang spectra of the sign-switch construction and compares them with those of power functions and Ness–Helleseth-type binomials. It also establishes the lower bound on boomerang uniformity for APN functions over odd-characteristic finite fields and shows that the constructed functions attain it in characteristic three.

3.1 The exact differential spectrum

  • For a ∈ F3*, D_aG is a permutation; for each a outside F3, its DDT row has four zeros, four 2s, and q−8 ones, so G is APN.Across nonzero a, two rows have type 1^q and q−3 rows have type 0^4 1^(q−8)2^4.Source: §3.1 · pp. 9–11

3.2 The exact boomerang spectrum

  • The BCT has two zero rows and q−3 rows with four entries equal to 2 and all others zero, giving G boomerang uniformity 2.Thus each nonzero entry in those rows equals 2.Source: §3.2 · pp. 13–14

3.3 Comparison with power functions and Ness–Helleseth-type binomials

  • The common differential spectrum rules out CCZ equivalence between G and every power function or Ness–Helleseth-type binomial.The comparison treats classes whose nonzero DDT and BCT rows share a common value distribution.Source: §3.3 · pp. 14–15
  • The constructed G has differential and boomerang spectra different from those of every power function and Ness–Helleseth-type binomial, so it is CCZ-inequivalent to each.The spectrum inequalities are SDDT(G) ≠ SDDT(H) and SBCT(G) ≠ SBCT(H); the differential-spectrum inequality implies CCZ-inequivalence.Source: §3.3 · p. 15
  • At n = 11, the computed boomerang uniformities of F1–F6 are (8, 8, 4, 8, 6, 10), while β_G = 2.For every defined F1–F6 and odd 5 ≤ n ≤ 11, computations give β_Fi ≥ 4.Source: Selected APN monomial families and… · p. 17
  • For every odd n > 1 and DO PN input g, the construction has δ_G = β_G = 2, giving the first known infinite family in characteristic three with both uniformities equal to 2.The paper also notes that the inverse family appears to have been the only previously established infinite APN family over odd-characteristic fields with boomerang uniformity two.Source: Selected APN monomial families and… · p. 17

3.4 A lower bound on the boomerang uniformity of APN functions

  • If δ_F ≤ 2 and β_F = 0, then F is perfect nonlinear with δ_F = 1; conversely, every perfect nonlinear F has β_F = 0.This criterion underlies the lower bound for APN functions.Source: §3.4 · p. 17
  • Every APN function over a finite field of odd characteristic has boomerang uniformity at least 1.Thus boomerang uniformity zero is impossible for an APN function.Source: §3.4 · p. 18
  • The construction attains β = 1 for infinite families of APN functions over F_3^n for odd n > 1.The paper identifies this as the first general construction yielding infinite families of APN functions with boomerang uniformity one.Source: §3.4 · p. 18

4 APN functions with boomerang uniformity one via affine perturbations

This section studies affine perturbations of sign-switched APN maps arising from DO PN inputs, characterizing the parameters that yield boomerang uniformity one. It gives a translated family with an exact parameter count and applies the criteria to known DO PN examples, including Gold-based perturbations realizing all eight boomerang spectra.

4.1 The affine-perturbation construction

  • For any F3-affine perturbation with linear part M, GA remains APN, and βGA=1 exactly when M(u) avoids {0, ±L1(u), ±(τ−g(u))} for every u outside F3; otherwise βGA=2.The constant part of the affine map cancels from derivatives and output differences.Source: §4.1 · p. 19
  • The Gold function g(x)=x^4 and Ding–Yuan function g(x)=x^10+x^6−x^2 both yield APN examples with A(x)=±x and boomerang uniformity one.For Ding–Yuan, the stated spectrum uses zn=0, 6, 10, or 16 according as gcd(n,15)=1, 3, 5, or 15.Source: §4.1 · p. 21
  • Among the q parameter values c ∈ Fq, exactly (q−3)/2 give boomerang uniformity 1, and exactly (q+3)/2 give boomerang uniformity 2.Source: §4.1 · p. 24
  • Corollary 4.5 gives complete BCT row distributions and boomerang spectra for every translated-family parameter, covering admissible and nonadmissible c and the special cases in F3.The cited corollary distinguishes the case c∈Cg and further cases among the remaining parameters.Source: §4.1 · pp. 24–25
  • For every odd n ≥ 9, the perturbation family from the Gold function g(x) = x^10 realizes all eight boomerang spectra described in Corollary 4.5.The argument establishes that every sign pattern occurs for some c outside F3, yielding the three κ_c values in both parameter classes; c = 0 and c = ±1 give the two remaining spectra.Source: §4.1 · p. 26

4.2 Applications to known DO PN families

  • The corresponding f4 and f5 functions are linearly equivalent, and therefore EA- and CCZ-equivalent, consistent with Bierbrauer’s description of Theorem 4 as a slight generalization of the Zha–Kyureghyan–Wang family.Source: §4.2 · p. 27
  • For the functions \(G_{i,c}\), differential uniformity is 2 for every \(c\in\mathbb F_q\), while boomerang uniformity is 1 exactly when \(c\in C_i\).Source: §4.2 · p. 28
  • Exhaustive computations for selected f1, f3, and f5 PN functions support realization of all eight spectra for each displayed function.All six κ_i,c counts in each Table 3 row are positive; the two additional spectra come from c = 0 and c ∈ F3*, as covered by Corollary 4.5(c) and (d).Source: Table 3 · p. 28, §4.2 · p. 28
  • Every perturbation eG_i,c has algebraic degree 2n, which cannot distinguish these functions’ EA-equivalence classes.The nonzero sign-switch term has a nonzero x^(q−1) term of base-3 weight 2n, while the translated DO PN polynomial has degree 2.Source: §4.2 · p. 28
  • If DO PN functions g and h are not CCZ-equivalent, their sign-switches and associated boomerang-uniformity-one functions are also not CCZ-equivalent.For infinitely many odd n, the Gold f1, Ding–Yuan f3, and Bierbrauer f5 functions are pairwise CCZ-inequivalent, as are their associated APN functions with boomerang uniformity one.Source: §4.2 · pp. 28–29

5 Switch-rigidity and CCZ-inequivalence

The section proves that CCZ equivalence between sign-switches of DO PN functions forces EA equivalence between their PN inputs. It applies this rigidity to construct infinitely many extension degrees with three pairwise CCZ-inequivalent APN functions of boomerang uniformity one.

5.1 Uniqueness of the vertical subspace and CCZ-to-EA collapse

  • The vertical subspace is the unique n-dimensional F3-subspace whose nonzero vectors have zero difference count, forcing CCZ maps between the switches to preserve it.This yields the CCZ-to-EA collapse for the switched maps.Source: §5.1 · pp. 29–30

5.2 Uniqueness of the underlying PN function and switch-rigidity

  • CCZ equivalence between sign-switches of DO PN functions forces EA equivalence between the original PN functions.The result follows by recovering the PN function from a PN map that agrees with its sign-switch outside a two-point translate of F3*.Source: §5.2 · pp. 31–32

5.3 CCZ-inequivalence arising from inequivalent PN inputs

  • If the original PN functions are not CCZ-equivalent, neither are their sign-switches or the associated perturbed maps.The implication uses switch-rigidity and the EA equivalence between each perturbed map and its sign-switch.Source: §5.3 · p. 33
  • For infinitely many odd n, the Gold, Ding–Yuan, and Bierbrauer constructions yield three pairwise CCZ-inequivalent APN functions with boomerang uniformity one.The first degree obtained is n = 45.Source: §5.3 · pp. 33–34

6 Conclusion and further directions

For odd n > 1, the construction from a DO PN function yields APN functions with a common differential spectrum and parameter-dependent boomerang spectra. It attains boomerang uniformity one for half of the parameters and establishes an infinite-degree, three-family source of pairwise CCZ-inequivalent examples, subject to the DO setting.

6 Conclusion and further directions

  • Exactly (q − 3)/2 parameters give boomerang uniformity one, while the remaining (q + 3)/2 give uniformity two.All constructed functions are APN and share a common exact differential spectrum; their complete boomerang spectra have three types in the first case and five in the second.Source: §6 · p. 34
  • Boomerang uniformity one is the least possible for an APN function over a finite field of odd characteristic.For differential uniformity at most two, boomerang uniformity zero implies perfect nonlinearity.Source: §6 · p. 34
  • The common differential spectrum separates the construction from power functions and Ness–Helleseth-type binomials under CCZ equivalence.Switch-rigidity and nucleus orders also yield three pairwise CCZ-inequivalent examples from the Gold, Ding–Yuan, and Bierbrauer families for infinitely many odd degrees, first at n = 45.Source: §6 · p. 34
  • The method relies essentially on the DO property, which makes every derivative D_cg affine.The present affine-perturbation argument does not directly apply to the generally non-DO Coulter–Matthews PN family.Source: §6 · p. 34
Loading 2609.08968v1…