🔢 mathematics

A class of locally differentially $4$-uniform power functions with Niho exponents

This paper determines the differential spectrum of the power function $F(x) = x^{3q - 2}$ over $\mathbb{F}_{q^2}$ with $q = 2^m$ and even $m \geq 4$ , proving that it is a locally differentially 4-uniform function with a Niho exponent.

Original authors: Haode Yan, Kangquan Li

Published 2026-04-16

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Haode Yan, Kangquan Li

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 high-security vault for a bank. To keep thieves out, you need a special lock mechanism that scrambles the combination so thoroughly that even if a thief tries to guess the pattern by making tiny changes to their input, they can't predict the output. In the world of digital security, this "lock" is called a cryptographic function, and the "tiny changes" are called differential attacks.

This paper is about inventing a new, incredibly strong type of lock and proving exactly how good it is.

Here is the breakdown of the research using simple analogies:

1. The Setting: The Digital Playground

The researchers are working in a specific mathematical world called a finite field. Think of this as a giant, circular playground with a fixed number of spots (let's say $q^2$ spots).

The Function: They are testing a specific rule for moving around this playground. The rule is: "Take your current spot number, raise it to a very specific power ( $3q - 2$ ), and that's your new spot."
The Exponent: The power they chose ( $3q - 2$ ) is special. It's called a Niho exponent. Think of this like choosing a specific, rare key shape that mathematicians have known for a long time is good at creating complex patterns, but nobody had fully mapped out how this specific key behaves in this specific playground.

2. The Test: The "Butterfly Effect"

To see if the lock is strong, the researchers perform a test called differential analysis.

The Scenario: Imagine you and a friend are standing on two spots in the playground that are exactly one step apart. You both apply the "lock rule" to move to new spots.
The Question: If you know how far apart you started (one step), how many different ways could you end up at a specific distance apart on the other side?
The Goal: A weak lock is predictable. If you move one step, you always end up moving two steps. That's bad because a thief can guess the pattern. A strong lock is chaotic. If you move one step, you might end up moving 2 steps, or 4 steps, or 100 steps, depending on where you started.

3. The Discovery: "Locally" Strong

The researchers wanted to count exactly how many times each outcome happens. This collection of counts is called the Differential Spectrum. It's like a report card for the lock.

They found something fascinating:

The "Perfect" Case: If you start at a specific spot (spot #1), the rule is actually too predictable. It behaves like a weak link.
The "Locally" Strong Case: However, for every other spot in the entire playground (except that one weak spot), the rule is incredibly strong.
- They proved that for almost all starting positions, the "distance" between your new spots is either 0, 2, or 4.
- Crucially, they showed that the number of times you get a "distance of 4" is very low and well-controlled.

They call this "Locally Differentially 4-Uniform."

Analogy: Imagine a maze. In one tiny corner of the maze, the walls are straight and easy to walk through (predictable). But everywhere else in the maze, the walls twist and turn so wildly that if you take one step, you can't predict where you'll end up, and you'll never get stuck in a loop of 4 steps or less. The maze is "locally" a nightmare for intruders.

4. The Math Magic (The "How")

How did they prove this?

They used a special mathematical tool called a trinomial (a polynomial with three terms). Imagine this as a filter or a sieve.
They showed that when you run the numbers through this sieve, the results are very limited. The sieve only lets through a few specific outcomes.
They also used a sequence of numbers (called $\tau_m$ ) that acts like a "secret code" to calculate exactly how many times each outcome occurs. It's like having a precise formula to count the number of times a coin lands on heads vs. tails, even after a million flips.

5. Why Does This Matter?

In the real world, these "locks" are used in S-Boxes (Substitution Boxes). These are the tiny engines inside encryption software (like the ones protecting your WhatsApp messages or bank transfers) that scramble data.

Why care about "4-uniform"? In the world of even-numbered math fields (which computers love), the best possible locks usually have a "uniformity" of 2. Getting a lock that is "4-uniform" is very good, but getting one that is locally 4-uniform while being a new, unique type of key is a major breakthrough.
The Result: This paper adds a new, verified tool to the toolbox of cryptographers. It gives them a new, mathematically proven way to build stronger, more secure digital vaults.

Summary

The authors took a specific, rare mathematical key (a Niho exponent), tested it in a digital playground, and proved that except for one tiny weak spot, it scrambles data so chaotically that it is extremely difficult for hackers to predict. They didn't just say "it's strong"; they wrote down the exact "scorecard" (the differential spectrum) showing exactly how it behaves, giving engineers the confidence to use it in future security systems.

1. Problem Statement

The paper addresses the problem of determining the differential spectrum of a specific class of power functions over finite fields, which is a critical task in symmetric cryptography.

Context: Cryptographic functions, particularly Substitution Boxes (S-boxes), must resist differential cryptanalysis. The resistance is measured by differential uniformity ( $\Delta_F$ ) and the differential spectrum (the distribution of solution counts for the difference equation $F(x+a) - F(x) = b$ ).
Specific Challenge: While low differential uniformity (ideally 2 for Almost Perfect Nonlinear or APN functions) is desirable, many known power functions have high uniformity or unknown spectra. The authors focus on Niho exponents, which are of significant interest in sequence design and coding theory but whose differential properties are not fully characterized for all cases.
Target Function: The paper investigates the power function $F(x) = x^{3q-2}$ over the finite field $\mathbb{F}_{q^2}$ , where $q = 2^m$ and $m \geq 4$ is an even integer. The exponent $d = 3q-2$ is a Niho exponent.
Goal: To determine the exact differential spectrum of $F(x)$ and establish its differential uniformity, specifically investigating whether it exhibits "locally" low uniformity (excluding trivial cases).

2. Methodology

The authors employ a combination of algebraic number theory, polynomial analysis over finite fields, and combinatorial counting to derive their results.

Field Decomposition: They utilize the multiplicative subgroup $U_{q+1} = \{x \in \mathbb{F}_{q^2}^* : x^{q+1} = 1\}$ . A key lemma (Lemma 2) allows any non-zero element $x$ to be uniquely decomposed as $x = yz$, where $y \in \mathbb{F}_q^*$ and $z \in U_{q+1}$ . This decomposition is used to transform the difference equation into a system involving elements of $U_{q+1}$ .
Trinomial Analysis: The authors analyze the preimage cardinalities of a specific class of trinomials $f(x) = x^2 + x^{1-q} + x^{2-q}$ over $\mathbb{F}_{q^2}$ . They prove that for $c \in \mathbb{F}_{q^2} \setminus \mathbb{F}_2$ , the equation $f(x) = c$ has at most 2 solutions. This result is crucial for bounding the number of solutions to the differential equation.
System of Equations: To calculate the differential spectrum, they must determine the number of solutions to the system:
$\begin{cases} x_1 + x_2 + x_3 + x_4 = 0 \\ x_1^d + x_2^d + x_3^d + x_4^d = 0 \end{cases}$
They leverage existing results on the number of solutions ( $n_3, n_4$ ) for such systems over finite fields, utilizing a recursively defined sequence $\tau_m$ to express the counts explicitly.
Algebraic Manipulation: By substituting variables and utilizing the properties of the subgroup $U_{q+1}$ , they reduce the differential equation $(x+1)^d + x^d = b$ to a form involving a single variable $t = u_1 + u_2$ (where $u_i \in U_{q+1}$ ). This allows them to bound the number of solutions based on the properties of the trinomial analyzed earlier.

3. Key Contributions

New Differential Spectrum: The paper provides the first complete determination of the differential spectrum for the power function $F(x) = x^{3q-2}$ over $\mathbb{F}_{q^2}$ with $q=2^m$ ( $m \geq 4$ even).
Locally 4-Uniform Property: The authors prove that while the function has a high global differential uniformity (equal to $q$ ), it is locally differentially 4-uniform. This means that for all $b \in \mathbb{F}_{q^2} \setminus \{0, 1\}$ , the number of solutions to the difference equation is at most 4. This is a significant cryptographic property, as it indicates strong resistance to differential attacks for the vast majority of input differences.
CCZ-Inequivalence: The authors note that this function is CCZ-inequivalent to other power functions with known differential spectra, expanding the known class of cryptographic functions.
Explicit Formulas: They derive closed-form expressions for the multiplicities $\omega_i$ (the number of $b$ values yielding $i$ solutions) in terms of $q$ and the sequence $\tau_m$ .

4. Main Results

The paper establishes the following theorem for $F(x) = x^{3q-2}$ over $\mathbb{F}_{q^2}$ ( $q=2^m, m \geq 4$ even):

Differential Uniformity: $\Delta_F = q$ $Δ_{F} = q$ .
- Note: The maximum value occurs at $b=1$ , where $\delta_F(1,1) = q$ .
Differential Spectrum: The spectrum $DS_F$ $D S_{F}$ is given by the multiset of non-zero multiplicities:
$DS_F = \left\{ \omega_0, \omega_2, \omega_4, \omega_q \right\}$
where:
- $\omega_q = 1$ (corresponding to $b=1$ )
- $\omega_4 = \frac{1}{8}(q^2 - \tau_m q + 1)$
- $\omega_2 = \frac{1}{4}(q^2 + (\tau_m - 2)q - 1)$
- $\omega_0 = \frac{1}{8}(5q^2 + (-\tau_m + 4)q - 7)$
- $\tau_m$ is defined by the recurrence $\tau_1 = 1/2, \tau_2 = -7/4, \tau_m = \frac{1}{2}\tau_{m-1} - \tau_{m-2}$ , or explicitly via the closed form involving powers of complex roots.
Locality: For all $b \in \mathbb{F}_{q^2} \setminus \{0, 1\}$ , $\delta_F(1,b) \in \{0, 2, 4\}$ . Thus, $F$ is locally differentially 4-uniform.

Verification: The theoretical results were verified using the computer algebra system MAGMA for specific cases ( $m=4, 6, 8$ ), showing perfect agreement between the derived formulas and direct computation.

5. Significance

Cryptographic Design: The discovery of a function that is locally 4-uniform is highly valuable for S-box design. While perfect nonlinearity (PN) or almost perfect nonlinearity (APN) is ideal, such functions often do not exist or are hard to construct in even characteristic fields. Locally 4-uniform functions offer a strong alternative, ensuring that the vast majority of differential characteristics have a very low probability of occurrence.
Expansion of Known Classes: This work adds a new family of Niho exponent functions to the limited list of power functions with fully determined differential spectra. It complements previous studies on $x^{2q-1}$ and other Niho exponents.
Theoretical Insight: The methodology of linking the differential spectrum to the roots of specific trinomials and the sequence $\tau_m$ provides a new analytical framework that could be applied to other power functions with Niho exponents.
Open Problems: The paper highlights that the differential spectrum for odd characteristic fields or other values of $q$ remains an open problem, guiding future research directions in finite field theory and cryptography.