🔢 mathematics

Locally-APN Binomials with Low Boomerang Uniformity in Odd Characteristic

This paper extends recent results on locally-APN binomials with low boomerang uniformity in odd characteristic by establishing a general condition under which $F_r(x)=x^r+x^{r+\frac{q-1}{2}}$ achieves boomerang uniformity at most 2, while also analyzing the differential and boomerang spectra of specific instances like $F_3$ , $F_{\frac{2q-1}{3}}$ , and $F_2$ over fields of characteristic 3.

Original authors: Namhun Koo, Soonhak Kwon, Minwoo Ko, Byunguk Kim

Published 2026-04-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Namhun Koo, Soonhak Kwon, Minwoo Ko, Byunguk Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a security guard at a very high-tech vault (a block cipher) protecting a digital treasure. To keep the vault safe, you use a special lock mechanism called an S-box. This lock scrambles the input data in a way that makes it incredibly hard for thieves to figure out the original key by watching how small changes in the input affect the output.

In the world of cryptography, mathematicians measure how "confusing" this lock is using two main tools: Differential Uniformity and Boomerang Uniformity.

Differential Uniformity is like testing how the lock reacts when you push the door slightly. If a tiny nudge always causes a predictable, massive swing, the lock is weak. If the nudge causes a chaotic, hard-to-predict reaction, the lock is strong. The goal is to keep this number as low as possible (ideally 1 or 2).
Boomerang Uniformity is a more complex test. Imagine throwing a boomerang at the lock. You throw it, it hits, and it comes back. This test checks if a specific pattern of "throw and return" reveals a weakness. Again, a lower number means a stronger lock.

The Problem: Finding the Perfect Lock

For years, mathematicians have been hunting for specific mathematical formulas (called functions) that create these perfect locks. One popular family of formulas looks like this:
$F(x) = x^r + x^{r + \text{something}}$
Think of $x^r$ as the main engine of the lock, and the second part as a special "tuner" that adjusts how the lock behaves based on whether the input number is a "square" or a "non-square" (a property called the quadratic character).

The authors of this paper, Namhun Koo and his team, focused on a specific type of math world called odd characteristic (think of it as a universe where numbers behave differently than in our standard computer binary world). They wanted to find specific settings for the "engine" (the exponent $r$ ) that make the lock incredibly strong.

The Discovery: A New Rule for Strong Locks

The team discovered a "Golden Rule" for making these locks strong. They found that if you pick a specific exponent $r$ and ensure that a certain equation (related to how the lock reacts to a push) has at most one solution in a specific zone, then two amazing things happen:

The Differential Uniformity is low: The lock is "locally-APN." This is a fancy way of saying that for almost every possible push, the lock reacts in a way that is very hard to predict (specifically, the reaction is limited to just 2 possibilities).
The Boomerang Uniformity is low: The lock is also resistant to the "boomerang" attack, with a score of at most 2.

They proved that this rule works for a whole list of specific exponents (like $r=3$ , $r=2$ , and others involving powers of 3). It's like finding a master key that opens the door to a whole new class of super-secure locks.

The Surprise: Fixing a Previous Mistake

Here is the most exciting part of their story.

In the past, other researchers studied a specific lock where the engine was set to $r=2$ (a very simple formula). They claimed that for large enough vaults, this lock had a "Boomerang Uniformity" of 2. They thought it was good, but not perfect.

The authors of this paper looked closer, specifically in a universe where the prime number is 3 (a specific type of math world). They discovered that the previous researchers missed a subtle detail because of a quirk in how numbers work when the prime is 3 (specifically, that $1 = -2$ in this world).

Their finding: In this specific world, the lock with $r=2$ is actually even stronger than previously thought. Its Boomerang Uniformity is 1.

Analogy: Imagine a previous study said a car's top speed was 100 mph. This new paper says, "Actually, if you look at the engine under these specific conditions, it's running at 101 mph." It's a small difference, but in the world of cryptography, getting that perfect score of 1 is a huge deal.

What They Did Exactly

