Pith. sign in

REVIEW 3 minor 25 references

Quadratic APN Functions in Dimension 8 via Gr\"obner Basis Search in a Self-Equivalence Subspace

T0 review · 0 major / 3 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A search restricted to the 40-dimensional space of functions commuting with a fixed order-5 linear map yields four new CCZ-inequivalent quadratic APN classes over F_{2^8}.

desk verdict Four new CCZ classes of quadratic APN functions in dimension 8, found via Groebner enumeration in a 40-dimensional self-equivalence subspace that prior searches missed, with public code and database verification. read the letter →

arxiv 2606.11967 v2 pith:QQOXOJEX submitted 2026-06-10 cs.CR cs.ITmath.COmath.IT

Oleksandr Kuznetsov This is my paper · ORCID
classification cs.CRcs.ITmath.COmath.IT
keywords quadraticAPNfunctionsCCZ-equivalenceself-equivalencesubspaceGröbnerbasisdimension8ortho-derivativeinvariantfinitefieldscryptography
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper restricts attention to the 40-dimensional F_2-linear space V_A of quadratic functions over F_{2^8} that commute with a chosen linear automorphism A of order 5. Inside this space it samples center functions by random search and then uses Gröbner-basis computations to enumerate all APN functions lying in selected 24-dimensional hyperplanes. The resulting 566 functions fall into six CCZ classes; four of those classes (500 functions) produce an ortho-derivative signature absent from two large prior compilations. For quadratic APN functions, Yoshiara's theorem equates CCZ and EA equivalence, so the signature mismatch constitutes a proof that the four classes are new.

What carries the argument

The 40-dimensional self-equivalence subspace V_A = {F : F ∘ A = A ∘ F} for a fixed linear A of order 5, combined with the ortho-derivative invariant to certify CCZ-inequivalence.

What would settle it

Finding even one quadratic APN function belonging to one of the four reported classes whose ortho-derivative signature matches an entry already present in the Beierle et al. database or the pre-2020 compilation.

Watch

Extended reading notes

Core claim

Restricting to the self-equivalence subspace V_A of dimension 40 and enumerating APN members of 428 hyperplanes via Gröbner bases produces 566 quadratic APN functions in six CCZ classes; four classes containing 500 functions are absent from the Beierle et al. 2025 database of 3 775 599 quadratic APN functions and from the pre-2020 list of 12 921 instances, thereby proving CCZ-inequivalence by Yoshiara's theorem together with the ortho-derivative invariant.

Load-bearing premise

That the absence of a match against the cited databases, when the ortho-derivative invariant is used, rigorously establishes that the four classes are CCZ-inequivalent to every previously known quadratic APN function.

Editorial extensions

If this is right

  • Four new CCZ-inequivalence classes of quadratic APN functions in dimension 8 are obtained.
  • The method recovers the known Gold functions x^3 and x^9, confirming that the search pipeline works.
  • A signature mismatch with the ortho-derivative invariant supplies a rigorous certificate of CCZ-inequivalence for any quadratic APN function.
  • The 500 functions in the new classes enlarge the known pool of quadratic APN examples in dimension 8.
  • All data, code, and verification scripts are released for independent checking.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same subspace-search technique could be applied to other linear automorphisms to locate still more new classes.
  • The newly found functions may serve as building blocks for S-boxes with improved differential uniformity in cryptographic designs.
  • Extending the hyperplane enumeration to additional subspaces might reveal whether the total number of quadratic APN classes in dimension 8 is finite or still growing.
  • Combining the ortho-derivative invariant with further invariants could produce a complete classification of quadratic APN functions up to dimension 8.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The manuscript describes a two-phase computational search for quadratic APN functions over F_{2^8} inside the 40-dimensional self-equivalence subspace V_A = {F : F ∘ A = A ∘ F} for a fixed linear A of order 5. Phase 1 uses explicit RREF sampling to locate APN centers; phase 2 applies Gröbner-basis enumeration in Magma over 24-dimensional hyperplanes through each center. From 428 hyperplanes (0.65 % of the 65 536 total), 566 quadratic APN functions are obtained and partitioned into six CCZ-classes via the ortho-derivative invariant. Four classes (500 functions) have signatures absent from the Beierle et al. 2025 database (3 775 599 entries) and the pre-2020 compilation (12 921 entries); by Yoshiara’s theorem these are therefore new CCZ-inequivalence classes. The remaining two classes recover the Gold functions x^3 and x^9, confirming correctness of the pipeline. All code, data and verification scripts are public.

