On the Walsh spectra of quadratic APN functions

Basic Information

• Paper ID: 2510.12008
• Title: On the Walsh spectra of quadratic APN functions
• Authors: Sophie Hannah Bénéteau (University of Florida), Nicolas Goluboff (University of Massachusetts Amherst), Lukas Kölsch (University of South Florida), Divyesh Vaghasiya (University of South Florida)
• Classification: math.CO cs.IT math.IT
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12008

Abstract

Almost Perfect Nonlinear (APN) functions play a central role in block cipher design as optimal functions for resisting differential attacks. One of the most important properties of APN functions is their linearity, which is directly related to the Walsh spectrum of the function. This paper establishes two novel connections that enable us to derive strong conditions on the Walsh spectra of quadratic APN functions. The paper proves that the Walsh transform of a quadratic APN function $F$ operating on $n=2k$ bits is uniquely associated with vector space partitions of $\mathbb{F}_2^n$ and specific blocking sets in the corresponding projective space $PG(n-1,2)$. These connections enable us to prove multiple results concerning the Walsh spectrum of $F$, such as demonstrating that $F$ can have at most one component function with magnitude greater than $2^{\frac{3}{4}n}$, and finding the first non-trivial upper bound on the number of bent component functions of quadratic APN functions.

Research Background and Motivation

Importance of the Problem

1. Cryptographic Applications: APN functions are core building blocks in symmetric cipher design, particularly in substitution-permutation networks (SPNs) of block ciphers, providing optimal resistance against differential attacks.
2. Theoretical Challenges: While the magnitude distribution of quadratic APN functions in odd dimensions has been completely determined (all non-trivial components have magnitude $2^{\frac{n+1}{2}}$), the even-dimensional case remains an open problem.
3. Existing Limitations:
   • For even $n$, the only known constraint on magnitudes comes from the fourth moment characterization of the Walsh transform
   • Lack of non-trivial bounds on the number of bent component functions of quadratic APN functions
   • Insufficient understanding of the deep structure of Walsh spectra

Research Motivation

This paper aims to deepen the understanding of the structural properties of Walsh spectra and derive stronger constraints by establishing new connections between quadratic APN functions and geometric objects (vector space partitions and blocking sets).

Core Contributions

1. Established Vector Space Partition Connection: Proved a unique correspondence between the magnitude distribution of a quadratic APN function $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ (where $n$ is even) and vector space partitions of $\mathbb{F}_2^n$.
2. Constructed Blocking Set Theory: Proved that the set of non-trivial non-bent component functions $N_F$ forms a special blocking set in the projective space $PG(n-1,2)$.
3. Derived New Constraints:
   • Proved that $F$ can have at most one component function with magnitude greater than $2^{\frac{3}{4}n}$
   • Established the first non-trivial upper bound on the number of bent component functions
   • Provided necessary conditions for CCZ equivalence to a permutation
4. Completed Small-Dimensional Analysis: Performed complete analysis for dimensions 6, 8, and 10, determining all possible magnitude distributions.

Methodology Details

Task Definition

Study the Walsh spectrum structure of quadratic APN functions $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ (where $n$ is even), with:

• Input: A quadratic APN function $F$
• Output: Constraints and structural properties of the Walsh spectrum
• Objective: Understand the possibilities and limitations of magnitude distributions

Core Theoretical Framework

1. Vector Space Partition Theory

Definition of Difference Functions: For non-zero $a \in \mathbb{F}_2^n$, define $D_{F,a}(x) = F(x) + F(x+a)$.

Construction of Vector Spaces: Define

• $T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}$
• $\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}$
• $V_b = T_b \cup \overline{T_b}$

where $H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}$.

Main Theorem (Theorem 2.4): The magnitude of $F_b$ is $2^{\frac{n+\dim(V_b)}{2}}$.

2. Blocking Set Theory

Blocking Set Properties: The set of non-trivial non-bent component functions $N_F$ forms a blocking set with respect to $(n/2)$-spaces in $PG(n-1,2)$, with the intersection size with each $(n/2)$-space being odd.

Key Result: Using the Govaerts-Storme theorem on the size of minimal non-trivial blocking sets, we obtain upper bounds on the number of bent component functions.

Technical Innovations

1. Geometric Approach: First transformation of the Walsh spectrum problem for quadratic APN functions into a geometric problem involving vector space partitions and blocking sets.
2. Structural Characterization: Direct determination of the magnitude of component function $F_b$ through $\dim(V_b)$, establishing direct connections between algebraic structure and spectral properties.
3. Interdisciplinary Application: Skillful application of deep theories from finite geometry concerning vector space partitions and blocking sets.

Experimental Setup

Theoretical Verification Methods

This paper is primarily theoretical research, verified through:

1. Complete Small-Dimensional Analysis:
   • Dimension 6: Verified that all possible vector space partition types correspond to known quadratic APN functions
   • Dimension 8: Determined 18 possible magnitude distributions
   • Dimension 10: Analyzed all theoretically possible cases
