🔢 mathematics

On APN Exponents and the Differential and Boomerang Properties of Binomials in Characteristic 3

This paper systematically analyzes Almost Perfect Nonlinear power functions in characteristic 3 and rigorously proves that specific binomials derived from these exponents, including those with $r = 2 \cdot 3^{\frac{n-1}{2}} + 1$ and $r = 3^n - 3$ , achieve minimal boomerang uniformity of 0 or 1, thereby extending the understanding of cryptographic properties in this field.

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

Published 2026-05-25

📖 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 designing a secret code to protect a digital vault. To make this code unbreakable, you need a special "lock" (a mathematical function) that scrambles data so thoroughly that no one can guess the original message, even if they know how the lock works.

In the world of cryptography, mathematicians use two main tools to test how strong these locks are: Differential Uniformity and Boomerang Uniformity.

Think of Differential Uniformity as a test for "slippery slopes." If you nudge the input of the lock just a tiny bit, how much does the output change? If the change is predictable, a hacker can slide down the slope and crack the code. The best locks are "Almost Perfect Nonlinear" (APN), meaning they are so slippery that even a tiny nudge creates a chaotic, unpredictable result.

Think of Boomerang Uniformity as a test for a "boomerang attack." Imagine a hacker throws a question at the lock, gets an answer, and then throws a slightly different question to see if the answers bounce back in a way that reveals the secret. A low boomerang uniformity means the answers don't bounce back in a predictable pattern; they scatter randomly. The lower the number, the better the lock.

The Paper's Mission: Finding the "Perfect" Scramblers in a Specific World

This paper focuses on a specific type of mathematical lock called a binomial (a function with two parts) in a world called Characteristic 3. In this mathematical universe, numbers wrap around after hitting 3 (like a clock that only has 1, 2, and 0).

The authors discovered that in this specific "Characteristic 3" world, these binomial locks seem to be exceptionally good at hiding secrets. They found instances where the "boomerang score" is incredibly low—specifically 0 or 1. A score of 0 is the theoretical "gold standard," meaning the lock is practically immune to this type of attack.

What They Actually Found

The researchers didn't just guess; they built a systematic map to find these super-strong locks. Here is what they did, broken down simply:

1. The "APN" Blueprint
First, they looked at a known family of "Almost Perfect Nonlinear" (APN) functions. Think of these as the master blueprints for the strongest locks. The authors created a new, explicit formula (a "parametrization") to generate these blueprints specifically for the Character 3 world.

The Analogy: Imagine they found a master key that can generate thousands of unique, high-security locks, whereas before, people only had a few scattered examples. They proved that for small sizes (up to a certain limit), this master key explains almost every strong lock they've ever seen.

2. The "Zero-Boomerang" Classes
Using these blueprints, they identified two specific types of binomial locks that achieve a Boomerang Uniformity of 0.

Class A: These locks are built directly from the new APN blueprints mentioned above.
Class B: These locks use a specific mathematical exponent (a power number) of the form $2 \cdot 3^{(n-1)/2} + 1$ .
The Result: For these specific classes, the "boomerang" never bounces back predictably. It's a perfect defense.

3. The "One-Boomerang" Discovery
They also studied a different type of lock where the exponent is $3^n - 3$ .

The Result: They proved that for these locks, the boomerang score is 1 (which is still extremely low and very secure) when the size of the field is large enough (specifically, when $n \ge 5$ ).
The Deep Dive: They didn't just stop at the score; they calculated the entire "spectrum" of this lock. Imagine taking a photo of every possible way the lock reacts to an attack and cataloging exactly how often each reaction happens. They did this mathematically, providing a complete picture of its security.

4. The Computer Search
To make sure they hadn't missed anything, the authors ran a massive computer search for small field sizes.

They found many examples of locks with scores of 0 and 1.
They matched these computer findings with their new mathematical formulas, confirming that their formulas cover almost all the "perfect" cases they found.
They noted that for the "score of 1" cases, some are still "sporadic" (happening by chance rather than fitting a neat pattern), and finding a pattern for those is a job for future research.

The Bottom Line

In simple terms, this paper is a catalog of the best possible digital locks for a specific type of mathematical world (Characteristic 3).

They created a new recipe to generate these locks.
They proved that two specific recipes produce perfectly secure locks (score 0).
They proved that a third recipe produces near-perfect locks (score 1) and mapped out exactly how they behave.
They used computers to verify that their recipes cover almost every known example of these super-secure locks.

The paper concludes that in this specific mathematical world, these binomial functions are exceptionally resistant to "boomerang" style attacks, making them prime candidates for building unbreakable encryption systems.

Technical Summary: On APN Exponents and the Differential and Boomerang Properties of Binomials in Characteristic 3

