WorksComputer Science
Quadratic APN Functions of with a Self-Equivalence of Prime Order
Abstract
Almost perfect nonlinear (APN) functions of have the lowest possible differential uniformity. The only known APN permutation in even dimension, in dimension six, is equivalent to a quadratic APN function with a nontrivial linear self-equivalence; no APN permutation is known for even . In a published collection of about 3.8 million quadratic APN classes of dimension eight, at most 0.34% have a nontrivial linear self-equivalence. In dimension ten, the 25 literature classes considered here all have one. We study all quadratic APN functions of with such a self-equivalence, which usually confines them to a much smaller linear space. Up to conjugacy and power similarity, self-equivalences of prime order have 299 types. We settle 298 of them. Elementary lemmas exclude 280 types, and exhaustive searches confirm this for 242 of them. The other 18 types are settled by exhaustive searches with exact equivalence certificates. Up to extended affine equivalence, the 298 types contain 29 classes of quadratic APN functions, four of them new. This also classifies the quadratic APN functions with coefficients in a subfield. Exactly 24 classes contain one with coefficients in , and all 3 that contain one with coefficients in are among them. The open type consists of the quadratic canonical triplicate functions. They correspond to maximum additive Hermitian rank-distance codes. Three different searches find only the invariants of 16 classes, all among the 29. We conjecture there are no others. No quadratic APN function in the 298 settled types is Carlet-Charpin-Zinoviev equivalent to a permutation.
Introduction
function is almost perfect nonlinear (APN) if the equation has at most two solutions for every and every [1]. So an APN function has the lowest possible differential uniformity. For an S-box, this is the best possible property against differential cryptanalysis [1]. APN permutations in odd dimension are used in practice, for example in the S-boxes of MISTY1 [2]. APN functions are also linked to many objects in coding theory and finite geometry [3]. Most known APN functions are quadratic, that is, of algebraic degree two.
APN functions are classified up to CCZ-equivalence [4]. For quadratic APN functions, CCZ-equivalence is the same as extended affine (EA) equivalence [5]. In dimension all APN functions are known, and in dimension six all quadratic ones are known. In dimension eight, searches have found millions of quadratic APN classes [6, 7, 8]. Of the 3,808,491 classes listed in [8] (arXiv version 2), only 12,775 have an automorphism group larger than the translation group [8], Table 5.2. By Section II, the others have no nontrivial linear self-equivalence. So at most 12,775 of them, that is, at most 0.34%, have a nontrivial linear self-equivalence. Dimension ten is different. Only 25 classes of quadratic APN functions of are known from published instances [6, 9, 10, 11], as collected in [12]. When we say “published classes”, we mean these 25. They all have algebraic structure: they are power functions, members of infinite families, or functions with a nontrivial self-equivalence.
Our starting point is an observation. Each of the 25 known classes has a linear self-equivalence of prime order (Section VIII). A linear self-equivalence of is a pair of invertible linear maps such that and differ by an affine map. Beierle and Leander [6] used such self-equivalences to find new quadratic APN functions in dimensions nine and ten. They listed the possible types of prime-order self-equivalences and searched them, but not exhaustively. In this paper we make their approach exhaustive in dimension ten.
E. Bellini is with the Technology Innovation Institute, Abu Dhabi, United Arab Emirates (e-mail: [email protected]).
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.
| Known quadratic APN classes | millions | 25 (29 with this paper) |
| Random search finds new classes | yes | rarely |
| Classes with a self-equivalence of prime order | at most 12,775 of 3,808,491 (0.34%) in [8] | all known ones |
| Where the known classes come from | large computational searches and constructions | power functions, infinite families, self-equivalences |
| Classes CCZ-equivalent to a permutation | none [6, 8] | none; three pass the counting criterion but fail the projection test [12] |
| Analogy with Dillon’s permutation () | , as |
Table 1. Quadratic APN functions in dimensions eight and ten: two opposite situations.
Why dimension ten
The big APN problem asks whether there is an APN permutation of for some even . The only known example in even dimension lives in dimension six [13]. It is CCZ-equivalent to a quadratic APN function with many self-equivalences. We ask whether a similar quadratic function exists in dimension eight or ten. Table I compares the two dimensions. In dimension eight, millions of quadratic APN classes are known. None of them is CCZ-equivalent to a permutation [6, 8]. In dimension ten, randomized searches have found few classes [6]. The known classes are structured, and all of them have a nontrivial self-equivalence. So we classify the quadratic APN functions of dimension ten by their self-equivalences. Dimension ten is also the next case after six with (mod 4).
Contributions
Let be the polar form of a quadratic function . A pair of invertible linear maps is a self-equivalence of if and only if for all . Every nontrivial self-equivalence has a power of prime order. Up to conjugacy and power similarity there are 299 types of prime-order pairs in dimension ten (Section III). Our main result is the following.
Theorem 1 (computer-assisted). Let be a quadratic APN function of with a linear self-equivalence of prime order. Suppose that has such a self-equivalence of a type other than type 64. Then is EA-equivalent to one of 29 functions. They are the 25 published classes and four new ones. Each of the 29 classes occurs in at least one type other than type 64.
Figure 1 gives an overview of the classification.