2. Known Function Verification:
   • Verification of classical Walsh spectrum functions
   • Analysis of maximum linearity functions
   • Verification of blocking set properties for the $x^3$ function

Computational Tools

The paper used computer-assisted verification to:

• Enumerate all possible vector space partitions in small dimensions
• Verify consistency between theoretical results and known APN functions

Experimental Results

Main Theoretical Results

1. Magnitude Constraints (Theorem 2.10)

Result: Let $n$ be even and $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ be a quadratic APN function with linearity $L(F) = 2^{\frac{n+l}{2}}$ where $l > n/2$. Then:

• $F$ has exactly one component function with magnitude $2^{\frac{n+l}{2}}$
• All other components have magnitude at most $2^{\frac{2n-l}{2}}$
• In particular, any quadratic APN function has at most one component function with magnitude greater than $2^{\frac{3n}{4}}$

2. Upper Bound on Bent Component Functions (Theorem 3.9)

Result: Let $n \geq 6$ be even and $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ be a quadratic APN function. Then: $|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ with equality possible only when $n=8$.

3. Complete Classification for Dimension 8 (Theorem 4.5)

For quadratic APN functions $F: \mathbb{F}_2^8 \to \mathbb{F}_2^8$, the possible magnitude distributions are:

• $[0^{190}, 2^{64}, 6^1]$
• $[0^{238-4i}, 2^{5i}, 4^{17-i}]$, where $1 \leq i \leq 17$

Ablation Analysis

1. Bound Comparison (Proposition 4.4)

Comparison of three different lower bounds for $|N_F|$:

• Vector Space Partition Bound: Strongest when $k < n/2$
• Blocking Set Bound: Strongest when $k = n/2$
• Dimension Bound: Strongest when $k > n/2$

2. Equivalence Analysis

Proved that under EA equivalence:

• Vector space partitions preserve equivalence (Theorem 5.2)
• Blocking sets preserve equivalence (Theorem 5.1)

Important Findings

1. Structural Constraints: The Walsh spectra of quadratic APN functions are subject to strict geometric constraints and are not arbitrary.
2. Dimensional Effects: The number of possible magnitude distributions decreases dramatically as dimension increases.
3. CCZ Equivalence Condition: If a quadratic function is CCZ-equivalent to a permutation, then $|N_F| \geq 3(2^{n/2} - 1)$.

Related Work

Main Research Directions

1. APN Function Classification: Work by Carlet, Charpin, Zinoviev, and others
2. Walsh Spectrum Theory: Fourth moment methods and linearity bounds
3. Vector Space Partitions: Construction theory by Heden, Bu, and others
4. Blocking Set Theory: Optimal bounds by Govaerts-Storme

Advantages of This Paper

• First to establish direct connections between Walsh spectra and geometric objects
• Provides stronger constraints than classical fourth moment methods
• Unifies algebraic and geometric perspectives

Conclusions and Discussion

Main Conclusions

1. The Walsh spectra of quadratic APN functions possess deep geometric structure
2. Vector space partitions and blocking sets provide powerful tools for understanding Walsh spectra
3. Most theoretically possible magnitude distributions cannot be realized in practice

Limitations

1. Constructive Issues: Theory excludes many possibilities but does not provide new construction methods
2. Dimensional Restrictions: Main results focus on even dimensions
3. Computational Complexity: Complete analysis for high dimensions remains difficult

Future Directions

The paper proposes 6 open problems, including:

1. Finding examples of missing magnitude distributions in dimension 8
2. Improving bounds on $|N_F|$
3. Identifying more unrealizable vector space partition types

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Establishes a novel geometric perspective for understanding Walsh spectra
2. Systematic Methodology: Systematically investigates from both vector space partition and blocking set perspectives
3. Profound Results: Obtains multiple first non-trivial bounds
4. Complete Analysis: Exhaustive analysis for small-dimensional cases

Weaknesses

1. Missing Constructions: Primarily exclusionary results, lacking new APN function constructions
2. Computational Verification: Some results rely on computer verification with incomplete theoretical proofs
3. Limited Applications: Primarily theoretical contributions with uncertain practical cryptographic value

Impact

1. Academic Value: Provides new research tools and perspectives for APN function theory
2. Methodological Contribution: Geometric methods may inspire research on other cryptographic problems
3. Open Problems: Proposed problems provide direction for future research

Applicable Scenarios

• Theoretical analysis of quadratic APN functions
• Design and analysis of S-boxes in cryptography
• Application of finite geometry to cryptography
• Structural research on Walsh spectra of Boolean functions

References

The paper cites 25 important references covering multiple fields including APN function theory, vector space partitions, and blocking set theory, reflecting the interdisciplinary nature of the research. Key references include Carlet's monograph on Boolean functions, Govaerts-Storme's work on blocking sets, and Heden et al.'s research on vector space partitions.