Significance. If the enumeration and database-comparison claims hold, the work adds four new CCZ-inequivalence classes of quadratic APN functions in dimension 8, a concrete advance in the classification problem that is directly relevant to the design of optimal cryptographic S-boxes. The self-equivalence subspace restriction together with the hybrid sampling-plus-Gröbner strategy is a novel and reproducible method that succeeded where an earlier recursive tree search on the same subspace reported none. Public release of the complete dataset, Magma scripts and verification code constitutes a strong reproducibility asset.

minor comments (3)
  1. [Abstract] Abstract: the figure 65 536 for the total number of hyperplanes in the 40-dimensional F_2-space V_A is stated without derivation; a one-sentence parenthetical (e.g., 2^{16} because each hyperplane is a codimension-16 affine subspace) would aid readers.
  2. [Abstract] Abstract: the phrase “class index 22 in the taxonomy of Beierle, Brinkmann, and Leander” should be accompanied by the precise bibliographic entry in the reference list.
  3. The manuscript repeatedly uses the abbreviation “CCZ” without an initial expansion; while standard in the field, a parenthetical on first use improves accessibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of the manuscript, for highlighting its significance in advancing the classification of quadratic APN functions, and for the recommendation to accept. The recognition of the novel search strategy, the rigorous use of the ortho-derivative invariant together with Yoshiara’s theorem, and the value of the public dataset is appreciated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper's derivation consists of explicit RREF parameterization of the 40-dimensional subspace V_A, random sampling to locate APN centers, Gröbner basis enumeration over 428 hyperplanes, and direct comparison of ortho-derivative signatures against two external databases (Beierle et al. 2025 with 3,775,599 entries and the pre-2020 compilation of 12,921 instances). CCZ-inequivalence follows from signature mismatch via the external Yoshiara theorem (CCZ=EA for quadratic APN) and the EA-invariant property of the ortho-derivative. The pipeline is validated by recovering the known Gold functions x^3 and x^9. No equations define a quantity in terms of itself, no fitted parameters are relabeled as predictions, and no load-bearing step reduces to a self-citation chain or author-specific uniqueness theorem. The central claim is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The work rests on standard results from finite-field algebra and prior theorems on APN equivalence; no new free parameters, ad-hoc axioms, or postulated entities are introduced.

assumptions (1)
  • domain assumption Yoshiara's theorem that CCZ-equivalence coincides with EA-equivalence for quadratic APN functions
    Invoked to conclude that an ortho-derivative signature mismatch with existing databases proves the four classes are new.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quadratic APN Functions in Dimension 8 via Gr\"obner Basis Search in a Self-Equivalence Subspace." pith.science (2026). https://pith.science/paper/QQOXOJEX