Proved the Rule: They showed mathematically that if the "push" equation has limited solutions, the lock is strong (locally-APN) and boomerang-resistant.
Checked the List: They verified that their list of special exponents (found in their "Table 3") all follow this rule.
Mapped the Terrain: For the exponents $r=3$ and $r=2q-1/3$ , they didn't just say "it's strong"; they drew a complete map (called the spectrum) showing exactly how many times the lock reacts with 0, 1, or 2 solutions. This gives engineers a precise blueprint.
Corrected the Record: They proved that for the $r=2$ case in characteristic 3, the lock is actually perfect (uniformity 1), correcting the previous belief that it was 2.

Summary

In simple terms, this paper is a guidebook for building better digital locks. The authors found a reliable recipe to ensure these locks are highly resistant to two major types of attacks. They also fixed a small error in a previous guidebook, showing that one specific lock design is actually even more secure than anyone realized in certain mathematical worlds. Their work helps cryptographers choose the best formulas to protect data in the future.

1. Problem Statement

The paper addresses the cryptographic properties of a specific class of functions defined over finite fields $\mathbb{F}_q$ (where $q = p^n$ is an odd prime power). The focus is on functions of the form:
$F_r(x) = x^r(1 + \chi(x)) = x^r + x^{r + \frac{q-1}{2}}$
where $\chi(x) = x^{\frac{q-1}{2}}$ is the quadratic character.

The study aims to determine two critical security metrics for these functions:

Differential Uniformity ( $\delta_F$ ): Measures resistance to differential cryptanalysis. A function is Almost Perfect Nonlinear (APN) if $\delta_F = 2$ . Since these functions are not APN in the strict global sense for many parameters, the authors investigate if they are Locally-APN (satisfying $\delta_F(1, b) \le 2$ for all $b \in \mathbb{F}_q \setminus \mathbb{F}_p$ ).
Boomerang Uniformity ( $\beta_F$ ): Measures resistance to boomerang attacks. The paper seeks to establish if $\beta_F \le 2$ and to determine the full Boomerang Spectrum (the distribution of solution counts for the boomerang connectivity table).

Specifically, the paper investigates whether these properties hold for a subclass of exponents $r$ where the monomial $x^r$ has low differential uniformity (often Perfect Nonlinear or APN) and $\gcd(r, q-1) \mid 2$ .

2. Methodology

The authors employ a combination of algebraic number theory, character sum analysis, and combinatorial counting over finite fields.

Decomposition of Solution Sets: The authors partition the field $\mathbb{F}_q$ based on the quadratic character of $x$ and $x+1$ . They define sets $S_{ij} = \{x \in \mathbb{F}_q : \chi(x) = (-1)^i, \chi(x+1) = (-1)^j\}$ for $i, j \in \{0, 1\}$ .
Differential Analysis: To count solutions to $F_r(x+a) - F_r(x) = b$ , they reduce the problem to analyzing the equation $(x+1)^r - x^r = b$ within specific sets $S_{ij}$ . They prove that if the equation has at most one solution in $S_{00}$ (where both $x$ and $x+1$ are quadratic residues), the function is Locally-APN.
Boomerang Analysis: They analyze the system of equations defining the Boomerang Connectivity Table (BCT). By decomposing the solution space $(x, y)$ into products of the sets $S_{ij} \times S_{kl}$ , they bound the number of solutions.
Character Sums: The authors utilize Weil bounds and specific properties of quadratic characters (e.g., $\sum \chi(f(x))$ ) to estimate the number of solutions and derive exact differential and boomerang spectra for specific cases.
Linear Equivalence: They utilize Lemma 2.8 to show that certain exponents (like $3^{k+1}/2$ ) are linearly equivalent to others, allowing results to be generalized.

3. Key Contributions

A. General Theoretical Framework

The paper establishes a sufficient condition for a binomial $F_r$ to be Locally-APN with low boomerang uniformity:

Condition: If $\gcd(r, q-1) \mid 2$ $g cd (r, q - 1) ∣ 2$ and the equation $(x+1)^r - x^r = b$ $(x + 1)^{r} - x^{r} = b$ has at most one solution in $S_{00}$ $S_{00}$ for all $b \in \mathbb{F}_q^*$ $b \in F_{q}^{*}$ , then:
- $\delta_{F_r} = \frac{q+1}{4}$ (Locally-APN).
- $\beta_{F_r} \le 2$ .

B. Verification for Specific Exponents

The authors verify that the above condition holds for a list of exponents $r$ (summarized in Table 3 of the paper), including:

$r = p^k + 1$ (for odd $n$ ).
$r = \frac{3^{k+1}}{2}$ (Generalized Coulter-Matthews exponents).
$r = 3$ and $r = \frac{2q-1}{3}$ (under $q \equiv 11 \pmod{12}$ ).
$r = \frac{3^{n+1}-1}{2}$ and $r = \frac{3^{n+1}-1}{8}$ (for $p=3$ ).

C. Exact Spectra Determination

Differential Spectrum: The paper derives the exact differential spectrum for $F_3$ $F_{3}$ and $F_{\frac{2q-1}{3}}$ $F_{\frac{2 q - 1}{3}}$ when $q \equiv 11 \pmod{12}$ $q \equiv 11 (mod 12)$ .
- For $F_3$ , the spectrum depends on a character sum $\Gamma$ .
- For $F_{\frac{2q-1}{3}}$ , the spectrum is explicitly calculated as $\{\omega_0 = \frac{q-3}{2}, \omega_1 = \frac{q+5}{4}, \omega_2 = \frac{q-3}{4}, \omega_{\frac{q+1}{4}} = 1\}$ .
Boomerang Spectrum for $F_2$ ( $p=3$ ): The paper provides the first complete boomerang spectrum for $F_2$ when $p=3$ and $n$ is odd.

4. Key Results

Locally-APN Property: The function $F_r$ is proven to be Locally-APN with differential uniformity $\frac{q+1}{4}$ for all exponents listed in Table 3.
Boomerang Uniformity Bound: For the same class of exponents, the boomerang uniformity is proven to be at most 2.
Correction of Previous Literature (Significant Finding):
- Previous work (Mesnager and Wu, [14]) conjectured and proved that for large $q$ , the boomerang uniformity of $F_2$ is 2.
- This paper disproves this for characteristic 3. The authors prove that for $p=3$ and odd $n$ , the boomerang uniformity of $F_2$ is exactly 1.
- Reason: In characteristic 3, the identity $1 = -2$ causes certain cases considered in previous proofs to become incompatible or degenerate, leading to a lower uniformity.
Explicit Boomerang Spectrum for $F_2$ ( $p=3$ ):
The spectrum is given by $\nu_0 = \frac{3q-5+2\Lambda}{4}$ and $\nu_1 = \frac{q+1-2\Lambda}{4}$ , where $\Lambda = \sum_{x \in \mathbb{F}_q} \chi(x+1)\chi(x^2+1)$ .

5. Significance

Cryptographic Design: The results provide new candidates for S-boxes in block ciphers operating over odd characteristic fields. Functions with low differential and boomerang uniformity are essential for resisting modern cryptanalytic attacks.
Theoretical Advancement: The paper extends the understanding of "Locally-APN" functions beyond the well-studied even characteristic cases. It provides a unified framework for analyzing binomials with specific exponent structures.
Refinement of Bounds: By identifying a specific case ( $p=3$ ) where the boomerang uniformity drops from 2 to 1, the paper highlights the importance of characteristic-specific analysis in finite field cryptography, correcting assumptions made in general characteristic studies.
Spectrum Characterization: Providing exact differential and boomerang spectra (rather than just uniformity bounds) allows for a more precise evaluation of the security margins of these functions.

In conclusion, this paper successfully generalizes the Locally-APN property to a broad class of binomials in odd characteristic, proves their low boomerang uniformity, and offers a critical correction to the understanding of $F_2$ in characteristic 3.