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

Computer Science > Cryptography and Security [Submitted on 10 Jun 2026] Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace Oleksandr Kuznetsov We describe a computational search for quadratic APN (Almost Perfect Nonlinear) functions in dimension 8 within a structured self-equivalence subspace. The search space is a 40-dimensional binary linear subspace consisting of all functions commuting with a linear automorphism of order 5 (class 22 in the taxonomy of Beierle, Brinkmann, and Leander, 2021), previously reported to contain no APN functions. Our approach combines random sampling via an explicit RREF parameterization (approximately 600 fresh APN-positive evaluations per core-hour) with Gröbner basis computation in Magma to enumerate all APN functions in a 24-dimensional hyperplane through each center (approximately 10 minutes per hyperplane). From 428 hyperplane computations, covering 0.65% of all 65,536 hyperplanes, we obtained 566 quadratic APN functions forming six CCZ-equivalence classes under the ortho-derivative invariant. Four classes, comprising 500 functions, match no entry in the 2025 database of 3,775,599 quadratic APN functions or in the pre-2020 compilation of 12,921 instances. Two classes (66 functions) are CCZ-equivalent to the Gold functions x^3 and x^9, confirming the correctness of the search pipeline. A membership analysis shows that the three new classes (B, C, D) lie entirely outside the original subspace and occur only in Gold-centered slices, demonstrating the essential role of the Gröbner basis stage. In 532 experiments using database functions as slice centers and 20 experiments with random centers, no APN neighbors were found, indicating that the gateway phenomenon is specific to the self-equivalence structure of the search space. Since the ortho-derivative invariant is a complete CCZ-invariant for quadratic APN functions, the absence of matching signatures provides a rigorous proof of CCZ-inequivalence. Subjects: Cryptography and Security (cs.CR); Information Theory (cs.IT); Combinatorics (math.CO) Cite as: arXiv:2606.11967 [cs.CR]   (or arXiv:2606.11967v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.11967 Focus to learn more Submission history From: Oleksandr Kuznetsov [view email] [v1] Wed, 10 Jun 2026 11:45:12 UTC (31 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.IT math math.CO math.IT References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)