@misc{pith2026260611967,
  author       = {Pith},
  title        = {Pith review of: Quadratic APN Functions in Dimension 8 via Gr\"obner Basis Search in a Self-Equivalence Subspace},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QQOXOJEX}},
  note         = {Machine review of arXiv:2606.11967}
}
abstract

We describe a computational search for quadratic APN (Almost Perfect Nonlinear) functions over $\mathbb{F}_{2^8}$ within a structured algebraic subspace defined by a self-equivalence constraint. The search space is the 40-dimensional $\mathbb{F}_2$-linear subspace $V_A = \{F : F \circ A = A \circ F\}$ for a specific linear automorphism $A$ of order 5 (class index 22 in the taxonomy of Beierle, Brinkmann, and Leander); this subspace was previously reported to contain no APN functions under their recursive tree search method. We combine two phases: (1) random sampling inside $V_A$ via an explicit RREF parameterization to find APN center functions, and (2) Groebner basis computation in Magma over the Boolean polynomial ring to enumerate all APN functions in a 24-dimensional hyperplane through each center. From 428 hyperplane computations (covering 0.65% of the 65,536 total hyperplanes in $V_A$) we obtained 566 quadratic APN functions falling into six CCZ-equivalence classes under the ortho-derivative invariant. Four of these classes, comprising 500 functions, match no entry in the Beierle et al. 2025 database of 3,775,599 quadratic APN functions and no entry in the pre-2020 compilation of 12,921 instances. Two classes (66 functions) are identified as CCZ-equivalents of the Gold functions x^3 and x^9, confirming pipeline correctness. For quadratic APN functions, a signature mismatch rigorously certifies CCZ-inequivalence, by Yoshiara's theorem (CCZ = EA for quadratic APN) together with the ortho-derivative invariant; the absence of a signature match in the above databases therefore constitutes a rigorous proof of CCZ-inequivalence for the new classes. The complete dataset, source code, and verification scripts are publicly available.

Figures

Figures reproduced from arXiv: 2606.11967 by the authors.

Figure 1
Figure 1. Overview of the five-stage search pipeline. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. CCZ-class landscape in and around VA. Blue region: functions inside VA (IN CLASS22). Dashed boxes: functions found by the Grobner basis ¨ step, lying outside VA (OUT CLASS22). Arrows show which classes co-occur in each NL=4 slice. CLASS-A centered slices yield only CLASS-A. Each Gold-x 3 slice yields one CLASS-E center plus two CLASS-B and one CLASS-C neighbor. Each Gold-x 9 slice yields one CLASS-F center plus one … view at source ↗
Figure 3
Figure 3. The GB-navigation mechanism. A structured subspace [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 20 canonical work pages

  1. [1]

    Differentially uniform mappings for cryptography,

    K. Nyberg, “Differentially uniform mappings for cryptography,” inAdvances in Cryptology — EUROCRYPT 1993, Lecture Notes in Comput. Sci., vol. 765, Springer, 1994, pp. 55–64. doi:10.1007/3-540-48285-7 6

    work page doi:10.1007/3-540-48285-7 1993

  2. [2]

    Differential cryptanalysis of DES-like cryptosystems,

    E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,”J. Cryptology, vol. 4, no. 1, pp. 3–72, 1991. doi:10.1007/BF00630563

    work page doi:10.1007/bf00630563 1991

  3. [3]

    Codes, bent functions and permutations suitable for DES-like cryptosystems,

    C. Carlet, P. Charpin, and V . Zinoviev, “Codes, bent functions and permutations suitable for DES-like cryptosystems,”Des. Codes Cryptogr., vol. 15, pp. 125–156, 1998. doi:10.1023/A:1008344232130

    work page doi:10.1023/a:1008344232130 1998

  4. [4]

    Maximal recursive sequences with 3-valued recursive cross-correlation functions,

    R. Gold, “Maximal recursive sequences with 3-valued recursive cross-correlation functions,”IEEE Trans. Inf. Theory, vol. 14, no. 1, pp. 154–156, 1968. doi:10.1109/TIT.1968.1054106

    work page doi:10.1109/tit.1968.1054106 1968

  5. [5]

    The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes,

    T. Kasami, “The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes,”Inf. Control, vol. 18, no. 4, pp. 369–394, 1971. doi:10.1016/S0019-9958(71)90473-6

    work page doi:10.1016/s0019-9958(71)90473-6 1971

  6. [6]

    A new almost perfect nonlinear function which is not quadratic,

    Y . Edel and A. Pott, “A new almost perfect nonlinear function which is not quadratic,”Adv. Math. Commun., vol. 3, no. 1, pp. 59–81, 2009. doi:10.3934/amc.2009.3.59

    work page doi:10.3934/amc.2009.3.59 2009

  7. [7]

    A matrix approach for constructing quadratic APN functions,

    Y . Yu, M. Wang, and Y . Li, “A matrix approach for constructing quadratic APN functions,”Des. Codes Cryptogr., vol. 73, pp. 587–600, 2014. doi:10.1007/s10623-014-9955-3 ePrint: https://eprint.iacr.org/2013/007

    work page doi:10.1007/s10623-014-9955-3 2014

  8. [8]

    On quadratic almost perfect nonlinear functions and their related algebraic object,

    G. Weng, Y . Tan, and G. Gong, “On quadratic almost perfect nonlinear functions and their related algebraic object,” inProc. Workshop on Coding and Cryptography (WCC 2013), Bergen, Norway, 2013

    2013

Show all 25 references
  1. [9]

    On quadratic almost perfect nonlinear functions and their related algebraic object,

    G. Weng, Y . Tan, and G. Gong, “On quadratic almost perfect nonlinear functions and their related algebraic object,” inProceedings of the Workshop on Coding and Cryptography (WCC 2013), Bergen, Norway, pp. 48–57, 2013

    2013

  2. [10]

    On some quadratic APN functions,

    H. Taniguchi, “On some quadratic APN functions,”Des. Codes Cryptogr., vol. 87, no. 9, pp. 1973–1983, 2019. doi:10.1007/s10623-018-00598-2

    1973 doi

  3. [11]

    Linearly self-equivalent APN permutations in small dimension,

    C. Beierle, M. Brinkmann, and G. Leander, “Linearly self-equivalent APN permutations in small dimension,”IEEE Trans. Inf. Theory, vol. 67, no. 7, pp. 4863–4875, Jul. 2021. doi:10.1109/TIT.2021.3071533 arXiv: https://arxiv.org/abs/2003.12006

    2021 doi

  4. [12]

    New instances of quadratic APN functions,

    C. Beierle and G. Leander, “New instances of quadratic APN functions,”IEEE Trans. Inf. Theory, vol. 68, no. 1, pp. 670–678, Jan. 2022. doi:10.1109/TIT.2021.3120698 arXiv: https://arxiv.org/abs/2009.07204 Dataset (Zenodo): doi:10.5281/zenodo.4738942 IEEE TRANSACTIONS ON INFORMA...

    2022 doi

  5. [13]

    Trims and extensions of quadratic APN functions,

    C. Beierle, G. Leander, and L. Perrin, “Trims and extensions of quadratic APN functions,”Des. Codes Cryptogr., vol. 90, no. 4, pp. 1009–1036, 2022. doi:10.1007/s10623-022-01024-4 arXiv: https://arxiv.org/abs/2108.13280

    2022 doi

  6. [14]

    Millions of inequivalent quadratic APN functions in eight variables,

    C. Beierle, P. Langevin, G. Leander, A. Polujan, and S. Rasoolzadeh, “Millions of inequivalent quadratic APN functions in eight variables,” arXiv:2508.04644, 2025. Dataset (Zenodo): doi:10.5281/zenodo.16752428 arXiv: https://arxiv.org/abs/2508.04644

    2025 doi

  7. [15]

    Recovering or testing extended-affine equivalence,

    A. Canteaut, A. Couvreur, and L. Perrin, “Recovering or testing extended-affine equivalence,”IEEE Trans. Inf. Theory, vol. 68, no. 9, pp. 6187–6206, Sep. 2022. doi:10.1109/TIT.2022.3166692 arXiv: https://arxiv.org/abs/2103.00078

    2022 doi

  8. [16]

    Equivalences of quadratic APN functions,

    S. Yoshiara, “Equivalences of quadratic APN functions,”J. Algebraic Combin., vol. 35, no. 3, pp. 461–475, 2012. doi:10.1007/s10801-011-0309-1

    2012 doi

  9. [17]

    Equivalences of power APN functions with power or quadratic APN functions,

    S. Yoshiara, “Equivalences of power APN functions with power or quadratic APN functions,”J. Algebraic Combin., vol. 44, no. 3, pp. 561–585, 2016. doi:10.1007/s10801-016-0680-z

    2016 doi

  10. [18]

    Constructing APN functions through isotopic shifts,

    L. Budaghyan, M. Calderini, C. Carlet, R. S. Coulter, and I. Villa, “Constructing APN functions through isotopic shifts,”IEEE Trans. Inf. Theory, vol. 66, no. 8, pp. 5299–5309, 2020. doi:10.1109/TIT.2020.2974471

    2020 doi

  11. [19]

    On the EA-classes of known APN functions in small dimensions,

    M. Calderini, “On the EA-classes of known APN functions in small dimensions,”Cryptogr. Commun., vol. 12, pp. 821–840, 2020. doi:10.1007/s12095- 020-00427-1

    2020 doi

  12. [20]

    Carlet,Boolean Functions for Cryptography and Coding Theory

    C. Carlet,Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, 2021. doi:10.1017/9781108606806

    2021 doi

  13. [21]

    The Magma algebra system I: The user language,

    W. Bosma, J. Cannon, and C. Playoust, “The Magma algebra system I: The user language,”J. Symb. Comput., vol. 24, pp. 235–265, 1997. doi:10.1006/jsco.1996.0125

    1997 doi

  14. [22]

    sboxU: Tools for analysing S-boxes,

    L. Perrin, “sboxU: Tools for analysing S-boxes,” https://github.com/lpp-crypto/sboxU, 2022

    2022

  15. [23]

    An APN permutation in dimension six,

    K. Browning, J. Dillon, M. McQuistan, and A. Wolfe, “An APN permutation in dimension six,” inFinite Fields: Theory and Applications (FQ9), Contemp. Math., vol. 518, Amer. Math. Soc., 2010, pp. 33–42. https://www.ams.org/books/conm/518/

    2010

  16. [24]

    Cryptanalysis of block ciphers with overdefined systems of equations,

    N. Courtois and J. Pieprzyk, “Cryptanalysis of block ciphers with overdefined systems of equations,” inAdvances in Cryptology — ASIACRYPT 2002, Lecture Notes in Comput. Sci., vol. 2501, Springer, 2002, pp. 267–287. doi:10.1007/3-540-36178-2 17

    2002 doi

  17. [25]

    The M4RI library,

    M. R. Albrecht and G. V . Bard, “The M4RI library,” 2010. https://github.com/malb/m4ri

    2010

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.