Figure 1. Overview of the classification. The core-hours cover the classification and confirmation searches, including the confirmation searches on 242 types that are also excluded by proof (§ 5).
Proofs. We give elementary lemmas on the polar form (§ 4). They show that 280 types contain no APN function. A bound of Baudrin et al. [14] gives a partial cross-check.
Exhaustive searches. The other 18 types are settled by exhaustive searches (§ 5 and VI). Two of them, types 24 and 47, need a dedicated method. We also ran the generic search exhaustively on 242 of the 280 excluded types, and it agrees with the proofs. These searches are validated on cases with a known answer. Every function they find is matched to a known class by an explicit equivalence certificate.
One open type. Type 64 consists of the quadratic canonical triplicate functions [10]. We show that they correspond to maximum additive Hermitian rank-distance codes (Section VII). Three exploratory searches find only functions with the fingerprint, an EA-invariant, of one of 16 classes, all among the 29. Unlike the searches that settle the other 298 types, these three searches are not exhaustive on type 64, and they do not certify equivalences. We conjecture that there are no others. If the conjecture holds, the quadratic APN functions of with a nontrivial linear self-equivalence are exactly the 29 classes.
Two special cases are of independent interest. Type 73 is the set of quadratic functions of with coefficients in . Ichanska et al. considered an exhaustive search of this set infeasible [7]. We find exactly 24 APN classes in it, four of them new (Theorem 10). Type 24 is the set of quadratic functions with coefficients in . In dimension six, the analogous set contains a function CCZ-equivalent to Dillon’s permutation. It contains only three APN classes (Theorem 15). The proper subfields of are , and . So these two cases classify the quadratic APN functions of with coefficients in any proper subfield. For we find the three classes of Yu et al. [15].
None of the 29 classes is CCZ-equivalent to a permutation. For the 25 published classes this was known [6], [10], [12], and we check it for the four new ones. So, within the reach of this classification, there is no quadratic route to an APN permutation of .
Related work
Beierle and Leander introduced the search by self-equivalence types [6]. Baudrin, Canteaut and Perrin describe the linear self-equivalences of the known APN families [16]. Baudrin et al. prove a general bound on the fixed spaces of a self-equivalence of a differentially uniform function [14]. Beierle, Brinkmann and Leander study the self-equivalences of APN permutations [17]. Gölöǧlu and Kölsch determine the equivalences between bijective APN functions [18]. Dempwolff and Edel study the automorphisms of extensions of quadratic APN functions and of dimensional dual hyperovals. Their methods rely on elementary abelian 2-subgroups of the automorphism group [19]. Budaghyan, Ivkovic and Kaleyski introduced triplicate functions [10]. Ichanska et al. search quadratic functions with coefficients in subfields [7]. Yu et al. classify the quadratic APN functions of with coefficients in [15]. Helleseth, Ichanska and Kaleyski give new infinite families in even dimension [11]. Our tools for equivalence follow Canteaut, Couvreur and Perrin [20].
Organization
Section II recalls the background. Section III lists the 299 types. Section IV gives the lemmas that exclude types by proof. Section V describes the generic exhaustive search and the equivalence test. Section VI treats the types that need a dedicated method. Section VII studies the open type 64. Section VIII collects the results, and Section IX concludes.
Preliminaries
Quadratic APN functions
We identify with the field when convenient. Write as with coordinate functions . The algebraic degree of is the maximum degree of the algebraic normal forms of . In univariate form over , it is the maximum binary weight of an exponent with . The function is quadratic if all its derivatives are affine, that is, if its algebraic degree is at most two. For an affine function is not APN, so a quadratic APN function has algebraic degree exactly two. The polar form of a quadratic is
It is bilinear, symmetric and alternating: . Two quadratic functions with the same polar form differ by an affine map. So, up to EA-equivalence, a quadratic function is given by its polar form. We write for the linear map . Since , the following criterion is standard.
Lemma 2. A quadratic function is APN if and only if for every . Equivalently, for all linearly independent .
For a linear form , the component is a quadratic Boolean function. Its polar form is an alternating bilinear form. The component is bent if and only if is nondegenerate.
Equivalences and invariants
Two functions are EA-equivalent if with affine permutations and affine. EA-equivalence preserves the algebraic degree of functions of degree at least two. They are CCZ-equivalent if an affine permutation of maps the graph of onto the graph of [4]. For quadratic APN functions the two notions agree [5]. We use the invariants of Canteaut, Couvreur and Perrin [20]. The ortho-derivative of a quadratic APN function maps to the unique nonzero linear form that vanishes on the image of . The differential and extended Walsh spectra of are EA-invariants of . In this paper, a class is an EA-class of quadratic APN functions. By [5], it is exactly the set of quadratic functions in a CCZ-class. That CCZ-class may also contain functions of higher degree. For example, Dillon’s APN permutation of has degree four, and its CCZ-class contains a quadratic APN function [13]. So the number of classes is both the number of EA-classes of quadratic APN functions and the number of CCZ-classes that contain a quadratic APN function. All counts of classes in this paper, including the counts of known classes we cite, are of this kind. APN functions whose CCZ-class contains no quadratic function are not counted. To show that two functions are in the same class, we always compute an explicit equivalence and check it. To show that they are in different classes, we compare invariants.
Permutations
A component is non-bent if is degenerate. Let be the set of linear forms that give non-bent components, together with . If is CCZ-equivalent to a permutation, then contains two linear subspaces with [21]. We call this the counting criterion. It implies a weaker condition: the largest dimension of a linear subspace contained in satisfies . When we only use this bound, we say so. In [12] we give an exact test, the projection test, and apply both tests to the 25 published classes in dimension ten collected there. We use the same tests for the new classes of this paper.
Self-equivalences
A linear self-equivalence of a quadratic function is a pair of invertible linear maps of such that is affine. Equivalently,
The pairs that satisfy (1) form a group. If is a self-equivalence of , then is a self-equivalence of the function with polar form , which is EA-equivalent to . So only the conjugacy classes of and matter. Every nontrivial element of a finite group has a power of prime order. So every quadratic function with a nontrivial linear self-equivalence has one of prime order , that is, , and . In this paper “self-equivalence” always means a linear one.
Other papers count the full automorphism group , the group of affine permutations of that preserve the graph of [8]. For a quadratic , it contains the maps , which are affine since is affine. They form a group of order . If with affine, then is also in . Composing it with the maps above gives elements with linear parts and . So , where is the group of pairs that satisfy (1). In particular, if , then has no nontrivial linear self-equivalence.
For fixed , the polar forms that satisfy (1) form a linear space
It is the solution space of a homogeneous linear system with unknowns, the coordinates of the vectors , . For there are 450 unknowns. Every search and every proof in this paper starts from .
| total | |||||
| 2 | – | 25 | 5 | 5 | 35 |
| 3 | 2 | 25 | 5 | 5 | 35 |
| 5 | 4 | 4 | 2 | 2 | 8 |
| 7 | 3 | 41 | 5 | 5 | 51 |
| 11 | 10 | 1 | 1 | 1 | 3 |
| 17 | 8 | 2 | 1 | 1 | 4 |
| 31 | 5 | 123 | 5 | 5 | 133 |
| 73 | 9 | 8 | 1 | 1 | 10 |
| 127 | 7 | 18 | 1 | 1 | 20 |
| all | 247 | 26 | 26 | 299 |
Table 2. Number of self-equivalence types of prime order in dimension ten.
Notation
We write for the fixed space of . For a polynomial we write for the kernel of evaluated at . Let have odd prime order . Then is the direct sum of and the spaces . Here runs over the irreducible factors of the cyclotomic polynomial . We call the -part of . Each factor has degree , the multiplicative order of 2 modulo . We write for a primitive element of . We write for the absolute trace from to .
The 299 types
We follow Beierle and Leander [6 Sec. 4.1]. Let be a prime. An element of order of is described, up to conjugacy, as follows.
If is odd, it is a block-diagonal matrix. Each block is the companion matrix of an irreducible factor of . An identity block completes the matrix. So the conjugacy class is given by a multiset of factors of of total degree at most 10. All factors have degree , so we need . This leaves , with .
If , it is an involution. Its conjugacy class is given by the number of Jordan blocks of size two. We write for it. Then .
A self-equivalence of prime order has one of three kinds:
, if both and have order ;
, if ;
, if .
Conjugating and independently does not change the EA-class of the functions (Section II). Moreover, and with coprime to generate the same group. So we also identify pairs up to this power similarity. It permutes the factors of : the factor with root goes to the factor with root .
Table II gives the number of types. We obtained it by direct enumeration. For each , we list the conjugacy classes as above, form all pairs, and count the orbits of the powers . The power maps a factor of with root to the factor with root . A short independent script, included in the artifact, reproduces every entry of the table. We number them from 0 to 298, in the order of the artifact [22]. The 247 types of kind agree with the list of Beierle and Leander [6]. Their list of one-sided types is not reduced by power similarity, so it is longer than ours.
The space of a type
For each type we fix matrices and and compute the space of (1). Its dimension ranges from 0 to 405. Thirty-one types have : they contain no nonzero polar form, hence no quadratic function of degree two. For the others, the size of an exhaustive search depends on much more than . We estimate it with Knuth’s random probing method [23] on the search tree of Section V. The estimates range from a single node to about nodes. So a search alone cannot settle all types, and we first exclude as many types as possible by proof.
Table III gives the block structure of the types that are not excluded by proof, so that the numbering can be checked without the artifact. For , and . For , is one of the two factors of degree eight of ; power similarity exchanges them. For , let be a root of ; then is the minimal polynomial of : , , , , and . The artifact gives the matrices of all 299 types [22].
Some types in plain words
Several types have a simple description in the field . We use the following ones below.
Type 24 is . is conjugate to the Frobenius map . By Lemma 3 below, type 24 is the set of quadratic functions with coefficients in , up to EA-equivalence.
Type 73 is with of order 5, with two blocks of and . is conjugate to the Frobenius map . By Lemma 3, type 73 is the set of quadratic functions with coefficients in , up to EA-equivalence.
Type 64 is with the multiplication by on . These are the functions with up to affine terms. They are the quadratic canonical triplicate functions [10, 16, 24].
Types 41 and 47 are with of order 3, with two and three blocks of . So is 6 and 4. Types 24 and 73 hold the self-equivalence only up to affine terms. The next lemma shows that this makes no difference for subfield coefficients.
Lemma 3. Let divide , let on , and let be a quadratic function of . Write , where collects the terms of the reduced univariate polynomial of whose exponents have binary weight two, and is affine. Then is a self-equivalence of if and only if all coefficients of lie in . In that case is EA-equivalent to , which satisfies exactly.
Proof. Write over the exponents of binary weight two. Then , where is reduced modulo . The map permutes the exponents of weight two. So this is a reduced polynomial whose exponents all have weight two. It is affine only if it is zero, that is, only if for every . Since is affine, is affine if and only if is.
A function has a self-equivalence of type 24 if and only if it is EA-equivalent to one with the self-equivalence for , since is conjugate to . By Lemma 3, these are the quadratic functions with coefficients in , up to EA-equivalence. The same holds for type 73 with and .
| Type | Type | ||||||
| 24 | 2 | 175 | 31 | ||||
| 47 | 3 | 176 | 31 | ||||
| 64 | 3 | 180 | 31 | ||||
| 73 | 5 | 198 | 31 | ||||
| 116 | 7 | 207 | 31 | ||||
| 129 | 11 | 208 | 31 | ||||
| 132 | 17 | 209 | 31 | ||||
| 170 | 31 | 231 | 31 | ||||
| 171 | 31 | 235 | 31 | ||||
| 255 | 31 |
Table 3. The 19 types not excluded by proof. For odd , a block structure lists the factors of with multiplicity; an identity block completes the matrix. is an involution with Jordan blocks of size two, and the identity.
Excluding types by proof
In this section is a quadratic APN function of with polar form , and is a self-equivalence of prime order, so (1) holds. The lemmas give necessary conditions on the type of . Each condition can be checked on the matrices or on the space . When a condition fails, the type contains no APN function, and no search is needed.
Intertwiners
The first lemma uses the fixed points of .
Lemma 4 (Intertwiner lemma). Let , , and let . Then and .
Consequently:
(i) For every polynomial , maps into , and . Here is 1 if and 0 otherwise.
(ii) If is odd and , then for every irreducible factor of .
(iii) If and are involutions, then if , and if $k_A=n/2.
Proof. For all we have , since . The kernel of is by Lemma 2. From we get , so maps into . Its kernel on is , which gives (i). For (ii), take : then , because is fixed and . For (iii), put and . Then , so maps into , with kernel . We have and . If , then , and we may choose . This gives . If , every choice gives .
Lemma 4 says that the block structure of must fit into that of . It does not use the space at all. The next lemma looks at the action of in the other direction. It fixes a point outside and reads on .
Lemma 5 (Dual intertwiner lemma). Let be odd, and let be an irreducible factor of with . Then .
Proof. For and all we have . So intertwines and , and it maps into . Fix , . The map is linear on , with values in . Its kernel is contained in , since is not fixed. So it is injective.
Baudrin et al. proved a bound of a similar kind for all functions of low differential uniformity, not only quadratic ones [14 Corollary 3 and Remark 1]. Their self-equivalences satisfy exactly. For an APN function with such a nontrivial self-equivalence, the bound reads
Our self-equivalences hold only up to an affine term. So (2) does not apply to our types directly, and we only compare it with our necessary conditions. The two bounds are different: (2) compares with , while Lemma 5 compares with one part of . In dimension ten, Lemma 5 excludes 95 types, and (2) would exclude 65. Each excludes types that the other does not. For instance, type 41 has , so it violates (2). It is also excluded by Lemma 5, since . Neither bound excludes a type beyond Table IV below.
Restriction to an invariant subspace
The values of on fixed vectors are fixed: for we have . So restricts to a quadratic APN function from to , up to affine terms. The next lemma bounds such restrictions.
Lemma 6. Let , and let be a subspace of dimension . Let be the span of . If is APN, then .
Proof. For , , the restriction of to has kernel , so its image in has dimension . Suppose . Then this image is all of for every . Take a nonzero linear form on . The alternating form on is nondegenerate. Indeed, if is in its radical, then vanishes on , so . So the forms , , make up a space of dimension of alternating forms on whose nonzero elements are all nondegenerate. If is odd, this is impossible, since every alternating form in odd dimension is degenerate. If is even, the Pfaffian is a form of degree in the coordinates of . Since , Chevalley’s theorem [25 Cor. 6.6] gives a nonzero with Pfaffian zero, that is, a degenerate form.
Take , so that . The proof shows that contains , of dimension . So forces , which Lemma 6 forbids when . Together with the obvious bound , this extends Lemma 4 of Beierle and Leander [6], which states outside two small cases. The bound on spaces of nondegenerate alternating forms is also noted by Gow [26 Sec. 3]. In the computer check, runs over the sums of the subspaces , where is an irreducible factor of and . These subspaces are invariant under . The computer check does not use one candidate but the whole space . It computes from a basis of . For every the space of Lemma 6 lies in , and it has dimension at least if is APN. So forces , which the lemma forbids.
Order three
For we have , and is the part of without fixed points.
Lemma 7. Let have order , so that , and let . If is APN, then .
Proof. For put . Since , we get . So maps into . If , then and are linearly independent, so by Lemma 2. So the coordinates of are quadratic forms in variables with only the trivial common zero. By the Chevalley–Warning theorem, .
Odd dimension over
Lemma 8. Let with odd, and let be the multiplication by on . Let have prime order; since has order 3, this order is 3, so . If , then no quadratic APN function has the self-equivalence .
Proof. Write the output space as with . Then is an -space of dimension , where acts as , and . Let be the -component of . It satisfies . Extend scalars from to . Then the -linear map splits the space into its eigenspaces for and , and so does on . (On the original -space , is a scalar, so this splitting only appears after the extension.) Let and be eigenvectors of for and . The -eigencomponent of is nonzero only if , that is, . In particular vanishes on pairs of eigenvectors for and , since has no eigenvalue 1 on . The -eigencomponent is the conjugate of the -eigencomponent. So is determined by its restriction to the -eigenspace, which is an -tuple of -bilinear alternating forms in variables. In suitable coordinates, , where is the coordinatewise Frobenius image of . Since is odd, is degenerate. Take with in its radical. Then is semilinear over with image in an -space of dimension at most . So its kernel has dimension at least over . The -component adds at most linear conditions. So , and is not APN.
In dimension ten (), Lemma 8 excludes types 55 to 59. In Table 4, types 57, 58 and 59 are counted under Lemma 7, which also excludes them, and types 55 and 56 under Lemma 8. Among them, type 56 has a Knuth estimate of about nodes. As a cross-check, an exhaustive search confirms the case in dimension six.
| Criterion | types |
| 31 | |
| Compression, invariant subspaces (Proposition 9) | 237 |
| Restriction (Lemma 6) | 4 |
| Order three (Lemma 7) | 4 |
| Compression with Wong sequences | 2 |
| Odd dimension over (Lemma 8) | 2 |
| Total | 280 |
Table 4. Types excluded by proof. A type is counted under the first criterion that applies.
Compression
Lemmas 4 and 5 follow from one observation. For and a subspace , let
Proposition 9 (Compression criterion). If some with polar form in is APN, then for every and every subspace ,
Proof. The map sends into , with kernel .
Proposition 9 is a computation on . By bilinearity, is spanned by the vectors , where runs over a basis of and over a basis of . A failing pair is a certificate that the type is empty. The certificate is valid only if the basis spans all of , not just a subspace. The artifact therefore stores, for each excluded type, the matrices and , a basis of , and a witness for the first criterion that excludes it. For this criterion and for the Wong-sequence criterion the witness is the pair . For Lemma 6 it is a basis of the subspace, and for Lemma 7 the two dimensions it compares. When or Lemma 8 applies, no witness beyond , and the basis is needed. An independent checker recomputes the rank of the linear system that defines from and , checks that the stored basis has the full dimension and satisfies the system, and then checks the witness [22]. Lemma 4 (i) and (ii) are the case , . Lemma 4 (iii) is the case , . Lemma 5 is the case , . But the criterion is stronger, since is computed from the actual space . We test all and all sums of the subspaces as above.
For two types the invariant subspaces are not enough, and we choose adapted to . Fix and a generic map for some . Let . The second Wong sequence [27], [28] , is increasing. Here is the full preimage, and is the span of all with , ; both are computed by linear algebra from bases. Its limit gives with . We then check Proposition 9 for this directly. So the result is a certificate even though was chosen at random. This settles types 130 and 169.
Summary of the exclusions
Table IV summarizes the exclusions. Lemma 4 and Lemma 6 on alone already exclude 170 types, using only the matrices and . The bound (2) and Lemma 5 exclude no type beyond Table IV. No criterion excludes a type in which our searches found an APN function. This is a useful consistency check of the implementation. For most excluded types we also ran the generic search of Section V, and it found no APN function.
Exhaustive search
This section describes the generic search, which works for any type. Section VI describes the dedicated methods for types 24 and 47.
The search tree
Fix a type and a basis of . A polar form in is with . The 450 unknowns are the coordinates , ordered first by the pair in the order , , , , and then by the output coordinate . We put the basis in reduced echelon form with respect to this order, with the pivot of at its first nonzero unknown. We say that the pivot of is at the pair of that unknown. Then the value depends only on the coefficients whose pivot is at or before the pair .
The search follows the variable approach of earlier work [6], [29]. Level adds the input vector . Within a level, the pairs are filled in order. At each pair, the coefficients with a pivot there are chosen in all possible ways. Let . By Lemma 2, is APN on if and only if it is APN on and
Indeed, let be linearly independent. If both lie in , the condition on applies. If exactly one, say , lies in , write with ; then , which is nonzero by (3) with . If neither lies in , then is nonzero and , which is the previous case. Condition (3) is tested for as soon as is known for the highest index in . We keep a reduced echelon basis of each space , so each test takes at most steps. A leaf of the tree is a quadratic APN function of with the self-equivalence .
Using the centralizers
The centralizers and act on by with , . This action preserves the EA-class. We use it in three ways, and each one keeps at least one member of every orbit.
First value. The value is restricted to representatives of the orbits of on nonzero vectors.
Output side. On the first pairs, the search keeps only values that are lexicographically least under a stabilizer chain in . This comparison uses a different order from the echelon form above. Each value is read as an integer, and sequences of values are compared pair by pair with the usual order of integers. If a value ties with its image, the value is kept and the comparison moves to the next pair.
Input side. At the end of some levels, we apply sampled maps that preserve , followed by the output reduction. If the image of the current prefix is lexicographically smaller, the branch is pruned. The order is the same lexicographic order on the sequence of values, and preserves . So if the image of a prefix is smaller, the image of every completion is smaller too. Hence the least member of each orbit is never pruned, and the reduction is sound even with sampled maps.
For several hard types it also helps to reorder the input basis: first , then , then a complement. The random choices are reseeded from a hash of the current prefix. So the pruning is deterministic, and the tree can be split into independent shards that are run in parallel.
Cost
We estimate the size of each tree with Knuth’s method [23], before and after the reductions. Each estimate averages 2,000 or 3,000 random root-to-leaf probes with a fixed seed. These estimates are heuristic; we use them only to choose a method, never as part of a proof. For example, type 18 goes from to nodes. The generic search completed on 258 types. The classification and confirmation searches took about 36,400 core-hours: 13,300 on type 47, 12,600 on type 73, 7,500 on type 24, and about 3,000 on all other searched types. The last figure includes the confirmation searches on the 242 types that are also excluded by proof. It does not count the type-64 searches or the Knuth estimates. The runs used three Linux servers (Ubuntu 22.04). Each has two AMD EPYC 7763 processors (64 cores each, 2.45 GHz, two hardware threads per core, so 256 threads) and 1 TB of RAM. The servers were shared with other users, and our jobs could use at most 200 threads per server. Every job is single-threaded and ran at the lowest priority. A core-hour here is one hour of wall-clock time of one job on one hardware thread. It is not a measurement on a dedicated core. The search engine is written in C and compiled with gcc 11.4 and −O3. The equivalence tests are in Python. Each type’s cost is listed in the artifact [22].
Validation
We validated the search on cases with a known answer.
The space of all functions gives exactly 1023 APN functions, and one after normalization. The space of all gives none.
Type 231 (order 31) gives Beierle–Leander #1 [6].
In dimension eight, type 68 of the dimension-eight list (order 7) contains 9 classes. The search without reductions ( nodes) and with both reductions ( nodes) give the same 9 classes. The same holds when the run is split into shards.
In dimension ten, type 176 gives the same 11 classes with and without the reductions.
Splitting a run into shards and running the same program again tests the splitting, not the reductions. The tests with and without reductions, and the cases with a known answer, check the implementation of the reductions. They complement the soundness arguments above; they do not replace them.
The APN property of every reported function, including the representatives of the four new classes, is checked independently from its full difference table.
Classifying the leaves
Every leaf is matched to a known class by an explicit EA-equivalence. We first compute the ortho-derivative invariants of the leaf [20]. They select a known representative with the same invariants, or show that the leaf is new. The certificate search is exhaustive: if it finds no equivalence, the leaf is not EA-equivalent to , and we keep it as a possible new class. This never happened: every leaf whose invariants matched a known class was certified equivalent to it. Then we search for linear , and affine with . The search builds one basis vector at a time and derives by linear algebra. Two observations reduce the cost of a test.
Kernel partners. For a quadratic APN function, every nonzero linear form defines a component whose polar form has a radical . If , then . So maps the points that share a radical with onto the points that share a radical with . The search chooses the next basis vector among such partners whenever possible. Its image is then restricted to the partners of the image.
Transitivity. For the Gold functions, the maps act transitively on the nonzero inputs. So the image of the first basis vector can be fixed.
Each certificate is checked independently by recomputing . With these two observations, a test takes between 0.2 and 1.4 seconds in Python on one core. Without them, a test against the Gold function took more than ten minutes.
Results of the generic search
Table V lists the types in which the generic search finds APN functions. Every leaf was tested. Each one is EA-equivalent to a known class or to one of the four new classes of type 73. The other types searched by the generic method contain no APN function. Eight of them are not excluded by any lemma of Section IV: types 116, 132, 198, 207, 208, 209, 235 and 255. For these, as for type 47 in Section VI, the search is the only proof.
| Type | leaves | classes | names | |
| 129 | 11 | 250 | 4 | Gold , , Beierle–Leander #5, F13 |
| 170 | 31 | 338 272 | 1 | F3 |
| 171 | 31 | 338 272 | 1 | F3 |
| 175 | 31 | 492 032 | 1 | Gold |
| 176 | 31 | 3 189 280 | 11 | Beierle–Leander #3, six F12, four F13 |
| 180 | 31 | 492 032 | 1 | Gold |
| 231 | 31 | 961 | 1 | Beierle–Leander #1 |
| 73 | 5 | 4 536 | 24 | see Section VI-A |
Table V. Types in which the generic search finds APN functions. Leaves are APN functions in the search space after normalization.
Three hard types
Three types not excluded by proof are too large for a direct search with the basic settings: types 73, 24 and 47. For type 73 the generic search with all reductions is enough, on a large scale. Types 24 and 47 need a normal form and a dedicated solver.
Type 73: coefficients in
Type 73 is the set of quadratic functions of with coefficients in , up to EA-equivalence (Section III). This is the case of the search with subfield coefficients of Ichanska et al. who report it as infeasible [7]. Beierle and Leander ran a randomized, non-exhaustive search over most types in dimension ten [6]. Two of their new functions, Beierle–Leander #1 and #5, lie in type 73.
We split the tree into 192 shards. The run explored about nodes and took 12,600 core-hours. A second run, split into 3,072 shards, printed every leaf. Both runs agree piece by piece (16 shards of the second run for each of the 192 pieces of the first). They have the same number of nodes and the same 4,536 leaves. Every leaf was matched to a class by an exact certificate (§ 5-E).
Theorem 10 (computer-assisted). Up to EA-equivalence, there are exactly 24 quadratic APN functions of with all coefficients in . Twenty of them are published classes. Four are new.
Type 73 contains 20 published classes. Nine of them are the Gold functions and , Beierle–Leander #1 and #5 [6], and the triplicate functions #1, #3, #4, #5 and #6 of Budaghyan, Ivkovic and Kaleyski [10]. The other eleven come from known infinite families [9]. We call these families F3, F4, F12 and F13, as in the artifact [22]. Type 73 contains two, two, two and five classes of them. The five published classes missing from type 73 are Beierle–Leander #3 and four F12 classes. They all lie in type 176.
Table VI lists the four new classes. Their ortho-derivative spectra differ from those of all published classes and from each other. So they are four new EA-classes, hence four new CCZ-classes. We use the conventions of [20], and we reproduced the spectra published in [11]. We computed by listing all linear subspaces of of dimension up to five; the artifact recomputes it. All four classes have , so none of them is CCZ-equivalent to a permutation. Each new class has a univariate representative with 24 to 26 terms and all coefficients in . These representatives are listed in Appendix A and in the artifact [22].
Type 24: coefficients in
Type 24 is the set of quadratic functions of with coefficients in . It has a special role for the big APN problem. In dimension six, the quadratic APN functions with coefficients in form exactly two EA-classes: the Gold class and the class of Kim’s function. Kim’s function is on , with a primitive element. Its coefficients are not in , but its EA-class contains with , where is a root of ; we checked an explicit certificate. Kim’s function is CCZ-equivalent to Dillon’s APN permutation [13]. The next lemma shows that the bound never rules out this case.
Lemma 11. Let with odd, and let be a quadratic function of with all coefficients in . Then the components with are not bent. In particular .
Proof. Let be the Frobenius , so that (1) holds. Put . Expanding gives . With and this becomes . Let be a linear form with ; these are the forms with . Put and . Then: (a) ; since , this shows that is defined on the quotient in both arguments, and this quotient has dimension ; (b) by the same identity, so is symmetric; (c) , since lies in , and . So is alternating in odd dimension , hence degenerate. Take in its radical. Then is in the radical of .
So the simplest necessary condition for a permutation holds for every function of type 24. This makes type 24 the place to look for an analogue of Kim’s function. Its search tree is large: about nodes for the generic search, even with a fixed Gold prefix. We use a normal form instead.
Write with , and choose bases such that and on the output. Then .
Lemma 12 (Normal form). Every quadratic APN function with a self-equivalence of type 24 is EA-equivalent to a function
where is the Gold function or of , is the polar form of , is a bilinear map, and is a quadratic map with polar form . Conversely, every function (4) has the self-equivalence .
Proof. Write for the two output halves, and with bilinear . The equation has two halves. The first half reads . Expanding, it gives and . The second half reads . Expanding, it gives and . The maps , and are free.
The restriction has polar form . By Lemma 2, is the polar form of a quadratic APN function of . By the classification of the APN functions of [30], a quadratic one is EA-equivalent to or . The maps with commute with . Applying such maps on the input and the output, we may assume . Put and . Then and . These are the polar forms of (4). Two quadratic functions with the same polar form differ by an affine map, which proves the first claim. The converse is the same computation read backwards.
Lemma 12 leaves the bilinear map (125 bits) and the alternating form (50 bits). The next lemma turns APN into one condition per plane on . A plane is a 2-dimensional subspace of .
Lemma 13 (Planes). Let be as in (4). For linearly independent , let be the set of values , over all with . For a plane , let be the union of over the three bases of . Then is APN if and only if
(i) for every , and
(ii) for every plane .
Proof. Since is alternating, , so depends only on . By Lemma 2, is APN if and only if for all linearly independent and . We use the formulas for and from the proof of Lemma 12.
Case . Then , which is nonzero since is APN.
Case , . Then , and vanishes only for . For we get . So for all such if and only if (i) holds for . The case , is the same, since is symmetric.
Case . Then , and . This is the previous case.
Case independent. They span a plane , and . So for some if and only if . Since is symmetric, . The ordered pairs of independent vectors of give the three bases of . So this case is exactly (ii).
Lemma 13 turns APN into one “avoid a set” condition per plane on . There are 155 planes in . The search uses two groups of transformations that preserve the normal form (4) and the EA-class.
Translations of . For , the maps on the input and on the output commute with . They keep and , change , and replace by with . These form a space of dimension 49. So only the coset matters. We take the unique element of the coset that vanishes on the pivot coordinates of a reduced echelon basis of . This leaves 45 free bits for after condition (i) of Lemma 13. Under a translation, is a bijection of the solutions in the definition of , and is shifted by a vector that depends only on the plane .
Automorphisms of . The maps (, ) satisfy for a linear . Such a map sends to . Both coordinate changes commute with , and keeps , since . It replaces by . Hence , with the three parts permuted.
Lemma 14. The 155 maps act regularly on the 155 planes of .
Proof. It suffices to show that only the identity fixes a plane . Let fix . The group has order 155, which is prime to . So fixes each of the three nonzero points of . If , then for , so . If , the nonzero fixed points satisfy . Since , this has exactly one solution, so has at most one nonzero fixed point.
The key of a plane. For each plane we compute a key: the size of , the sorted sizes of its three parts, and, to break ties, the affine dimension, the sizes of the pairwise and triple intersections of the parts, and a hash of their multiplicity histograms. By the two previous paragraphs, the key of is unchanged by translations of , and after an automorphism. Moreover depends only on the columns with . So the keys of the planes inside are fixed once the first columns of are chosen.
The solver. It runs for and separately.
Choose the columns , , in reduced form, each satisfying condition (i). After columns 2 and 3, reject the prefix if some plane inside the current span has a strictly smaller key than .
List all values of on that satisfy condition (ii) on its planes.
Choose column , apply the key test, and extend to .
For each option of column , extend to and check condition (ii) on the remaining planes.
Every complete is a leaf. Its lookup table is rebuilt from (4) and checked to be APN.
Coverage. Let be APN of type 24. By Lemma 12, it is EA-equivalent to a function (4). Choose a plane of smallest key. By Lemma 14, there is exactly one automorphism of with . For the resulting we have for every plane . Then reduce modulo ; this does not change any key. The result has of smallest key among all planes. So it passes every key test, since the tests reject only strictly smaller keys. It satisfies conditions (i) and (ii), so is a leaf. Hence every class of type 24 has at least one leaf.
The run is split into 4,096 jobs: for each , job keeps the options of column 1 whose index is congruent to modulo 2048. The artifact lists the expected job identifiers and the completion record of each job, and a script checks that all of them finished with exit code zero. The full run took about 7,500 core-hours. It printed every leaf: there are three. In our runs, contradictions appeared only at the last step, when is extended to all of .
We validated the solver in two ways. First, an earlier implementation of the same method finds exactly the Gold and Kim classes in dimension six. Second, we planted known functions of type 24 in all 155 positions given by the automorphisms of . The production solver recovers , and from every position allowed by the key rule.
Theorem 15 (computer-assisted). Up to EA-equivalence, there are exactly three quadratic APN functions of with all coefficients in : , , and .
All three have . Since , Theorem 15 also covers the quadratic APN functions with coefficients in . All classes of Theorem 15 have representatives with coefficients in . So there are exactly three such classes. This agrees with Yu et al., who also found three classes with a different method [15]. Only the two Gold functions pass the counting criterion, and they fail the projection test [12]. So, unlike dimension six, type 24 contains no function CCZ-equivalent to a permutation.
Type 47
In type 47, has order three, with and of dimension four. Equivariance leaves four blocks of . The block on is a pair , with into and into . The block on is an intertwiner into , which is -linear in . The block on is the polar form of a quadratic function from to .
Lemma 16. If a function of type 47 is APN, then for every , : , and .
Proof. The -part of is , and its -part has rank at most . APN needs rank 9, so . The second condition is Lemma 2 restricted to .
We now describe the search. Identify with , with acting as . The block has four -valued coordinates, and each is of the form with a Hermitian matrix over . Up to linear maps on the output , only the span of matters. The block is -bilinear in and alternating, so it factors through the cross product: for a matrix over . An -linear output map sends to , so only the column space of matters. Since , an input map sends to . An input map acts by and . For we have , and vanishes for all exactly when for all . So APN requires to be anisotropic: for all only if .
Pairs . We list every subspace of dimension at most four, keep the anisotropic ones, and sort them into -orbits. Each orbit is checked to be complete: we compute the stabilizer of by brute force over all 181,440 elements of , and check . This gives 34 orbits of . For each, we split the -subspaces of into orbits of . This gives 806 classes of pairs with anisotropic.
Lemma 16. It removes 703 classes; 103 remain.
Normal form of . Fix the point . The map is injective, since for . Its image is a 4-dimensional -subspace of , and APN at requires . Input maps on act freely on the bases of , so we may choose the basis of such that is the reduced echelon basis of . The -linear output maps that fix act on the possible ; we keep one representative per orbit, the one with the smallest bitset. A slice is a class of step 2 together with one representative . There are 8,056 slices.
Completion. In each slice, the solver enumerates all remaining values of and all , testing the APN condition as it goes, as in Section V.
Coverage. Every APN function of type 47 is EA-equivalent, by maps that commute with , to one whose pair is one of the 806 representatives. By Lemma 16 it is one of the 103. Changing the basis of and applying an output map that fixes , we reach a slice. The solver is exhaustive within a slice.
The solver was validated on the analogue in dimension six, with and . There we fixed the blocks of and compared with a brute force over all completions . The brute force finds 144 APN completions, and 6 after the same normalization of ; the solver finds the same 6, all with the ortho-derivative spectrum of . The artifact lists the 806 classes, the 103 survivors and the 8,056 slices, and a script recomputes the split and checks that every slice finished with no APN function. All 8,056 slices finished. They took about 13,300 core-hours. No choice of reaches the last level.
Theorem 17 (computer-assisted). No quadratic APN function of has a self-equivalence of type 47.
The open type: canonical triplicate functions
In type 64, is the multiplication by on and . So the functions satisfy , up to affine terms. Up to EA-equivalence, these are the quadratic canonical triplicate functions of Budaghyan, Ivkovic and Kaleyski [10]. Baudrin, Canteaut and Perrin study them as a family of cyclotomic mappings [16]. No lemma of Section IV applies, and the type is too large for our searches (Section VII-C). It is the only type that we cannot settle. In this section we give a reformulation, the evidence we have, and the reasons why the type is hard.
A Hermitian reformulation
Write for the conjugate transpose of , where conjugation is . Let be the space of Hermitian matrices over . It is a vector space of dimension 25 over . For , the map takes values in , and it is invariant under . Its polar form is , where . This polar form is zero only for . So is injective modulo affine terms. The quadratic Boolean functions invariant under , modulo affine terms, also form a space of dimension 25: type 64 has , that is, 25 for each of the ten output coordinates. So these Boolean functions are exactly the Hermitian forms , up to affine terms. So a function of type 64 is given by ten Hermitian matrices :
Up to EA-equivalence, only their -span matters. If is APN, then . Indeed, the coordinates of are linearly independent modulo affine functions exactly when the values of span . They span a space of dimension at least 9, since has rank 9 for , and Lemma 6 with excludes dimension 9. On we use the nondegenerate -bilinear form , where is the matrix trace, and we write . Note that .
Proposition 18. Let be of type 64 with . The following are equivalent.
is APN.
Every point of is annihilated by exactly one nonzero matrix of .
is 3-to-1 on , with nonzero values.
The space contains no nonzero matrix of rank at most two.
Proof. (1)(2). Fix and consider the -linear map , . Since the trace form on is nondegenerate over , the rank of equals . By Lemma 2, is APN if and only if for all , that is, if and only if exactly one nonzero satisfies . This condition depends only on the point .
(3)(4). We have if and only if for all , that is, . Similarly if and only if . Over , the Hermitian matrices of rank one are the , and those of rank two are the with independent, since Hermitian forms of a given rank are congruent. Since , every nonzero fiber has at least three elements. So (3) says that has no element of rank one or two.
(1)(3) is the criterion of Budaghyan, Ivkovic and Kaleyski for triplicate functions [10 Thm. 1]. Its hypotheses hold: holds exactly, , and is plateaued, as every quadratic function is.
Proposition 18 links type 64 to Hermitian rank-metric codes. Here is an additive code of Hermitian matrices with minimum rank distance 3. It meets the bound of Schmidt for additive Hermitian codes with equality [31 Theorem 1]. Since the distance 3 is odd, the rank distribution of is determined by these parameters [31 Theorems 1 and 3]. By duality, so is the rank distribution of ; in particular every nonzero element of has rank at least four. Then Proposition 18(2) gives the rest: a matrix of rank four annihilates exactly one point of and a matrix of rank five none. So has 341 elements of rank 4, one for each point, and of rank 5. The code has 1,705 elements of rank 3, 12,958 of rank 4 and 18,104 of rank 5. We also computed these numbers directly, by listing all elements of and , for the 16 known classes [22]. Since every nonzero element of has rank at least four, the graphs , , pairwise meet in at most a point. In geometric terms, they are 1,024 generators of the Hermitian polar space with this property [32]. Here is defined in by the Hermitian form ; the graph of a Hermitian is totally isotropic for it. Trombetti and Zullo study maximum additive Hermitian codes [33]. We found no classification of these codes for matrices over . To our knowledge, the realization of type 64 as subspaces of and the characterization of APN by the dual code (Proposition 18) are new. The triplicate functions themselves and their 3-to-1 criterion are due to [10].
So type 64 is the same as the following problem. Classify the 10-dimensional -subspaces of such that every point of is annihilated by exactly one nonzero element of . The group acts on these subspaces by . Equivalent subspaces give EA-equivalent functions. The converse is not clear, since an EA-equivalence need not respect the -structure.
What is known in type 64
Sixteen of the 29 classes of Theorem 1 lie in type 64. They are the Gold functions and , two F3 classes, two F4 classes, five F13 classes, and the triplicate functions #1, #3, #4, #5 and #6 of [10]. The triplicate function #2 of [10] is EA-equivalent to an F13 class; we checked an explicit certificate. All 16 classes also lie in type 73.
We explored type 64 with three search strategies. They are evidence, not proofs, and they are weaker than the searches of § 5 and VI in one respect. For speed, each search keeps only the first APN function it finds with a given fingerprint, the differential spectrum of the ortho-derivative stored as a 64-bit hash, and discards the others. The kept functions are then named by comparing their ortho-derivative invariants [20] with those of the 29 known classes; no equivalence certificate is computed. The fingerprint is not a complete invariant. So what the searches show is that every APN function they found has the fingerprint of one of the 16 known classes of type 64. A new class with the same fingerprint as a known one would not be detected.
Sparse polynomials, exhaustively. We listed all polynomials , where the are distinct exponents among the 24 exponents with odd, and the are nonzero. We ran with and , with and , and with and . The number of candidates is over these cases. This extends the search of [10 Sec. 9.2] to more terms and to . It found 37,044,315 APN functions, with the fingerprints of exactly the 16 classes.
Switching in the Hermitian picture. For each of the 16 classes we took one space . For each of its 174,251 subspaces of dimension 8, we computed by linear algebra all spaces of dimension 10 that contain and satisfy Proposition 18(2). This step has no cap. The program excludes itself, which is a completion of every . It computes the fingerprint of every completion it finds. An independent program recounts the completions on sampled subspaces , and checks each of them to be APN with the full difference table [22]. This includes every switching of codimension one. The search found 529,903 pairs . All of them have the fingerprints of 7 of the 16 classes. Since EA-equivalence need not respect the -structure, one class may contain several inequivalent spaces ; we switched only from one space per class.
Random sparse polynomials. Type 64 is spanned by the 25 monomials with odd. More than random polynomials with 2 to 14 of these terms, and coefficients in , or , give the fingerprints of the 16 classes again, and no other fingerprint.
Why type 64 is hard
The generic search of § 5 has a Knuth estimate of about nodes on type 64.
A dedicated solver builds point by point in , with one matrix of rank four fixed. Its tree has about nodes, and about when it branches on the most constrained point. The constraints prune only at the last two of ten levels.
The estimates suggest that isomorph rejection alone is not enough. The group has order about . The Knuth estimate of the tree at level eight is about partial spaces. Dividing by the group order suggests that, even with perfect isomorph rejection, at least about inequivalent partial spaces remain there. This is an estimate, not a proven bound: the nodes of the tree need not be distinct partial spaces, and the set of explored nodes need not be invariant under the group.
In short, valid spaces are rare among partial ones, and the constraints act only at the end.
The evidence for the following conjecture is the three searches above. None of them is exhaustive on type 64.
Conjecture 19. Every quadratic APN function of with a self-equivalence of type 64 is EA-equivalent to one of the 16 known classes. Equivalently, every quadratic canonical triplicate APN function of is EA-equivalent to one of these 16 classes.
Since all 16 classes occur in type 73, Conjecture 19 and Theorem 1 together would give the following: a quadratic APN function of has a nontrivial linear self-equivalence if and only if it is EA-equivalent to one of the 29 classes.
| Settled by | types | remarks |
| proof and search | 242 | no APN function |
| proof only | 38 | search too large or not run; no APN function |
| search only | 18 | 9 empty, 9 with APN functions |
| open | 1 | type 64 |
| total | 299 |
Table VII. How the 299 types are settled.
Results
How the 299 types are settled
Table VII shows how each type is settled. Most types are settled twice, by a proof and by a search. The per-type table, with the certificate of each proof and the cost of each search, is in the artifact [22].
The types settled by search only are the following. Types 47, 116, 132, 198, 207, 208, 209, 235 and 255 contain no APN function. Types 24, 73, 129, 170, 171, 175, 176, 180 and 231 contain APN functions. No other type contains an APN function, except possibly type 64.
The 29 classes
Table VIII lists the 29 classes and the types that contain them. Every class lies in at least one type other than type 64. The published classes are the 25 classes of [6], [9]–[11], as collected in [12], with an explicit representative and an equivalence certificate for each. When we say “published classes”, we mean these 25. For some infinite families, [12] checked only sampled members in dimension ten, so we do not claim that every member of every published family is among them. The recent exhaustive searches of Ichanska and Kaleyski for extended biprojective functions in dimension ten find only Carlet’s classes and the classes of [11] [34 Sec. 7.1]. These are among the 25.
Proof of Theorem 1. Let have a self-equivalence of prime order of type . If is one of the 280 types of § 4, then is not APN. The same holds for the nine empty types settled by search, including type 47 (Theorem 17). Otherwise is one of the nine types listed above. The searches of § 5 and Theorems 10 and 15 list all APN functions of these types. Each of them is EA-equivalent to a class of Table VIII, by an explicit certificate. Table VIII shows that each class occurs in such a type. □
Consequences
Every known class has a self-equivalence: Each of the 25 published classes has a linear self-equivalence of prime order. Table VIII gives, for each class, the types in which it occurs.
| Class | types | |
| Gold | 5 | 24, 64, 73, 129, 175 |
| Gold | 5 | 24, 64, 73, 129, 180 |
| F4 () | 5 | 24, 64, 73 |
| F4 | 5 | 64, 73 |
| F3 | 4 | 64, 73, 170 |
| F3 | 4 | 64, 73, 171 |
| F12, two classes | 3, 4 | 73, 176 |
| F12, four classes | 3, 4, 3, 4 | 176 |
| F13 , four classes | 5, 5, 4, 3 | 64, 73, 176 |
| F13 | 3 | 64, 73, 129 |
| Beierle–Leander #1 | 3 | 73, 231 |
| Beierle–Leander #3 | 5 | 176 |
| Beierle–Leander #5 | 4 | 73, 129 |
| BIK triplicate #1, #3, #4, #5, #6 | 4 | 64, 73 |
| N1 | 3 | 73 |
| N2, N3, N4 | 4 | 73 |
Table VIII. The 29 quadratic APN classes of and the types that contain them. Names of the published classes follow the artifact [22]; BIK refers to [10]. N1–N4 are the new classes of Table VI.
Permutations: None of the 29 classes is CCZ-equivalent to a permutation. For the 25 published classes this is shown in [12]. The four new classes have (Table VI). So Theorem 1 gives the following.
| Class | ortho-derivative differential spectrum | |
| N1 | 3 | |
| N2 | 4 | |
| N3 | 4 | |
| N4 | 4 |
Table VI. The four new quadratic APN classes of . is the largest dimension of a space of non-bent components. The spectrum is the differential spectrum of the ortho-derivative, written as value^{multiplicity}.
Corollary 20. Let be a quadratic APN function of with a linear self-equivalence of prime order, of a type other than 64. Then is not CCZ-equivalent to a permutation.
Conclusion
We classified the quadratic APN functions of with a linear self-equivalence of prime order, for 298 of the 299 types. There are 29 classes, four of them new, and none is CCZ-equivalent to a permutation. Elementary lemmas on the polar form settle 280 types without any search. The remaining types need exhaustive searches. The classification and confirmation searches took about 36,400 core-hours.
The open type 64 is a problem on Hermitian matrices. Classify the 10-dimensional spaces of Hermitian matrices over such that every point of is annihilated by exactly one nonzero matrix. As sets, these spaces are the duals of the maximum additive Hermitian codes of minimum distance three in this size. We expect that a proof of Conjecture 19 needs more structure than our searches use, for example a geometric argument in the Hermitian polar space .
Two questions remain open beyond type 64. First, the lemmas of § 4 hold in every dimension. However, we do not know whether the searches stay feasible in dimension twelve. Second, we do not know whether has quadratic APN functions without any nontrivial linear self-equivalence.
The four new classes
Let be a root of , so that , and let . Then , so . In the artifact, field elements are integers in the basis , so is 236 and is 237. The following polynomials are representatives of the classes N1–N4 of Table VI. They are the shortest forms we found among the leaves of type 73. We checked independently, from the full difference table, that each one is APN. The artifact gives them also as lookup tables, in the file data/quadratic_classes.tsv [22].
Code and Data
The artifact holds the code, the supplied data and the regeneration instructions. It is available at https://github.com/peacker/apn10-self-equivalences. This paper refers to commit 6f8a932a9f93; it will be archived with a DOI at publication. The artifact contains the matrices of the 299 types, a basis of each space , the exclusion certificates with an independent checker, the job lists and completion records of all searches with a checking script, and lookup tables of all 29 classes. It contains every leaf of types 24 and 73. The generic search also found APN functions in seven other types, with 4,851,099 leaves in all. For these, the artifact contains one record per leaf, with its invariant, its class and the result of its equivalence test, but not the lookup tables, which take about 8 GB. They are available on request, and the searches that print them take about 9 core-hours. For type 64, the artifact contains the classified fingerprints, not every function found. The file DATA.md lists all omitted data. An equivalence certificate was computed and checked for every leaf of the 298 settled types when the leaves were classified. The certificates themselves are not stored: the logs record the result, and the quick checks recompute a sample. For the 4,536 leaves of type 73, the full check takes about 20 minutes on one core. For the other 4,851,099 leaves it means regenerating the leaves and then about 1,300 core-hours of equivalence tests. A file of SHA-256 checksums identifies every file. The README separates three levels: consistency checks of the stored logs, independent checks of the stored certificates and representatives, which take minutes, and the full regeneration of the searches and equivalences. Field elements are integers in the polynomial basis: is defined by , and , in the type-24 solver, by .
Acknowledgment
The author used a large language model, Claude (Anthropic), throughout this work. It was used to write and run the code of the artifact, to draft and edit the text of all sections, and to check proofs and references. All results were checked by the author. For the 298 settled types, every leaf used in the classification was matched to a known class by an explicit EA-equivalence certificate, which was checked directly (§ 5 and VI). The exploratory searches of type 64 compute no certificates (Section VII). The exhaustive searches were validated on cases with a known answer (§ 5 and VI). The author takes full responsibility for the content.
References
References
- [1]K. Nyberg, “Differentially uniform mappings for cryptography,” in Advances in Cryptology - EUROCRYPT ’93, Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings, ser. Lecture Notes in Computer Science, vol. 765. Berlin, Heidelberg: Springer, 1993, pp. 55–64.
- [2]M. Matsui, “New block encryption algorithm MISTY,” in Fast Software Encryption (FSE 1997), ser. Lecture Notes in Computer Science, vol. 1267. Springer, 1997, pp. 54–68.DOI
- [3]C. Carlet, Boolean Functions for Cryptography and Coding Theory. Cambridge: Cambridge University Press, 2021.DOI
- [4]C. Carlet, P. Charpin, and V. A. Zinoviev, “Codes, bent functions and permutations suitable for DES-like cryptosystems,” Des. Codes Cryptogr., vol. 15, no. 2, pp. 125–156, 1998. [Online]. Available: https://doi.org/10.1023/A:1008344232130
- [5]S. Toshiara, “Equivalences of quadratic APN functions,” J. Algebraic Combin., vol. 35, no. 3, pp. 461–475, 2012. [Online]. Available: https://doi.org/10.1007/s10801-011-0309-1
- [6]C. Beierle and G. Leander, “New instances of quadratic APN functions,” IEEE Trans. Inf. Theory, vol. 68, no. 1, pp. 670–678, 2022. [Online]. Available: https://doi.org/10.1109/TIT.2021.3120698
- [7]N. Ichanska, S. Berg, N. S. Kalevski, and Y. Yu, “Pushing the QAM method for finding APN functions further,” Cryptogr. Commun., vol. 18, no. 3, pp. 727–762, 2026, preprint: Cryptology ePrint Archive, Paper 2024/1838. [Online]. Available: https://doi.org/10.1007/s12095-025-00851-1
- [8]C. Beierle, P. L. G. P. Levegin, G. Leander, A. A. Polujan, and S. Rasoolzadeh, “Millions of inequivalent quadratic APN functions in eight variables,” CoRR, vol. abs/2508.04644, 2025, version 2, August 2026. [Online]. Available: https://doi.org/10.48550/arXiv.2508.04644
- [9]L. Budaghyan, M. Calderini, and I. Villa, “On equivalence between known families of quadratic APN functions,” Finite Fields Their Appl., vol. 66, 2020, Art. no. 101704. [Online]. Available: https://doi.org/10.1016/j.ffa.2020.101704
- [10]L. Budaghyan, I. Ivkovic, and N. S. Kaleyski, “Triplicate functions,” Cryptogr. Commun., vol. 15, no. 1, pp. 35–83, 2023. [Online]. Available: https://doi.org/10.1007/s12095-022-00587-2
- [11]T. Helleseth, N. Ichanska, and N. Kaleyski, “New infinite families of APN functions from the switching construction in even dimension,” Cryptology ePrint Archive, Paper 2026/2401, 2026. [Online]. Available: https://eprint.iacr.org/2026/2401
- [12]E. Bellini, “Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions,” Cryptology ePrint Archive, Paper 2026/2800. Submitted to Cryptogr. Commun., 2026. [Online]. Available: https://eprint.iacr.org/2026/2800arxiv.org/abs/2611.10269
- [13]K. A. Browning, J. F. Dillon, M. T. McQuistan, and A. J. Wolfe, “An APN permutation in dimension six,” in Finite Fields: Theory and Applications, ser. Contemporary Mathematics. Providence, RI: American Mathematical Society, 2010, vol. 518, pp. 33–42.DOI
- [14]J. Baudrin, C. Beierle, P. Felke, G. Leander, P. Neumann, L. Perrin, and L. Stennes, “Commutative cryptanalysis as a generalization of differential cryptanalysis,” Des. Codes Cryptogr., vol. 93, no. 8, pp. 3243–3281, 2025.DOI
- [15]Y. Yu, J. Li, N. Ichanska, and N. S. Kaleyski, “Classification of quadratic APN functions with coefficients in F₂ in dimension 10,” Appl. Algebra Eng. Comput. Commun., vol. 37, no. 6, pp. 1391–1409, 2026. [Online]. Available: https://doi.org/10.1007/s00200-025-00711-8
- [16]J. Baudrin, A. Canteaut, and L. Perrin, “Linear self-equivalence of the known family of APN functions: a unified point of view,” Cryptology ePrint Archive, Paper 2026/1012, 2026. [Online]. Available: https://eprint.iacr.org/2026/1012
- [17]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, 2021. [Online]. Available: https://doi.org/10.1109/TIT.2021.3071533
- [18]F. Göloğlu and L. Kölsch, “Equivalences of biprojective almost perfect nonlinear functions,” Comb. Theory, vol. 5, no. 3, 2025, Art. no. 7. [Online]. Available: https://doi.org/10.5070/C65365555
- [19]U. Dempwolff and Y. Edel, “Isomorphisms and automorphisms of extensions of bilinear dimensional dual hyperovals and quadratic APN functions,” J. Group Theory, vol. 19, no. 2, pp. 249–322, 2016.DOI
- [20]A. Canteaut, A. Couvreur, and L. Perrin, “Recovering or testing extended-affine equivalence,” IEEE Trans. Inf. Theory, vol. 68, no. 9, pp. 6187–6206, 2022. [Online]. Available: https://doi.org/10.1109/TIT.2022.3166692
- [21]F. Göloğlu and J. Pavlů, “On CCZ-inequivalence of almost perfect nonlinear functions to permutations,” Cryptogr. Commun., vol. 13, no. 3, pp. 377–391, 2021. [Online]. Available: https://doi.org/10.1007/s12095-021-00476-0
- [22]E. Bellini, “Code and data for “quadratic APN functions of F₂¹⁰ with a self-equivalence of prime order”,” https://github.com/peacker/apn10-self-equivalences, 2026.
- [23]D. E. Knuth, “Estimating the efficiency of backtrack programs,” Math. Comp., vol. 29, no. 129, pp. 121–136, 1975.
- [24]L. Kölsch, B. Kriepke, and G. M. Kyureghyan, “Image sets of perfectly nonlinear maps,” Des. Codes Cryptogr., vol. 91, no. 1, pp. 1–27, 2023.arxiv.org/abs/2012.00870
- [25]R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., ser. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1997, vol. 20.DOI
- [26]R. Gow, “Rank-related dimension bounds for subspaces of bilinear forms over finite fields,” arXiv:1703.07266, 2017.arxiv.org/abs/1703.07266
- [27]K.-T. Wong, “The eigenvalue problem λTx + Sx,” J. Differential Equations, vol. 16, no. 2, pp. 270–280, 1974.DOI
- [28]G. Ivanyos, M. Karpinski, Y. Qiao, and M. Santha, “Generalized Wong sequences and their applications to Edmonds’ problems,” J. Comput. Syst. Sci., vol. 81, no. 7, pp. 1373–1386, 2015.
- [29]Y. Yu, M. Wang, and Y. Li, “A matrix approach for constructing quadratic APN functions,” Des. Codes Cryptogr., vol. 73, no. 2, pp. 587–600, 2014. [Online]. Available: https://doi.org/10.1007/s10623-014-9955-3
- [30]M. Brinkmann and G. Leander, “On the classification of APN functions up to dimension five,” Des. Codes Cryptogr., vol. 49, no. 1–3, pp. 273–288, 2008.DOI
- [31]K.-U. Schmidt, “Hermitian rank distance codes,” Des. Codes Cryptogr., vol. 86, no. 7, pp. 1469–1481, 2018.arxiv.org/abs/1702.02793
- [32]R. Gow, M. Lavrauw, J. Sheekey, and F. Vanhove, “Constant rank-distance sets of Hermitian matrices and partial spreads in Hermitian polar spaces,” Electron. J. Combin., vol. 21, no. 1, 2014, Art. no. P1.26.arxiv.org/abs/1208.1903
- [33]R. Trombetti and F. Zullo, “On maximum additive Hermitian rank-metric codes,” J. Algebraic Combin., vol. 54, no. 1, pp. 151–171, 2021.arxiv.org/abs/2001.06628
- [34]N. Ichanska and N. S. Kaleyski, “Extended biprojective APN functions,” Cryptology ePrint Archive, Paper 2026/2451, 2026. [Online]. Available: https://eprint.iacr.org/2026/2451