Problem Statement
The paper investigates the cryptographic properties of binomial functions of the form $F_r(x) = x^r(1 + \chi(x))$ over finite fields $\mathbb{F}_{3^n}$ , where $\chi(x)$ is the quadratic character. While differential uniformity is a standard metric for resistance against differential attacks, it does not fully capture resistance to boomerang attacks. The notion of boomerang uniformity ( $\beta_F$ ) was introduced to address this. Previous studies [9] established that for certain exponents $r$ , the function $F_r$ exhibits low differential uniformity and boomerang uniformity bounded by 2. However, empirical observations suggest that in characteristic 3, instances of extremely low boomerang uniformity (specifically 0 or 1) occur more frequently than in other characteristics. The paper aims to systematically analyze these phenomena, identify the specific exponents $r$ that yield boomerang uniformity 0 or 1, and provide rigorous proofs for these classes.

Methodology
The authors employ a combination of theoretical analysis and computational verification:

Theoretical Framework: The study builds upon the concept of "locally-PN" and "locally-APN" functions. By analyzing the differential equation $(x+1)^r - x^r = b$ and the associated boomerang system, the authors derive conditions under which the differential spectrum and boomerang spectrum can be explicitly determined.
APN Classification: The paper provides a systematic parametrization of Almost Perfect Nonlinear (APN) power functions arising from the construction of Zha and Wang [23]. This involves solving the Diophantine condition $(3m+1)r - 2 = k(3^n-1)$ to generate explicit families of exponents.
Character Sums and Spectral Analysis: To determine the boomerang spectrum for specific classes (notably $r = 3^n - 3$ ), the authors evaluate character sums involving quadratic characters and polynomial roots.
Computational Search: Exhaustive searches were conducted for small values of $n$ (up to $n=13$ ) using SageMath to identify exponents yielding boomerang uniformity 0 or 1. These results are cross-referenced with the theoretical families derived.

Key Contributions and Results

Parametrization of APN Exponents: The authors present an explicit parametrization (Proposition 3.3) for APN exponents derived from the framework in [23]. They demonstrate that for $n \le 13$ , this generalized construction accounts for all known APN power functions in characteristic 3 that were not previously listed in standard tables [2]. This includes recovering known classes (e.g., $r = 3^{(n+1)/2} - 1$ ) and identifying new sporadic instances.
Two Classes with Boomerang Uniformity 0: The paper rigorously proves that two specific classes of binomials $F_r$ $F_{r}$ possess the minimum possible boomerang uniformity of 0:
1. Exponents $r$ arising from the APN construction in [23] (satisfying the condition $(3m+1)r - 2 = k(3^n-1)$ ).
2. The exponent $r = 2 \cdot 3^{(n-1)/2} + 1$ .
  For both classes, the authors prove that $F_r$ is locally-PN and derive their differential spectra.
Analysis of $r = 3^n - 3$ : The paper analyzes the binomial with exponent $r = 3^n - 3$ . It is proven that for odd $n \ge 5$ , this function is locally-APN with boomerang uniformity 1. The authors completely determine its boomerang spectrum by evaluating specific character sums, providing explicit formulas for the number of $b$ values yielding $\beta_{F_r}(1, b) = 0$ and $1$.
Numerical Classification: Through exhaustive searches for $n \le 13$ , the authors compile tables of exponents yielding boomerang uniformity 0 and 1. They observe that for $n \le 9$ , the condition of being locally-PN appears to be both necessary and sufficient for boomerang uniformity 0, even without the strict $\gcd(r, 3^n-1) \in \{1, 2\}$ assumption used in previous theoretical bounds.

Significance
The paper clarifies and extends existing studies on the cryptographic properties of binomials in characteristic 3. Its primary significance lies in:

Systematic Characterization: Providing a unified framework that explains why certain binomials in characteristic 3 achieve boomerang uniformity 0 or 1, linking these properties directly to specific APN exponent constructions.
Extension of Bounds: Demonstrating that the general bound of boomerang uniformity 2 (established in [9]) can be strictly improved to 0 or 1 for specific infinite families in characteristic 3.
Completeness of APN Classification: Showing that the parametrization of APN exponents from [23] covers all known APN power functions in characteristic 3 for small $n$ , suggesting a comprehensive structure for these functions.
Empirical Validation: The numerical results support the theoretical findings and highlight a strong correlation between the locally-PN property and boomerang uniformity 0, posing this relationship as a potential area for future rigorous proof.

The authors conclude that while they have identified infinite families and sporadic cases with optimal boomerang properties, the precise equivalence between the locally-PN property and boomerang uniformity 0 remains an open problem, and extending the sporadic cases of boomerang uniformity 1 to infinite families is a direction for future research.

The Paper's Mission: Finding the "Perfect" Scramblers in a Specific World

What They Actually Found

The Bottom Line

More like this