On the Walsh spectra of quadratic APN functions
Pith reviewed 2026-05-21 20:13 UTC · model grok-4.3
The pith
The Walsh transform of a quadratic APN function on n=2k bits corresponds uniquely to a vector space partition of F_2^n and a blocking set in PG(n-1,2).
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The Walsh transform of a quadratic APN function F operating on n=2k bits is uniquely associated with a vector space partition of F_2^n and a specific blocking set in the corresponding projective space PG(n-1,2). These connections allow us to prove that F can have at most one component function of amplitude larger than 2^{3n/4}. We also find the first nontrivial upper bound on the number of bent component functions of a quadratic APN function, and provide conditions for a function to be CCZ-equivalent to a permutation based on its number of bent components.
What carries the argument
The unique correspondence that maps the Walsh transform of F to a vector space partition of F_2^n together with a blocking set in PG(n-1,2); this correspondence restricts the distribution of Walsh amplitudes across all components.
If this is right
- At most one component function can have amplitude larger than 2^{3n/4}.
- The number of bent component functions satisfies a nontrivial upper bound derived from the size and structure of the blocking set.
- The exact count of bent components determines whether the function is CCZ-equivalent to a permutation.
Where Pith is reading between the lines
- Enumerating admissible partitions and blocking sets could give a new route to listing quadratic APN functions up to equivalence.
- If analogous partitions exist for higher-degree APN maps, similar amplitude restrictions might carry over.
- The geometric picture may clarify how many bent components are needed to guarantee differential uniformity in related constructions.
Load-bearing premise
The Walsh transform of every quadratic APN function admits a unique correspondence to a vector space partition of F_2^n and a blocking set in PG(n-1,2).
What would settle it
A single quadratic APN function on n=2k bits whose Walsh spectrum contains two or more components each of amplitude larger than 2^{3n/4} would contradict the claimed unique correspondence.
read the original abstract
APN functions play a central role as building blocks in the design of many block ciphers, serving as optimal functions to resist 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. In this paper, we establish two novel connections that allow us to derive strong conditions on the Walsh spectra of quadratic APN functions. We prove that the Walsh transform of a quadratic APN function $F$ operating on $n=2k$ bits is uniquely associated with a vector space partition of $\mathbb{F}_2^n$ and a specific blocking set in the corresponding projective space $PG(n-1,2)$. These connections allow us to prove a variety of results on the Walsh spectrum of $F$. We prove for instance that $F$ can have at most one component function of amplitude larger than $2^{3n/4}$. We also find the first nontrivial upper bound on the number of bent component functions of a quadratic APN function, and provide conditions for a function to be CCZ-equivalent to a permutation based on its number of bent components.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that the Walsh transform of any quadratic APN function F: F_2^n → F_2^n with n = 2k is in unique bijection with a vector space partition of F_2^n together with a specific blocking set in the projective space PG(n-1,2). From these geometric objects the authors derive that F has at most one component function whose Walsh amplitude exceeds 2^{3n/4}, obtain the first nontrivial upper bound on the number of bent component functions, and give CCZ-equivalence criteria phrased in terms of the number of bent components.
Significance. If the stated unique correspondence holds, the work supplies the first systematic geometric dictionary for the Walsh spectra of quadratic APN functions and yields concrete, previously unavailable bounds on spectral amplitudes and bent components. These results are directly relevant to the cryptographic analysis of S-boxes. The manuscript supplies explicit proofs of the association rather than heuristic arguments, which strengthens the contribution.
major comments (2)
- [§3] The uniqueness claim for the association between the Walsh transform and the pair (vector-space partition, blocking set) is the load-bearing premise for every subsequent bound. The argument (appearing after the definition of the blocking set in the main theorem of §3) must explicitly verify that distinct quadratic APN functions cannot produce the same partition/blocking-set pair; the current counting argument does not address the possibility that two different quadratic APN maps share the same hyperplane distribution.
- [Theorem 4.1] The derivation of the amplitude bound “at most one component larger than 2^{3n/4}” (Theorem 4.1) proceeds by counting points outside the blocking set. The estimate uses the fact that the blocking set is of Rédei type, but the paper does not check whether every quadratic APN function produces a blocking set that satisfies the Rédei property; if this fails for even one known family (e.g., the Gold or Kasami APN functions), the bound does not hold in full generality.
minor comments (2)
- [§2] Notation for the Walsh transform W_F(a,b) is introduced without an explicit formula; adding the standard definition (sum over x of (-1)^{<a,x> + <b,F(x)>}) would improve readability.
- [§5] The statement of the CCZ-equivalence criterion in §5 refers to “the number of bent components” without recalling the precise threshold (2^{n/2}) used to declare a component bent; a one-line reminder would prevent ambiguity.
Simulated Author's Rebuttal
We thank the referee for the careful reading, the positive evaluation of the geometric approach, and the specific suggestions that will improve the clarity of the manuscript. We address each major comment below.
read point-by-point responses
-
Referee: [§3] The uniqueness claim for the association between the Walsh transform and the pair (vector-space partition, blocking set) is the load-bearing premise for every subsequent bound. The argument (appearing after the definition of the blocking set in the main theorem of §3) must explicitly verify that distinct quadratic APN functions cannot produce the same partition/blocking-set pair; the current counting argument does not address the possibility that two different quadratic APN maps share the same hyperplane distribution.
Authors: We agree that an explicit injectivity statement strengthens the foundation. The vector-space partition is recovered directly from the level sets of the Walsh transform, and the blocking set is defined by the hyperplanes attaining the maximal amplitude; because the underlying quadratic form is recovered from these data via the APN property, distinct functions cannot induce identical objects. Nevertheless, to remove any ambiguity we will insert a short lemma immediately after the main theorem of §3 that proves: if two quadratic APN maps produce the same partition and the same blocking set, then their Walsh transforms coincide pointwise. This will be accompanied by a one-paragraph explanation why the existing counting argument already precludes shared hyperplane distributions. revision: yes
-
Referee: [Theorem 4.1] The derivation of the amplitude bound “at most one component larger than 2^{3n/4}” (Theorem 4.1) proceeds by counting points outside the blocking set. The estimate uses the fact that the blocking set is of Rédei type, but the paper does not check whether every quadratic APN function produces a blocking set that satisfies the Rédei property; if this fails for even one known family (e.g., the Gold or Kasami APN functions), the bound does not hold in full generality.
Authors: The proof in §3 already establishes that the blocking set arising from any quadratic APN function is of Rédei type: the quadratic character forces every line in PG(n-1,2) to intersect the set in either one or two points (the precise Rédei condition in characteristic 2). This argument is independent of the particular family and therefore applies to Gold, Kasami, and all other known quadratic APN maps. To make the applicability transparent we will add a short remark after Theorem 4.1 that recalls the Rédei property for the two standard families and notes that the general proof covers them. revision: partial
Circularity Check
No significant circularity: derivation proceeds from definitions via proved combinatorial correspondence.
full rationale
The paper states it proves the unique association between the Walsh transform of quadratic APN functions and vector space partitions/blocking sets in PG(n-1,2) directly from the APN property and finite geometry definitions. Subsequent bounds (at most one large-amplitude component, bound on bent components) are then derived as consequences of that proved correspondence. No step reduces a claimed result to a fitted parameter, self-citation chain, or input by construction; the central mapping is presented as a theorem established in the paper rather than presupposed or renamed from prior results. This is a standard self-contained combinatorial argument.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Standard algebraic properties of APN functions and their Walsh transforms over F_2^n.
- standard math Existence and basic incidence properties of vector space partitions and blocking sets in PG(n-1,2).
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We prove that the Walsh transform of a quadratic APN function F operating on n=2k bits is uniquely associated with a vector space partition of F_2^n and a specific blocking set in the corresponding projective space PG(n-1,2).
-
IndisputableMonolith/Foundation/AlexanderDuality.leanalexander_duality_circle_linking unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 2.4. ... F_b has amplitude 2^{n+dim(Vb)/2}.
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Christof Beierle and Gregor Leander,New instances of quadratic APN functions, IEEE Transactions on Information Theory68(2021), no. 1, 670–678. (Cited on page 14.)
work page 2021
-
[2]
ChristofBeierle, GregorLeander, and L´ eoPerrin,Trims and extensions of quadratic APN functions, Designs, Codes and Cryptography90(2022), no. 4, 1009–1036. (Cited on page 6.)
work page 2022
- [3]
- [4]
-
[5]
Claude Carlet,Boolean and vectorial plateaued functions and APN functions, IEEE Transactions on Information Theory61(2015), no. 11, 6272–6289. (Cited on page 2.)
work page 2015
-
[6]
,Boolean functions for cryptography and coding theory, Cambridge University Press, 2021. (Cited on pages 2 and 6.)
work page 2021
-
[7]
Claude Carlet, Pascale Charpin, and Victor Zinoviev,Codes, bent functions and permutations suit- able for DES-like cryptosystems, Designs, Codes and Cryptography15(1998), no. 2, 125–156. (Cited on page 2.)
work page 1998
-
[8]
44, Springer Science & Business Media, 1968
Peter Dembowski,Finite geometries, vol. 44, Springer Science & Business Media, 1968. (Cited on page 8.)
work page 1968
-
[9]
Saad El-Zanati, Olof Heden, George Seelinger, Papa Sissokho, Lawrence Spence, and C Vanden Eynden,Partitions of the 8-dimensional vector space over GF(2), Journal of Combinatorial Designs 18(2010), no. 6, 462–474. (Cited on page 8.)
work page 2010
-
[10]
Faruk G¨ olo˘ glu and Philippe Langevin,Almost perfect nonlinear families which are not equivalent to permutations, Finite Fields and Their Applications67(2020), 101707. (Cited on page 12.)
work page 2020
-
[11]
Faruk G¨ olo˘ glu and Jiˇ r´ ı Pavlu,On CCZ-inequivalence of some families of almost perfect nonlinear functions to permutations, Cryptography and Communications13(2021), no. 3, 377–391. (Cited on pages 12 and 15.)
work page 2021
-
[12]
Patrick Govaerts and Leo Storme,The classification of the smallest nontrivial blocking sets in PG (n, 2), Journal of Combinatorial Theory, Series A113(2006), no. 7, 1543–1548. (Cited on pages 11 and 16.)
work page 2006
-
[13]
Olof Heden,On the length of the tail of a vector space partition, Discrete Mathematics309(2009), no. 21, 6169–6180. (Cited on page 7.)
work page 2009
-
[14]
,A survey of the different types of vector space partitions, Discrete Mathematics, Algorithms and Applications4(2012), no. 01, 1250001. (Cited on pages 6 and 8.)
work page 2012
-
[15]
Olof Heden, Juliane Lehmann, Esmeralda N˘ astase, and Papa Sissokho,Extremal sizes of subspace partitions, Designs, Codes and Cryptography64(2012), no. 3, 265–274. (Cited on page 7.)
work page 2012
-
[16]
Lukas K¨ olsch and Alexandr Polujan,The combinatorial structure and value distributions of plateaued functions, arXiv preprint arXiv:2410.00611 (2024). (Cited on page 11.)
-
[17]
Sascha Kurz,Heden’s bound on the tail of a vector space partition, Discrete Mathematics (2018), 3447–3452. (Cited on pages 7 and 8.)
work page 2018
-
[18]
Gohar M Kyureghyan,Crooked maps inF2n, Finite Fields and their applications13(2007), no. 3, 713–726. (Cited on pages 3, 4, and 12.)
work page 2007
-
[19]
Juliane Lehmann and Olof Heden,Some necessary conditions for vector space partitions, Discrete mathematics312(2012), no. 2, 351–361. (Cited on pages 7 and 8.)
work page 2012
-
[20]
Sihem Mesnager, Fengrong Zhang, Chunming Tang, and Yong Zhou,Further study on the maximum number of bent components of vectorial functions, Designs, Codes and Cryptography87(2019), no. 11, 2597–2610. (Cited on page 11.)
work page 2019
-
[21]
Alexander Pott,Almost perfect and planar functions, Designs, Codes and Cryptography78(2016), no. 1, 141–195. (Cited on page 8.) 17
work page 2016
-
[22]
Alexander Pott, Enes Pasalic, Amela Muratovi´ c-Ribi´ c, and Samed Bajri´ c,On the maximum number of bent components of vectorial functions, IEEE Transactions on Information Theory64(2017), no. 1, 403–411. (Cited on pages 10 and 11.)
work page 2017
-
[23]
G. Seelinger, P. Sissokho, L. Spence, and C. Vanden Eynden,Partitions of finite vector spaces over GF(2) into subspaces of dimensions 2 and s, Finite Fields and Their Applications18(2012), no. 6, 1114–1132. (Cited on page 9.)
work page 2012
- [24]
-
[25]
Lijing Zheng, Jie Peng, Haibin Kan, Yanjun Li, and Juan Luo,On constructions and properties of (n, m)-functions with maximal number of bent components, Designs, Codes and Cryptography88 (2020), no. 10, 2171–2186. (Cited on page 11.) 18
work page 2020
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.