Paper 2026/2799

Exploring the Set of APN Functions

Jules Baudrin, Versailles Saint-Quentin-en-Yvelines University
Pierre Galissant, French Institute for Research in Computer Science and Automation
Léo Perrin, French Institute for Research in Computer Science and Automation
Abstract

An Almost Perfect Nonlinear (APN) function $F : \mathbb{F}_2^n \to \mathbb{F}_2^n$ provides optimal protection against differential attacks, meaning that the equation $F(x+a)=F(x)+b$ has at most 2 solutions~$x$ when $a \neq 0$. Setting aside some sporadic examples, such functions are hard to find in practice, and whether there exists APN bijections of $ \mathbb{F}_2^n$ when $n > 6$ is even (the Big APN Problem) is still unknown. In this paper, we provide the tools needed to explore the complete set of known APN functions. Indeed, for a given APN function $F$, we in fact know many: all functions CCZ-equivalent to $F$ are also APN, and so are its switching neighbours. These notions have been in the literature for many years, but several unknowns remain that complicate the exploration of the corresponding functions in practice: a given function has too many switching neighbours, and the algorithms that are known to iterate through a CCZ-equivalence class return multiple representatives per extended-affine (EA) equivalence class. We solve both problems. First, we show how to partition precisely the CCZ-equivalence class of a quadratic APN function in practice, and thus obtain exactly one representative per EA-equivalence class. To achieve this, we carefully investigate the set of the automorphisms of the graph of a quadratic APN function, and show how to generate them very efficiently using the ortho-derivative. Second, we provide the first detailed investigation of the set of the switching neighbours of a function, show in particular how an overwhelming majority of them are trivial, and explain how to get rid of those. Incidentally, we build a new extended-affine equivalence class invariant using the resulting set of non-trivial switching neighbours. For both theoretical contributions, we pushed highly-efficient and easy to re-use implementations of the corresponding algorithms to the sboxU library. It allowed us to generate databases containing all known APN functions for $n=6$ and $n=7$. For $n=8$, our algorithms are efficient-enough that we can investigate the properties of the millions of quadratic APN function recently exhibited. In the process, we generate a few thousands of new CCZ-equivalence classes. In the light of our work, the successes of the exploration strategies for $n=6$ (i.e. finding an APN function inequivalent to any monomial and quadratic mapping, and finding an APN bijection in even dimension) seems to be an artifact due to the small dimension that we show not to work for dimension 8 and which we do not expect to work either when the dimension is greater.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
APN FunctionsBoolean FunctionsCCZ EquivalenceSwitching NeighboursDataset
Contact author(s)
jules baudrin @ uvsq fr
pierre galissant @ inria fr
leo perrin @ inria fr
History
2026-11-09: approved
2026-11-06: received
See all versions
Short URL
https://ia.cr/2026/2799
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2799,
      author = {Jules Baudrin and Pierre Galissant and Léo Perrin},
      title = {Exploring the Set of {APN} Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2799},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2799}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.