betaFeedback

WorksComputer Science

Quadratic APN Functions of F210\mathbb{F}_2^{10} with a Self-Equivalence of Prime Order

Abstract

Almost perfect nonlinear (APN) functions of F2n\mathbb{F}_2^n 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 n≥8n \geq 8. 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 F210\mathbb{F}_2^{10} 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 F4\mathbb{F}_4, and all 3 that contain one with coefficients in F32\mathbb{F}_{32} 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 F:F2n→F2nF:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n} is almost perfect nonlinear (APN) if the equation F(x+a)+F(x)=bF(x+a)+F(x)=b has at most two solutions for every a≠0a\ne0 and every bb [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 n≤5n\le5 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 F210\mathbb{F}_{2}^{10} 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 FF is a pair of invertible linear maps (A,B)(A,B) such that F∘AF\circ A and B∘FB\circ F 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.

n=8n = 8n=10n = 10
Known quadratic APN classesmillions25 (29 with this paper)
Random search finds new classesyesrarely
Classes with a self-equivalence of prime orderat most 12,775 of 3,808,491 (0.34%) in [8]all known ones
Where the known classes come fromlarge computational searches and constructionspower functions, infinite families, self-equivalences
Classes CCZ-equivalent to a permutationnone [6, 8]none; three pass the counting criterion but fail the projection test [12]
Analogy with Dillon’s permutation (n=6n = 6)n≡0(mod4)n \equiv0 \pmod{4}n≡2(mod4)n \equiv2 \pmod{4}, as n=6n = 6

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 F2n\mathbb{F}_2^n for some even n≥8n \ge8. 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 n≡2n \equiv2 (mod 4).

Contributions

Let β(x,y)=F(x+y)+F(x)+F(y)+F(0)\beta(x, y) = F(x + y) + F(x) + F(y) + F(0) be the polar form of a quadratic function FF. A pair (A,B)(A, B) of invertible linear maps is a self-equivalence of FF if and only if β(Ax,Ay)=Bβ(x,y)\beta(Ax, Ay) = B\beta(x, y) for all x,yx, y. Every nontrivial self-equivalence has a power of prime order. Up to conjugacy and power similarity there are 299 types of prime-order pairs (A,B)(A, B) in dimension ten (Section III). Our main result is the following.

Theorem 1 (computer-assisted). Let FF be a quadratic APN function of F210\mathbb{F}_2^{10} with a linear self-equivalence of prime order. Suppose that FF has such a self-equivalence of a type other than type 64. Then FF 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.

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 F210\mathbb{F}_{2}^{10} 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 F210\mathbb{F}_{2}^{10} with coefficients in F4\mathbb{F}_{4}. 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 F32\mathbb{F}_{32}. 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 F210\mathbb{F}_{2^{10}} are F2\mathbb{F}_{2}, F4\mathbb{F}_{4} and F32\mathbb{F}_{32}. So these two cases classify the quadratic APN functions of F210\mathbb{F}_{2^{10}} with coefficients in any proper subfield. For F2\mathbb{F}_{2} 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 F210\mathbb{F}_{2}^{10}.

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 F210\mathbb{F}_{2^{10}} with coefficients in F2\mathbb{F}_{2} [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 F2n\mathbb{F}_{2}^{n} with the field F2n\mathbb{F}_{2^{n}} when convenient. Write F:F2n→F2nF:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n} as F=(f1,…,fn)F=(f_{1},\ldots,f_{n}) with coordinate functions fi:F2n→F2f_i:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}. The algebraic degree of FF is the maximum degree of the algebraic normal forms of f1,…,fnf_1,\ldots,f_n. In univariate form F(x)=∑iaixiF(x)=\sum_i a_i x^i over F2n\mathbb{F}_{2^n}, it is the maximum binary weight of an exponent ii with ai≠0a_i\ne0. The function FF is quadratic if all its derivatives DaF(x)=F(x+a)+F(x)D_aF(x)=F(x+a)+F(x) are affine, that is, if its algebraic degree is at most two. For n≥2n\ge2 an affine function is not APN, so a quadratic APN function has algebraic degree exactly two. The polar form of a quadratic FF is

β(x,y)=F(x+y)+F(x)+F(y)+F(0).\beta(x,y)=F(x+y)+F(x)+F(y)+F(0).

It is bilinear, symmetric and alternating: β(x,x)=0\beta(x,x)=0. 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 βa=β(a,⋅)\beta_a=\beta(a,\mathord{\cdot}) for the linear map y↦β(a,y)y\mapsto\beta(a,y). Since DaF(x)=βa(x)+DaF(0)D_aF(x)=\beta_a(x)+D_aF(0), the following criterion is standard.

Lemma 2. A quadratic function FF is APN if and only if ker⁡βa={0,a}\ker\beta_a=\{0,a\} for every a≠0a\ne0. Equivalently, β(x,y)≠0\beta(x,y)\ne0 for all linearly independent x,yx,y.

For a linear form c∈(F2n)∗c\in(\mathbb{F}_2^n)^*, the component c⋅Fc\mathbin{\cdot}F is a quadratic Boolean function. Its polar form c⋅βc\mathbin{\cdot}\beta is an alternating bilinear form. The component is bent if and only if c⋅βc\mathbin{\cdot}\beta is nondegenerate.

Equivalences and invariants

Two functions F,GF,G are EA-equivalent if G=L1∘F∘L2+L3G=L_1\circ F\circ L_2+L_3 with L1,L2L_1,L_2 affine permutations and L3L_3 affine. EA-equivalence preserves the algebraic degree of functions of degree at least two. They are CCZ-equivalent if an affine permutation of F22n\mathbb{F}_2^{2n} maps the graph of FF onto the graph of GG [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 a≠0a\ne0 to the unique nonzero linear form π(a)\pi(a) that vanishes on the image of βa\beta_a. The differential and extended Walsh spectra of π\pi are EA-invariants of FF. 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 F26\mathbb{F}_2^6 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 c⋅Fc\mathbin{\cdot}F is non-bent if c⋅βc\mathbin{\cdot}\beta is degenerate. Let N\mathcal{N} be the set of linear forms cc that give non-bent components, together with 00. If FF is CCZ-equivalent to a permutation, then N\mathcal{N} contains two linear subspaces B1,B2B_1,B_2 with B1+B2=(F2n)∗B_1+B_2=(\mathbb{F}_2^n)^* [21]. We call this the counting criterion. It implies a weaker condition: the largest dimension MM of a linear subspace contained in N\mathcal{N} satisfies M≥n/2M\ge n/2. 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 FF is a pair (A,B)(A,B) of invertible linear maps of F2n\mathbb{F}_2^n such that F∘A+B∘FF\circ A+B\circ F is affine. Equivalently,

β(Ax,Ay)=B β(x,y)for all x,y.(1)\beta(Ax,Ay)=B\,\beta(x,y)\qquad\text{for all }x,y. \tag*{(1)}

The pairs that satisfy (1) form a group. If (A,B)(A,B) is a self-equivalence of FF, then (TAT−1,SBS−1)(TAT^{-1},SBS^{-1}) is a self-equivalence of the function with polar form Sβ(T−1x,T−1y)S\beta(T^{-1}x,T^{-1}y), which is EA-equivalent to FF. So only the conjugacy classes of AA and BB 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 pp, that is, Ap=IA^p=I, Bp=IB^p=I and (A,B)≠(I,I)(A,B)\ne(I,I). In this paper “self-equivalence” always means a linear one.

Other papers count the full automorphism group Aut⁡(F)\operatorname{Aut}(F), the group of affine permutations of F22n\mathbb{F}_2^{2n} that preserve the graph of FF [8]. For a quadratic FF, it contains the maps (x,y)↦(x+a,y+DaF(x))(x,y)\mapsto(x+a,y+D_aF(x)), which are affine since DaFD_aF is affine. They form a group of order 2n2^n. If F(Ax)=BF(x)+ℓ(x)F(Ax)=BF(x)+\ell(x) with ℓ\ell affine, then (x,y)↦(Ax,By+ℓ(x))(x,y)\mapsto(Ax,By+\ell(x)) is also in Aut⁡(F)\operatorname{Aut}(F). Composing it with the 2n2^n maps above gives 2n2^n elements with linear parts AA and BB. So ∣Aut⁡(F)∣≥2n∣G∣|\operatorname{Aut}(F)|\ge2^n|G|, where GG is the group of pairs (A,B)(A,B) that satisfy (1). In particular, if ∣Aut⁡(F)∣=2n|\operatorname{Aut}(F)|=2^n, then FF has no nontrivial linear self-equivalence.

For fixed (A,B)(A,B), the polar forms that satisfy (1) form a linear space

W(A,B)={β alternating bilinear:β(Ax,Ay)=B β(x,y)}.W(A,B)=\{\beta\text{ alternating bilinear}:\beta(Ax,Ay)=B\,\beta(x,y)\}.

It is the solution space of a homogeneous linear system with (n2)\binom{n}{2} unknowns, the coordinates of the vectors β(ei,ej)\beta(e_i,e_j), i<ji<j. For n=10n=10 there are 450 unknowns. Every search and every proof in this paper starts from W(A,B)W(A,B).

ppord⁡p(2)\operatorname{ord}_p(2)(p,p)(p,p)(p,1)(p,1)(1,p)(1,p)total
2–255535
32255535
544228
73415551
11101113
1782114
31512355133
73981110
1277181120
all2472626299

Table 2. Number of self-equivalence types of prime order in dimension ten.

Notation

We write Fix⁡(A)=ker⁡(A+I)\operatorname{Fix}(A) = \ker(A + I) for the fixed space of AA. For a polynomial gg we write ker⁡g(A)\ker g(A) for the kernel of gg evaluated at AA. Let AA have odd prime order pp. Then F2n\mathbb{F}_2^n is the direct sum of Fix⁡(A)\operatorname{Fix}(A) and the spaces ker⁡φ(A)\ker\varphi(A). Here φ\varphi runs over the irreducible factors of the cyclotomic polynomial Φp\Phi_p. We call ker⁡φ(A)\ker\varphi(A) the φ\varphi-part of AA. Each factor has degree ord⁡p(2)\operatorname{ord}_p(2), the multiplicative order of 2 modulo pp. We write ω\omega for a primitive element of F4\mathbb{F}_4. We write Tr⁡\operatorname{Tr} for the absolute trace from F2n\mathbb{F}_{2^n} to F2\mathbb{F}_2.

The 299 types

We follow Beierle and Leander [6 Sec. 4.1]. Let pp be a prime. An element of order pp of GL⁡(10,2)\operatorname{GL}(10,2) is described, up to conjugacy, as follows.

  • If pp is odd, it is a block-diagonal matrix. Each block is the companion matrix of an irreducible factor of Φp\Phi_p. An identity block completes the matrix. So the conjugacy class is given by a multiset of factors of Φp\Phi_p of total degree at most 10. All factors have degree d=ord⁡p(2)d = \operatorname{ord}_p(2), so we need d≤10d \le10. This leaves p∈{3,5,7,11,17,31,73,127}p \in\{3, 5, 7, 11, 17, 31, 73, 127\}, with d=2,4,3,10,8,5,9,7d = 2, 4, 3, 10, 8, 5, 9, 7.

  • If p=2p = 2, it is an involution. Its conjugacy class is given by the number k∈{1,…,5}k \in\{1, \ldots, 5\} of Jordan blocks of size two. We write JkJ_k for it. Then dim⁡Fix⁡(Jk)=10−k\dim\operatorname{Fix}(J_k) = 10 - k.

A self-equivalence (A,B)(A, B) of prime order has one of three kinds:

  • (p,p)(p,p), if both AA and BB have order pp;

  • (p,1)(p,1), if B=IB = I;

  • (1,p)(1,p), if A=IA = I.

Conjugating AA and BB independently does not change the EA-class of the functions (Section II). Moreover, (A,B)(A, B) and (Ar,Br)(A^r, B^r) with rr coprime to pp generate the same group. So we also identify pairs up to this power similarity. It permutes the factors of Φp\Phi_p: the factor with root zz goes to the factor with root zrz^r.

Table II gives the number of types. We obtained it by direct enumeration. For each pp, we list the conjugacy classes as above, form all pairs, and count the orbits of the powers r∈(Z/p)∗r \in(\mathbb{Z}/p)^*. The power rr maps a factor of Φp\Phi_p with root zz to the factor with root zrz^r. 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 (p,p)(p,p) 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 AA and BB and compute the space W(A,B)W(A, B) of (1). Its dimension ranges from 0 to 405. Thirty-one types have W(A,B)=0W(A, B) = 0: 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 dim⁡W(A,B)\dim W(A, B). 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 6⋅10726 \cdot10^{72} 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 p=7p = 7, ψ1=x3+x+1\psi_1 = x^3 + x + 1 and ψ3=x3+x2+1\psi_3 = x^3 + x^2 + 1. For p=17p = 17, χ\chi is one of the two factors of degree eight of Φ17\Phi_{17}; power similarity exchanges them. For p=31p = 31, let ζ\zeta be a root of x5+x2+1x^5 + x^2 + 1; then φr\varphi_r is the minimal polynomial of ζr\zeta^r: φ1=x5+x2+1\varphi_1 = x^5 + x^2 + 1, φ3=x5+x4+x3+x2+1\varphi_3 = x^5 + x^4 + x^3 + x^2 + 1, φ5=x5+x4+x2+x+1\varphi_5 = x^5 + x^4 + x^2 + x + 1, φ7=x5+x3+x2+x+1\varphi_7 = x^5 + x^3 + x^2 + x + 1, φ11=x5+x4+x3+x+1\varphi_{11} = x^5 + x^4 + x^3 + x + 1 and φ15=x5+x3+1\varphi_{15} = x^5 + x^3 + 1. The artifact gives the matrices of all 299 types [22].

Some types in plain words

Several types have a simple description in the field F210\mathbb{F}_{2^{10}}. We use the following ones below.

  • Type 24 is (J5,J5)(J_5, J_5). J5J_5 is conjugate to the Frobenius map x↦x32x \mapsto x^{32}. By Lemma 3 below, type 24 is the set of quadratic functions with coefficients in F32\mathbb{F}_{32}, up to EA-equivalence.

  • Type 73 is (A,A)(A, A) with AA of order 5, with two blocks of Φ5\Phi_5 and dim⁡Fix⁡(A)=2\dim\operatorname{Fix}(A) = 2. AA is conjugate to the Frobenius map x↦x4x \mapsto x^4. By Lemma 3, type 73 is the set of quadratic functions with coefficients in F4\mathbb{F}_4, up to EA-equivalence.

  • Type 64 is (A,I)(A, I) with AA the multiplication by ω\omega on F45\mathbb{F}_4^5. These are the functions with F(ωx)=F(x)F(\omega x) = F(x) up to affine terms. They are the quadratic canonical triplicate functions [10, 16, 24].

  • Types 41 and 47 are (A,A)(A, A) with AA of order 3, with two and three blocks of Φ3\Phi_3. So dim⁡Fix⁡(A)\dim\operatorname{Fix}(A) 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 kk divide nn, let ϕ(x)=x2k\phi(x) = x^{2^k} on F2n\mathbb{F}_{2^n}, and let FF be a quadratic function of F2n\mathbb{F}_{2^n}. Write F=Q+LF = Q + L, where QQ collects the terms of the reduced univariate polynomial of FF whose exponents have binary weight two, and LL is affine. Then (ϕ,ϕ)(\phi,\phi) is a self-equivalence of FF if and only if all coefficients of QQ lie in F2k\mathbb{F}_{2^k}. In that case FF is EA-equivalent to QQ, which satisfies Q∘ϕ=ϕ∘QQ \circ\phi= \phi\circ Q exactly.

Proof. Write Q(x)=∑ecexeQ(x) = \sum_e c_e x^e over the exponents ee of binary weight two. Then Q(ϕ(x))+ϕ(Q(x))=∑e(ce+ce2k)x2keQ(\phi(x)) + \phi(Q(x)) = \sum_e(c_e + c_e^{2^k})x^{2^k e}, where 2ke2^k e is reduced modulo 2n−12^n - 1. The map e↦2kee \mapsto2^k e 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 ce∈F2kc_e \in\mathbb{F}_{2^k} for every ee. Since LL is affine, F∘ϕ+ϕ∘FF \circ\phi+ \phi\circ F is affine if and only if Q∘ϕ+ϕ∘QQ \circ\phi+ \phi\circ Q is. □\square

A function has a self-equivalence of type 24 if and only if it is EA-equivalent to one with the self-equivalence (ϕ,ϕ)(\phi,\phi) for k=5k = 5, since ϕ\phi is conjugate to J5J_5. By Lemma 3, these are the quadratic functions with coefficients in F32\mathbb{F}_{32}, up to EA-equivalence. The same holds for type 73 with k=2k = 2 and F4\mathbb{F}_4.

TypeppAABBTypeppAABB
242J5J_5J5J_517531φ12\varphi_1^2φ32\varphi_3^2
473Φ32\Phi_3^2Φ32\Phi_3^217631φ12\varphi_1^2φ3φ5\varphi_3\varphi_5
643Φ52\Phi_5^2II18031φ12\varphi_1^2φ52\varphi_5^2
735Φ52\Phi_5^2Φ52\Phi_5^219831φ1φ3\varphi_1\varphi_3φ1φ5\varphi_1\varphi_5
1167ψ12ψ3\psi_1^2\psi_3ψ12ψ3\psi_1^2\psi_320731φ1φ3\varphi_1\varphi_3φ52\varphi_5^2
12911Φ11\Phi_{11}Φ11\Phi_{11}20831φ1φ3\varphi_1\varphi_3φ5φ7\varphi_5\varphi_7
13217χ\chiχ\chi20931φ1φ3\varphi_1\varphi_3φ5φ11\varphi_5\varphi_{11}
17031φ12\varphi_1^2φ1φ3\varphi_1\varphi_323131φ1φ5\varphi_1\varphi_5φ3φ7\varphi_3\varphi_7
17131φ12\varphi_1^2φ1φ5\varphi_1\varphi_523531φ1φ5\varphi_1\varphi_5φ5φ7\varphi_5\varphi_7
25531φ1φ15\varphi_1\varphi_{15}φ3φ7\varphi_3\varphi_7

Table 3. The 19 types not excluded by proof. For odd pp, a block structure lists the factors of Φp\Phi_p with multiplicity; an identity block completes the matrix. JkJ_k is an involution with kk Jordan blocks of size two, and II the identity.

Excluding types by proof

In this section FF is a quadratic APN function of F2n\mathbb{F}_2^n with polar form β\beta, and (A,B)(A,B) is a self-equivalence of prime order, so (1) holds. The lemmas give necessary conditions on the type of (A,B)(A,B). Each condition can be checked on the matrices A,BA,B or on the space W(A,B)W(A,B). When a condition fails, the type contains no APN function, and no search is needed.

Intertwiners

The first lemma uses the fixed points of AA.

Lemma 4 (Intertwiner lemma). Let x∈Fix⁡(A)x \in\operatorname{Fix}(A), x≠0x \ne0, and let Tx=βxT_x=\beta_x. Then TxA=BTxT_xA=BT_x and ker⁡Tx={0,x}\ker T_x=\{0,x\}.

Consequently:

(i) For every polynomial gg, TxT_x maps ker⁡g(A)\ker g(A) into ker⁡g(B)\ker g(B), and dim⁡ker⁡g(A)−[x∈ker⁡g(A)]≤dim⁡ker⁡g(B)\dim\ker g(A)-[x \in\ker g(A)] \le\dim\ker g(B). Here [x∈V][x \in V] is 1 if x∈Vx \in V and 0 otherwise.

(ii) If pp is odd and Fix⁡(A)≠0\operatorname{Fix}(A)\ne0, then dim⁡ker⁡φ(A)≤dim⁡ker⁡φ(B)\dim\ker\varphi(A)\le\dim\ker\varphi(B) for every irreducible factor φ\varphi of Φp\Phi_p.

(iii) If A=JkAA=J_{k_A} and B=JkBB=J_{k_B} are involutions, then kA≤kBk_A\le k_B if kA<n/2k_A<n/2, and kA−1≤kBk_A-1\le k_B if $k_A=n/2.

Proof. For all yy we have Tx(Ay)=β(Ax,Ay)=Bβ(x,y)=BTx(y)T_x(Ay)=\beta(Ax,Ay)=B\beta(x,y)=BT_x(y), since Ax=xAx=x. The kernel of TxT_x is {0,x}\{0,x\} by Lemma 2. From TxA=BTxT_xA=BT_x we get Txg(A)=g(B)TxT_xg(A)=g(B)T_x, so TxT_x maps ker⁡g(A)\ker g(A) into ker⁡g(B)\ker g(B). Its kernel on ker⁡g(A)\ker g(A) is {0,x}∩ker⁡g(A)\{0,x\}\cap\ker g(A), which gives (i). For (ii), take g=φg=\varphi: then x∉ker⁡φ(A)x\notin\ker\varphi(A), because xx is fixed and φ(1)≠0\varphi(1)\ne0. For (iii), put NA=A+IN_A=A+I and NB=B+IN_B=B+I. Then TxNA=NBTxT_xN_A=N_BT_x, so TxT_x maps Im⁡NA\operatorname{Im}N_A into Im⁡NB\operatorname{Im}N_B, with kernel {0,x}∩Im⁡NA\{0,x\}\cap\operatorname{Im}N_A. We have dim⁡Im⁡NA=kA\dim\operatorname{Im}N_A=k_A and Im⁡NA⊆Fix⁡(A)\operatorname{Im}N_A\subseteq\operatorname{Fix}(A). If kA<n/2k_A<n/2, then Im⁡NA≠Fix⁡(A)\operatorname{Im}N_A\ne\operatorname{Fix}(A), and we may choose x∈Fix⁡(A)∖Im⁡NAx\in\operatorname{Fix}(A)\setminus\operatorname{Im}N_A. This gives kA≤kBk_A\le k_B. If kA=n/2k_A=n/2, every choice gives kA−1≤kBk_A-1\le k_B.

Lemma 4 says that the block structure of AA must fit into that of BB. It does not use the space W(A,B)W(A,B) at all. The next lemma looks at the action of β\beta in the other direction. It fixes a point outside Fix⁡(A)\operatorname{Fix}(A) and reads β\beta on Fix⁡(A)\operatorname{Fix}(A).

Lemma 5 (Dual intertwiner lemma). Let pp be odd, and let φ\varphi be an irreducible factor of Φp\Phi_p with ker⁡φ(A)≠0\ker\varphi(A)\ne0. Then dim⁡Fix⁡(A)≤dim⁡ker⁡φ(B)\dim\operatorname{Fix}(A)\le\dim\ker\varphi(B).

Proof. For z∈Fix⁡(A)z\in\operatorname{Fix}(A) and all uu we have β(Au,z)=β(Au,Az)=Bβ(u,z)\beta(Au,z)=\beta(Au,Az)=B\beta(u,z). So u↦β(u,z)u\mapsto\beta(u,z) intertwines AA and BB, and it maps ker⁡φ(A)\ker\varphi(A) into ker⁡φ(B)\ker\varphi(B). Fix u∈ker⁡φ(A)u\in\ker\varphi(A), u≠0u\ne0. The map z↦β(u,z)z\mapsto\beta(u,z) is linear on Fix⁡(A)\operatorname{Fix}(A), with values in ker⁡φ(B)\ker\varphi(B). Its kernel is contained in {0,u}∩Fix⁡(A)={0}\{0,u\}\cap\operatorname{Fix}(A)=\{0\}, since uu 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 F∘A=B∘FF\circ A=B\circ F exactly. For an APN function with such a nontrivial self-equivalence, the bound reads

dim⁡Fix⁡(A)+dim⁡Fix⁡(B)≤n+1.(2)\dim\operatorname{Fix}(A)+\dim\operatorname{Fix}(B)\le n+1. \tag*{(2)}

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 Fix⁡(A)\operatorname{Fix}(A) with Fix⁡(B)\operatorname{Fix}(B), while Lemma 5 compares Fix⁡(A)\operatorname{Fix}(A) with one part of BB. 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 dim⁡Fix⁡(A)=dim⁡Fix⁡(B)=6\dim\operatorname{Fix}(A)=\dim\operatorname{Fix}(B)=6, so it violates (2). It is also excluded by Lemma 5, since dim⁡ker⁡φ(B)=4<6\dim\ker\varphi(B)=4<6. Neither bound excludes a type beyond Table IV below.

Restriction to an invariant subspace

The values of β\beta on fixed vectors are fixed: for x,y∈Fix⁡(A)x,y\in\operatorname{Fix}(A) we have Bβ(x,y)=β(Ax,Ay)=β(x,y)B\beta(x,y)=\beta(Ax,Ay)=\beta(x,y). So FF restricts to a quadratic APN function from Fix⁡(A)\operatorname{Fix}(A) to Fix⁡(B)\operatorname{Fix}(B), up to affine terms. The next lemma bounds such restrictions.

Lemma 6. Let k≥3k\ge3, and let D⊆F2nD\subseteq\mathbb{F}_2^n be a subspace of dimension kk. Let EE be the span of β(D,D)\beta(D,D). If FF is APN, then dim⁡E≠k−1\dim E\ne k-1.

Proof. For a∈Da \in D, a≠0a \ne0, the restriction of βa\beta_a to DD has kernel {0,a}\{0,a\}, so its image in EE has dimension k−1k-1. Suppose dim⁡E=k−1\dim E=k-1. Then this image is all of EE for every aa. Take a nonzero linear form e∗e^* on EE. The alternating form e∗∘βe^* \circ\beta on DD is nondegenerate. Indeed, if a≠0a \ne0 is in its radical, then e∗e^* vanishes on βa(D)=E\beta_a(D)=E, so e∗=0e^*=0. So the forms e∗∘βe^* \circ\beta, e∗∈E∗e^* \in E^*, make up a space of dimension k−1k-1 of alternating forms on F2k\mathbb{F}_2^k whose nonzero elements are all nondegenerate. If kk is odd, this is impossible, since every alternating form in odd dimension is degenerate. If kk is even, the Pfaffian is a form of degree k/2k/2 in the k−1k-1 coordinates of e∗e^*. Since k/2<k−1k/2<k-1, Chevalley’s theorem [25 Cor. 6.6] gives a nonzero e∗e^* with Pfaffian zero, that is, a degenerate form.

Take D=Fix⁡(A)D=\operatorname{Fix}(A), so that E⊆Fix⁡(B)E \subseteq\operatorname{Fix}(B). The proof shows that EE contains βa(D)\beta_a(D), of dimension dim⁡D−1\dim D-1. So dim⁡Fix⁡(B)=dim⁡Fix⁡(A)−1\dim\operatorname{Fix}(B)=\dim\operatorname{Fix}(A)-1 forces E=Fix⁡(B)E=\operatorname{Fix}(B), which Lemma 6 forbids when dim⁡Fix⁡(A)≥3\dim\operatorname{Fix}(A)\ge3. Together with the obvious bound dim⁡Fix⁡(B)≥dim⁡Fix⁡(A)−1\dim\operatorname{Fix}(B)\ge\dim\operatorname{Fix}(A)-1, this extends Lemma 4 of Beierle and Leander [6], which states dim⁡Fix⁡(B)≥dim⁡Fix⁡(A)\dim\operatorname{Fix}(B)\ge\dim\operatorname{Fix}(A) outside two small cases. The bound on spaces of nondegenerate alternating forms is also noted by Gow [26 Sec. 3]. In the computer check, DD runs over the sums of the subspaces ker⁡(g(A)j)\ker(g(A)^j), where gg is an irreducible factor of xp+1x^p+1 and j∈{1,2}j \in\{1,2\}. These subspaces are invariant under AA. The computer check does not use one candidate β\beta but the whole space W(A,B)W(A,B). It computes EW(D)=span⁡{β(d,e):β∈W(A,B), d,e∈D}E_W(D)=\operatorname{span}\{\beta(d,e):\beta\in W(A,B),\ d,e \in D\} from a basis of W(A,B)W(A,B). For every β∈W(A,B)\beta\in W(A,B) the space EE of Lemma 6 lies in EW(D)E_W(D), and it has dimension at least k−1k-1 if FF is APN. So dim⁡EW(D)≤k−1\dim E_W(D)\le k-1 forces dim⁡E=k−1\dim E=k-1, which the lemma forbids.

Order three

For p=3p=3 we have Φ3=x2+x+1\Phi_3=x^2+x+1, and U=ker⁡(A2+A+I)U=\ker(A^2+A+I) is the part of AA without fixed points.

Lemma 7. Let (A,B)(A,B) have order p=3p=3, so that A3=B3=IA^3=B^3=I, and let U=ker⁡(A2+A+I)U=\ker(A^2+A+I). If FF is APN, then 2dim⁡Fix⁡(B)≥dim⁡U2\dim\operatorname{Fix}(B)\ge\dim U.

Proof. For x∈Ux \in U put q(x)=β(x,Ax)q(x)=\beta(x,Ax). Since A2x=Ax+xA^2x=Ax+x, we get Bq(x)=β(Ax,A2x)=β(Ax,Ax+x)=β(Ax,x)=q(x)Bq(x)=\beta(Ax,A^2x)=\beta(Ax,Ax+x)=\beta(Ax,x)=q(x). So qq maps UU into Fix⁡(B)\operatorname{Fix}(B). If x≠0x \ne0, then xx and AxAx are linearly independent, so q(x)≠0q(x)\ne0 by Lemma 2. So the dim⁡Fix⁡(B)\dim\operatorname{Fix}(B) coordinates of qq are quadratic forms in dim⁡U\dim U variables with only the trivial common zero. By the Chevalley–Warning theorem, 2dim⁡Fix⁡(B)≥dim⁡U2\dim\operatorname{Fix}(B)\ge\dim U.

Odd dimension over F4\mathbb{F}_4

Lemma 8. Let n=2mn=2m with mm odd, and let AA be the multiplication by ω\omega on F4m\mathbb{F}_4^m. Let (A,B)(A,B) have prime order; since AA has order 3, this order is 3, so B3=IB^3=I. If B≠IB\ne I, then no quadratic APN function has the self-equivalence (A,B)(A,B).

Proof. Write the output space as Fix⁡(B)⊕Y\operatorname{Fix}(B)\oplus Y with Y=ker⁡(B2+B+I)Y=\ker(B^2+B+I). Then YY is an F4\mathbb{F}_4-space of dimension r≥1r\ge1, where BB acts as ω\omega, and dim⁡Fix⁡(B)=2m−2r\dim\operatorname{Fix}(B)=2m-2r. Let βω\beta_\omega be the YY-component of β\beta. It satisfies βω(ωx,ωy)=ωβω(x,y)\beta_\omega(\omega x,\omega y)=\omega\beta_\omega(x,y). Extend scalars from F4\mathbb{F}_4 to F4⊗F2F2\mathbb{F}_4\otimes_{\mathbb{F}_2}\mathbb{F}_2. Then the F2\mathbb{F}_2-linear map AA splits the space into its eigenspaces for ω\omega and ω2\omega^2, and so does BB on F4⊗Y\mathbb{F}_4\otimes Y. (On the original F4\mathbb{F}_4-space F4m\mathbb{F}_4^m, AA is a scalar, so this splitting only appears after the extension.) Let xx and yy be eigenvectors of AA for λ\lambda and μ\mu. The ω\omega-eigencomponent of βω(x,y)\beta_\omega(x,y) is nonzero only if λμ=ω\lambda\mu=\omega, that is, λ=μ=ω2\lambda=\mu=\omega^2. In particular βω\beta_\omega vanishes on pairs of eigenvectors for ω\omega and ω2\omega^2, since BB has no eigenvalue 1 on YY. The ω2\omega^2-eigencomponent is the conjugate of the ω\omega-eigencomponent. So βω\beta_\omega is determined by its restriction to the ω2\omega^2-eigenspace, which is an rr-tuple of F4\mathbb{F}_4-bilinear alternating forms in mm variables. In suitable coordinates, βω(x,y)=(c1(xˉ,yˉ),…,cr(xˉ,yˉ))\beta_\omega(x,y)=(c_1(\bar{x},\bar{y}),\ldots,c_r(\bar{x},\bar{y})), where xˉ\bar{x} is the coordinatewise Frobenius image of xx. Since mm is odd, c1c_1 is degenerate. Take a≠0a\ne0 with aˉ\bar{a} in its radical. Then βω(a,⋅)\beta_\omega(a,\cdot) is semilinear over F4\mathbb{F}_4 with image in an F4\mathbb{F}_4-space of dimension at most r−1r-1. So its kernel has dimension at least 2m−2(r−1)2m-2(r-1) over F2\mathbb{F}_2. The Fix⁡(B)\operatorname{Fix}(B)-component adds at most 2m−2r2m-2r linear conditions. So dim⁡ker⁡βa≥2\dim\ker\beta_a\ge2, and FF is not APN.

In dimension ten (m=5m=5), 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 104310^{43} nodes. As a cross-check, an exhaustive search confirms the case m=3m=3 in dimension six.

Criteriontypes
W(A,B)=0W(A, B) = 031
Compression, invariant subspaces (Proposition 9)237
Restriction (Lemma 6)4
Order three (Lemma 7)4
Compression with Wong sequences2
Odd dimension over F4\mathbb{F}_4 (Lemma 8)2
Total280

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 a≠0a \ne0 and a subspace DD, let

E(a,D)=span⁡{β(a,d):β∈W(A,B), d∈D}.E(a, D) = \operatorname{span}\{\beta(a,d) : \beta\in W(A, B),\ d \in D\}.

Proposition 9 (Compression criterion). If some FF with polar form in W(A,B)W(A, B) is APN, then for every a≠0a \ne0 and every subspace DD,

dim⁡D−[a∈D]≤dim⁡E(a,D).\dim D - [a \in D] \le\dim E(a, D).

Proof. The map βa\beta_a sends DD into E(a,D)E(a, D), with kernel {0,a}∩D\{0,a\} \cap D.

Proposition 9 is a computation on W(A,B)W(A, B). By bilinearity, E(a,D)E(a, D) is spanned by the vectors wk(a,dj)w_k(a,d_j), where wkw_k runs over a basis of W(A,B)W(A, B) and djd_j over a basis of DD. A failing pair (a,D)(a,D) is a certificate that the type is empty. The certificate is valid only if the basis spans all of W(A,B)W(A, B), not just a subspace. The artifact therefore stores, for each excluded type, the matrices AA and BB, a basis of W(A,B)W(A, B), and a witness for the first criterion that excludes it. For this criterion and for the Wong-sequence criterion the witness is the pair (a,D)(a,D). For Lemma 6 it is a basis of the subspace, and for Lemma 7 the two dimensions it compares. When W=0W = 0 or Lemma 8 applies, no witness beyond AA, BB and the basis is needed. An independent checker recomputes the rank of the linear system that defines W(A,B)W(A, B) from AA and BB, 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 a∈Fix⁡(A)a \in\operatorname{Fix}(A), D=ker⁡g(A)D = \ker g(A). Lemma 4 (iii) is the case a∈Fix⁡(A)a \in\operatorname{Fix}(A), D=Im⁡(A+I)D = \operatorname{Im}(A + I). Lemma 5 is the case a∈ker⁡φ(A)a \in\ker\varphi(A), D=Fix⁡(A)D = \operatorname{Fix}(A). But the criterion is stronger, since E(a,D)E(a, D) is computed from the actual space W(A,B)W(A, B). We test all a≠0a \ne0 and all sums DD of the subspaces ker⁡(g(A)j)\ker(g(A)^j) as above.

For two types the invariant subspaces are not enough, and we choose DD adapted to aa. Fix aa and a generic map M0=βaM_0 = \beta_a for some β∈W(A,B)\beta\in W(A, B). Let Ma={βa:β∈W(A,B)}\mathcal{M}_a = \{\beta_a : \beta\in W(A, B)\}. The second Wong sequence [27], [28] N0=0N_0 = 0, Ni+1=Ma(M0−1(Ni))N_{i+1} = \mathcal{M}_a(M_0^{-1}(N_i)) is increasing. Here M0−1(N)M_0^{-1}(N) is the full preimage, and Ma(D)\mathcal{M}_a(D) is the span of all M(d)M(d) with M∈MaM \in\mathcal{M}_a, d∈Dd \in D; both are computed by linear algebra from bases. Its limit N∗N^* gives D=M0−1(N∗)D = M_0^{-1}(N^*) with Ma(D)⊆N∗\mathcal{M}_a(D) \subseteq N^*. We then check Proposition 9 for this DD directly. So the result is a certificate even though M0M_0 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 Fix⁡(A)\operatorname{Fix}(A) alone already exclude 170 types, using only the matrices AA and BB. 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 (A,B)(A,B) and a basis w1,…,wdw_1,\ldots,w_d of W(A,B)W(A,B). A polar form in W(A,B)W(A,B) is β=∑ktkwk\beta=\sum_k t_kw_k with t∈F2dt\in\mathbb{F}_2^d. The 450 unknowns are the coordinates β(ei,ej)r\beta(e_i,e_j)_r, ordered first by the pair (i,j)(i,j) in the order (0,1)(0,1), (0,2)(0,2), (1,2)(1,2), (0,3)(0,3), …\ldots and then by the output coordinate r=0,…,9r=0,\ldots,9. We put the basis in reduced echelon form with respect to this order, with the pivot of wkw_k at its first nonzero unknown. We say that the pivot of wkw_k is at the pair (i,j)(i,j) of that unknown. Then the value β(ei,ej)\beta(e_i,e_j) depends only on the coefficients tkt_k whose pivot is at or before the pair (i,j)(i,j).

The search follows the variable approach of earlier work [6], [29]. Level ss adds the input vector ese_s. Within a level, the pairs (0,s),(1,s),…,(s−1,s)(0,s),(1,s),\ldots,(s-1,s) are filled in order. At each pair, the coefficients with a pivot there are chosen in all possible ways. Let Vs=span⁡{e0,…,es−1}V_s=\operatorname{span}\{e_0,\ldots,e_{s-1}\}. By Lemma 2, FF is APN on Vs+1V_{s+1} if and only if it is APN on VsV_s and

β(a,es)∉βa(Vs)for every a∈Vs, a≠0.(3)\beta(a,e_s)\notin\beta_a(V_s)\qquad\text{for every }a\in V_s,\ a\ne0. \tag*{(3)}

Indeed, let x,y∈Vs+1x,y\in V_{s+1} be linearly independent. If both lie in VsV_s, the condition on VsV_s applies. If exactly one, say xx, lies in VsV_s, write y=v+esy=v+e_s with v∈Vsv\in V_s; then β(x,y)=βx(v)+β(x,es)\beta(x,y)=\beta_x(v)+\beta(x,e_s), which is nonzero by (3) with a=xa=x. If neither lies in VsV_s, then x+y∈Vsx+y\in V_s is nonzero and β(x,y)=β(x,x+y)\beta(x,y)=\beta(x,x+y), which is the previous case. Condition (3) is tested for aa as soon as β(ei,es)\beta(e_i,e_s) is known for the highest index ii in aa. We keep a reduced echelon basis of each space βa(Vs)\beta_a(V_s), so each test takes at most nn steps. A leaf of the tree is a quadratic APN function of F210\mathbb{F}_2^{10} with the self-equivalence (A,B)(A,B).

Using the centralizers

The centralizers C(A)C(A) and C(B)C(B) act on W(A,B)W(A,B) by β↦Sβ(T⋅,T⋅)\beta\mapsto S\beta(T\cdot,T\cdot) with T∈C(A)T\in C(A), S∈C(B)S\in C(B). 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 β(e0,e1)\beta(e_0,e_1) is restricted to representatives of the orbits of C(B)C(B) on nonzero vectors.

  • Output side. On the first pairs, the search keeps only values that are lexicographically least under a stabilizer chain in C(B)C(B). This comparison uses a different order from the echelon form above. Each value β(ei,ej)∈F210\beta(e_i,e_j)\in\mathbb{F}_2^{10} 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 T∈C(A)T\in C(A) that preserve VsV_s, 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 TT preserves VsV_s. 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 Im⁡(A+I)\operatorname{Im}(A+I), then Fix⁡(A)\operatorname{Fix}(A), 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 1.8⋅10441.8\cdot10^{44} to 1.9⋅1081.9\cdot10^8 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 cx3cx^3 gives exactly 1023 APN functions, and one after normalization. The space of all cx5cx^5 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 (7.9⋅1067.9 \cdot10^6 nodes) and with both reductions (2.9⋅1042.9 \cdot10^4 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 FF 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 FF, 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 L1L_1, L2L_2 and affine L3L_3 with G=L1∘F∘L2+L3G = L_1 \circ F \circ L_2 + L_3. The search builds L2L_2 one basis vector at a time and derives L1L_1 by linear algebra. Two observations reduce the cost of a test.

  • Kernel partners. For a quadratic APN function, every nonzero linear form vv defines a component whose polar form has a radical KvFK^F_v. If G=L1∘F∘L2+L3G = L_1 \circ F \circ L_2 + L_3, then KvG=L2−1(KL1TvF)K^G_v = L_2^{-1}(K^F_{L_1^Tv}). So L2L_2 maps the points that share a radical with yy onto the points that share a radical with L2yL_2y. 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 x↦axx \mapsto ax act transitively on the nonzero inputs. So the image of the first basis vector can be fixed.

Each certificate (L1,L2,L3)(L_1,L_2,L_3) is checked independently by recomputing L1∘F∘L2+L3L_1 \circ F \circ L_2 + L_3. 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 x3x^3 took more than ten minutes.

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.

Typeppleavesclassesnames
129112504Gold x3x^3, x9x^9, Beierle–Leander #5, F13
17031338 2721F3
17131338 2721F3
17531492 0321Gold x3x^3
176313 189 28011Beierle–Leander #3, six F12, four F13
18031492 0321Gold x9x^9
231319611Beierle–Leander #1
7354 53624see 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 F4\mathbb{F}_4

Type 73 is the set of quadratic functions of F210\mathbb{F}_{2^{10}} with coefficients in F4\mathbb{F}_4, up to EA-equivalence (Section III). This is the case (n,m)=(10,2)(n,m)=(10,2) 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 1.9⋅10121.9 \cdot10^{12} 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 F210\mathbb{F}_{2^{10}} with all coefficients in F4\mathbb{F}_4. Twenty of them are published classes. Four are new.

Type 73 contains 20 published classes. Nine of them are the Gold functions x3x^3 and x9x^9, 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 MM by listing all linear subspaces of N\mathcal{N} of dimension up to five; the artifact recomputes it. All four classes have M<5M < 5, 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 F4\mathbb{F}_4. These representatives are listed in Appendix A and in the artifact [22].

Type 24: coefficients in F32\mathbb{F}_{32}

Type 24 is the set of quadratic functions of F210\mathbb{F}_{2^{10}} with coefficients in F32\mathbb{F}_{32}. It has a special role for the big APN problem. In dimension six, the quadratic APN functions with coefficients in F8\mathbb{F}_8 form exactly two EA-classes: the Gold class and the class of Kim’s function. Kim’s function is x3+x10+x24x^3+x^{10}+x^{24} on F64\mathbb{F}_{64}, with gg a primitive element. Its coefficients are not in F8\mathbb{F}_8, but its EA-class contains ax5+ax33+x40ax^5+ax^{33}+x^{40} with a=g54∈F8a=g^{54}\in\mathbb{F}_8, where gg is a root of x6+x4+x3+x+1x^6+x^4+x^3+x+1; we checked an explicit certificate. Kim’s function is CCZ-equivalent to Dillon’s APN permutation [13]. The next lemma shows that the bound M≥n/2M\ge n/2 never rules out this case.

Lemma 11. Let n=2mn=2m with mm odd, and let FF be a quadratic function of F2n\mathbb{F}_{2^n} with all coefficients in F2m\mathbb{F}_{2^m}. Then the components Tr⁡(cF)\operatorname{Tr}(cF) with c∈F2m∗c\in\mathbb{F}_{2^m}^{*} are not bent. In particular M≥n/2M\ge n/2.

Proof. Let A=BA=B be the Frobenius x↦x2mx\mapsto x^{2^m}, so that (1) holds. Put ϵ=A+I\epsilon=A+I. Expanding β(Ax,Ay)=Bβ(x,y)\beta(Ax,Ay)=B\beta(x,y) gives β(ϵx,y)+β(x,ϵy)+β(ϵx,ϵy)=ϵβ(x,y)\beta(\epsilon x,y)+\beta(x,\epsilon y)+\beta(\epsilon x,\epsilon y)=\epsilon\beta(x,y). With x=ϵux=\epsilon u and ϵ2=0\epsilon^2=0 this becomes β(ϵu,y)=ϵβ(ϵu,y)\beta(\epsilon u,y)=\epsilon\beta(\epsilon u,y). Let cc be a linear form with c∘ϵ=0c \circ\epsilon= 0; these are the forms Tr⁡(c⋅)\operatorname{Tr}(c \cdot) with c∈F2mc \in\mathbb{F}_{2^m}. Put b=c∘βb = c \circ\beta and γ(u,v)=b(ϵu,v)\gamma(u,v) = b(\epsilon u,v). Then: (a) b(ϵu,ϵv)=0b(\epsilon u,\epsilon v) = 0; since ker⁡ϵ=Fix⁡(A)\ker\epsilon= \operatorname{Fix}(A), this shows that γ\gamma is defined on the quotient F2n/Fix⁡(A)\mathbb{F}_2^n / \operatorname{Fix}(A) in both arguments, and this quotient has dimension mm; (b) γ(u,v)+γ(v,u)=b(ϵu,ϵv)=0\gamma(u,v) + \gamma(v,u) = b(\epsilon u,\epsilon v) = 0 by the same identity, so γ\gamma is symmetric; (c) γ(u,u)=c(β(ϵu,u))=0\gamma(u,u) = c(\beta(\epsilon u,u)) = 0, since β(ϵu,u)=β(Au,u)\beta(\epsilon u,u) = \beta(Au,u) lies in Fix⁡(B)\operatorname{Fix}(B), and Fix⁡(B)=Im⁡ϵ⊆ker⁡c\operatorname{Fix}(B) = \operatorname{Im}\epsilon\subseteq\ker c. So γ\gamma is alternating in odd dimension mm, hence degenerate. Take u∉Fix⁡(A)u \notin\operatorname{Fix}(A) in its radical. Then ϵu≠0\epsilon u \ne0 is in the radical of bb.

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 9⋅10269 \cdot10^{26} nodes for the generic search, even with a fixed Gold prefix. We use a normal form instead.

Write x=(s,t)x = (s,t) with s,t∈F25s,t \in\mathbb{F}_2^5, and choose bases such that A(s,t)=(s,s+t)A(s,t) = (s,s+t) and B=AB = A on the output. Then Fix⁡(A)={(0,t)}\operatorname{Fix}(A) = \{(0,t)\}.

Lemma 12 (Normal form). Every quadratic APN function with a self-equivalence of type 24 is EA-equivalent to a function

F(s,t)=(G(s)+ν(s,s)+μ(s,t), R(s)+ν(t,s)+G(t)),(4)F(s,t) = \left(G(s) + \nu(s,s) + \mu(s,t),\ R(s) + \nu(t,s) + G(t)\right), \tag*{(4)}

where GG is the Gold function x3x^3 or x5x^5 of F32\mathbb{F}_{32}, μ\mu is the polar form of GG, ν\nu is a bilinear map, and RR is a quadratic map with polar form ρ\rho. Conversely, every function (4) has the self-equivalence (A,A)(A,A).

Proof. Write β=(β1,β2)\beta= (\beta_1,\beta_2) for the two output halves, and βi((a,b),(u,c))=Xi(a,u)+Yi(a,c)+Yi(u,b)+Zi(b,c)\beta_i((a,b),(u,c)) = X_i(a,u) + Y_i(a,c) + Y_i(u,b) + Z_i(b,c) with bilinear Xi,Yi,ZiX_i,Y_i,Z_i. The equation β(Ax,Ay)=Aβ(x,y)\beta(Ax,Ay) = A\beta(x,y) has two halves. The first half reads β1(Ax,Ay)=β1(x,y)\beta_1(Ax,Ay) = \beta_1(x,y). Expanding, it gives Z1=0Z_1 = 0 and Y1(a,u)+Y1(u,a)=0Y_1(a,u) + Y_1(u,a) = 0. The second half reads β2(Ax,Ay)+β2(x,y)=β1(x,y)\beta_2(Ax,Ay) + \beta_2(x,y) = \beta_1(x,y). Expanding, it gives Y1=Z2Y_1 = Z_2 and X1(a,u)=Y2(a,u)+Y2(u,a)+Z2(a,u)X_1(a,u) = Y_2(a,u) + Y_2(u,a) + Z_2(a,u). The maps X2X_2, Y2Y_2 and Z2Z_2 are free.

The restriction t↦F(0,t)t \mapsto F(0,t) has polar form (0,Z2)(0,Z_2). By Lemma 2, Z2Z_2 is the polar form of a quadratic APN function of F25\mathbb{F}_2^5. By the classification of the APN functions of F25\mathbb{F}_2^5 [30], a quadratic one is EA-equivalent to x3x^3 or x5x^5. The maps (s,t)↦(Ls,Lt)(s,t) \mapsto(Ls,Lt) with L∈GL⁡(5,2)L \in\operatorname{GL}(5,2) commute with AA. Applying such maps on the input and the output, we may assume Z2=μZ_2 = \mu. Put ν(c,u)=Y2(u,c)\nu(c,u) = Y_2(u,c) and ρ=X2\rho= X_2. Then β1((a,b),(u,c))=μ(a,u)+ν(a,u)+ν(u,a)+μ(a,c)+μ(b,u)\beta_1((a,b),(u,c)) = \mu(a,u) + \nu(a,u) + \nu(u,a) + \mu(a,c) + \mu(b,u) and β2((a,b),(u,c))=ρ(a,u)+ν(b,u)+ν(c,a)+μ(b,c)\beta_2((a,b),(u,c)) = \rho(a,u) + \nu(b,u) + \nu(c,a) + \mu(b,c). 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 ν\nu (125 bits) and the alternating form ρ\rho (50 bits). The next lemma turns APN into one condition per plane on ρ\rho. A plane is a 2-dimensional subspace of F25\mathbb{F}_2^5.

Lemma 13 (Planes). Let FF be as in (4). For linearly independent u,v∈F25u,v \in\mathbb{F}_2^5, let Σ(u,v)\Sigma(u,v) be the set of values ν(b,v)+ν(c,u)+μ(b,c)\nu(b,v) + \nu(c,u) + \mu(b,c), over all b,c∈F25b,c \in\mathbb{F}_2^5 with μ(u,v)+ν(v,u)+ν(u,v)+μ(u,v)=0\mu(u,v) + \nu(v,u) + \nu(u,v) + \mu(u,v) = 0. For a plane PP, let Forb⁡(P)\operatorname{Forb}(P) be the union of Σ(u,v)\Sigma(u,v) over the three bases {u,v}\{u,v\} of PP. Then FF is APN if and only if

(i) ν(b,b)∉Im⁡μ(b,⋅)\nu(b,b) \notin\operatorname{Im}\mu(b,\mathord\cdot) for every b≠0b \ne0, and

(ii) ρ(u,v)∉Forb⁡(P)\rho(u,v) \notin\operatorname{Forb}(P) for every plane P=⟨u,v⟩P = \langle u,v\rangle.

Proof. Since ρ\rho is alternating, ρ(u,v)=ρ(u,u+v)=ρ(u+v,v)\rho(u,v) = \rho(u,u+v) = \rho(u+v,v), so ρ(u,v)\rho(u,v) depends only on PP. By Lemma 2, FF is APN if and only if β(x,y)≠0\beta(x,y) \ne0 for all linearly independent x=(a,b)x = (a,b) and y=(u,c)y = (u,c). We use the formulas for β1\beta_1 and β2\beta_2 from the proof of Lemma 12.

Case a=u=0a = u = 0. Then β(x,y)=(0,μ(b,c))\beta(x,y) = (0,\mu(b,c)), which is nonzero since GG is APN.

Case a=0a = 0, u≠0u \ne0. Then b≠0b \ne0, and β1=μ(b,u)\beta_1 = \mu(b,u) vanishes only for u=bu = b. For u=bu = b we get β2=ν(b,b)+μ(b,c)\beta_2 = \nu(b,b) + \mu(b,c). So β(x,y)≠0\beta(x,y) \ne0 for all such yy if and only if (i) holds for bb. The case a≠0a \ne0, u=0u = 0 is the same, since β\beta is symmetric.

Case a=u≠0a = u \ne0. Then β(x,y)=β(x,x+y)\beta(x,y) = \beta(x,x+y), and x+y=(0,b+c)x+y = (0,b+c). This is the previous case.

Case a,ua,u independent. They span a plane PP, and β2=ρ(a,u)+ν(b,u)+ν(c,a)+μ(b,c)\beta_2 = \rho(a,u) + \nu(b,u) + \nu(c,a) + \mu(b,c). So β(x,y)=0\beta(x,y) = 0 for some b,cb,c if and only if ρ(a,u)∈Σ(a,u)\rho(a,u) \in\Sigma(a,u). Since β\beta is symmetric, Σ(a,u)=Σ(u,a)\Sigma(a,u) = \Sigma(u,a). The ordered pairs (a,u)(a,u) of independent vectors of PP give the three bases of PP. So this case is exactly (ii).

Lemma 13 turns APN into one “avoid a set” condition per plane on ρ\rho. There are 155 planes in F25\mathbb{F}_2^5. The search uses two groups of transformations that preserve the normal form (4) and the EA-class.

Translations of ν\nu. For Y,Y′∈M5(F2)Y,Y' \in M_5(\mathbb{F}_2), the maps (s,t)↦(s,t+Ys)(s,t) \mapsto(s,t+Ys) on the input and (u,v)↦(u,v+Y′u)(u,v) \mapsto(u,v+Y'u) on the output commute with AA. They keep GG and μ\mu, change ρ\rho, and replace ν\nu by ν+θ\nu+\theta with θ(x,y)=μ(x,Yy)+Y′μ(x,y)\theta(x,y)=\mu(x,Yy)+Y'\mu(x,y). These θ\theta form a space TT of dimension 49. So only the coset ν+T\nu+T matters. We take the unique element of the coset that vanishes on the pivot coordinates of a reduced echelon basis of TT. This leaves 45 free bits for ν\nu after condition (i) of Lemma 13. Under a translation, (b,c)↦(b+Yu,c+Yv)(b,c) \mapsto(b+Yu,c+Yv) is a bijection of the solutions in the definition of Σ(u,v)\Sigma(u,v), and Σ(u,v)\Sigma(u,v) is shifted by a vector that depends only on the plane ⟨u,v⟩\langle u,v\rangle.

Automorphisms of GG. The maps L(x)=λx2kL(x)=\lambda x^{2^k} (λ∈F32∗\lambda\in\mathbb{F}_{32}^{*}, 0≤k<50 \le k < 5) satisfy G∘L=N∘GG \circ L=N \circ G for a linear NN. Such a map sends FF to F′=diag⁡(N−1,N−1)∘F∘diag⁡(L,L)F'=\operatorname{diag}(N^{-1},N^{-1})\circ F\circ\operatorname{diag}(L,L). Both coordinate changes commute with AA, and F′F' keeps μ\mu, since N−1μ(Lx,Ly)=μ(x,y)N^{-1}\mu(Lx,Ly)=\mu(x,y). It replaces ν\nu by ν′(x,y)=N−1ν(Lx,Ly)\nu'(x,y)=N^{-1}\nu(Lx,Ly). Hence Forb⁡F′(P)=N−1Forb⁡F(LP)\operatorname{Forb}_{F'}(P)=N^{-1}\operatorname{Forb}_F(LP), with the three parts permuted.

Lemma 14. The 155 maps x↦λx2kx \mapsto\lambda x^{2^k} act regularly on the 155 planes of F32\mathbb{F}_{32}.

Proof. It suffices to show that only the identity fixes a plane PP. Let g≠id⁡g \ne\operatorname{id} fix PP. The group has order 155, which is prime to 3!3!. So gg fixes each of the three nonzero points of PP. If k=0k=0, then λa=a\lambda a=a for a≠0a \ne0, so λ=1\lambda=1. If k≠0k \ne0, the nonzero fixed points satisfy x2k−1=λ−1x^{2^k-1}=\lambda^{-1}. Since gcd⁡(2k−1,31)=1\gcd(2^k-1,31)=1, this has exactly one solution, so gg has at most one nonzero fixed point.

The key of a plane. For each plane PP we compute a key: the size of Forb⁡(P)\operatorname{Forb}(P), 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 PP is unchanged by translations of ν\nu, and key⁡F′(P)=key⁡F(LP)\operatorname{key}_{F'}(P)=\operatorname{key}_F(LP) after an automorphism. Moreover Forb⁡(P)\operatorname{Forb}(P) depends only on the columns ν(⋅,w)\nu(\mathord\cdot,w) with w∈Pw \in P. So the keys of the planes inside span⁡{e0,…,ej}\operatorname{span}\{e_0,\ldots,e_j\} are fixed once the first j+1j+1 columns of ν\nu are chosen.

The solver. It runs for G=x3G=x^3 and G=x9G=x^9 separately.

  1. Choose the columns ν(⋅,e0)\nu(\mathord\cdot,e_0), ν(⋅,e1)\nu(\mathord\cdot,e_1), ν(⋅,e2)\nu(\mathord\cdot,e_2) 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 ⟨e0,e1⟩\langle e_0,e_1\rangle.

  2. List all values of ρ\rho on span⁡{e0,e1,e2}\operatorname{span}\{e_0,e_1,e_2\} that satisfy condition (ii) on its planes.

  3. Choose column ν(⋅,e3)\nu(\mathord\cdot,e_3), apply the key test, and extend ρ\rho to span⁡{e0,…,e3}\operatorname{span}\{e_0,\ldots,e_3\}.

  4. For each option of column ν(⋅,e4)\nu(\mathord\cdot,e_4), extend ρ\rho to F25\mathbb{F}_2^5 and check condition (ii) on the remaining planes.

  5. Every complete (ν,ρ)(\nu,\rho) is a leaf. Its lookup table is rebuilt from (4) and checked to be APN.

Coverage. Let FF be APN of type 24. By Lemma 12, it is EA-equivalent to a function (4). Choose a plane P0P_0 of smallest key. By Lemma 14, there is exactly one automorphism LL of GG with L⟨e0,e1⟩=P0L\langle e_0,e_1\rangle=P_0. For the resulting F′F' we have key⁡F′(⟨e0,e1⟩)=key⁡F(P0)≤key⁡F(LP)=key⁡F′(P)\operatorname{key}_{F'}(\langle e_0,e_1\rangle)=\operatorname{key}_F(P_0)\le\operatorname{key}_F(LP)=\operatorname{key}_{F'}(P) for every plane PP. Then reduce ν\nu modulo TT; this does not change any key. The result has ⟨e0,e1⟩\langle e_0,e_1\rangle 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 GG, job r∈{0,…,2047}r \in\{0,\ldots,2047\} keeps the options of column 1 whose index is congruent to rr 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 ρ\rho is extended to all of F25\mathbb{F}_2^5.

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 GG. The production solver recovers x3x^3, x9x^9 and x3+Tr⁡(x9)x^3+\operatorname{Tr}(x^9) from every position allowed by the key rule.

Theorem 15 (computer-assisted). Up to EA-equivalence, there are exactly three quadratic APN functions of F210\mathbb{F}_{2^{10}} with all coefficients in F32\mathbb{F}_{32}: x3x^3, x9x^9, and x3+Tr⁡(x9)x^3+\operatorname{Tr}(x^9).

All three have M=5M=5. Since F2⊂F32\mathbb{F}_2 \subset\mathbb{F}_{32}, Theorem 15 also covers the quadratic APN functions with coefficients in F2\mathbb{F}_2. All classes of Theorem 15 have representatives with coefficients in F2\mathbb{F}_2. 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, A=BA=B has order three, with U=ker⁡(A2+A+I)≅F43U=\ker(A^2+A+I)\cong\mathbb{F}_4^3 and Z=Fix⁡(A)Z=\operatorname{Fix}(A) of dimension four. Equivariance leaves four blocks of β\beta. The block on U×UU\times U is a pair (κ,h)(\kappa,h), with κ\kappa into UU and hh into ZZ. The block on U×ZU\times Z is an intertwiner τ(u,z)=Tzu\tau(u,z)=T_z u into UU, which is F4\mathbb{F}_4-linear in uu. The block on Z×ZZ\times Z is the polar form QQ of a quadratic function from ZZ to ZZ.

Lemma 16. If a function of type 47 is APN, then for every u∈Uu\in U, u≠0u\ne0: rank⁡h(u,⋅)≥3\operatorname{rank}h(u,\cdot)\ge3, and {x∈U:h(u,x)=0, κ(u,x)=0}={0,u}\{x\in U:h(u,x)=0,\ \kappa(u,x)=0\}=\{0,u\}.

Proof. The ZZ-part of β((u,0),⋅)\beta((u,0),\cdot) is h(u,⋅)h(u,\cdot), and its UU-part has rank at most dim⁡U=6\dim U=6. APN needs rank 9, so rank⁡h(u,⋅)≥3\operatorname{rank}h(u,\cdot)\ge3. The second condition is Lemma 2 restricted to UU.

We now describe the search. Identify UU with F43\mathbb{F}_4^3, with AA acting as ω\omega. The block hh has four F2\mathbb{F}_2-valued coordinates, and each is of the form hi(x,y)=Tr⁡4/2(x∗Miy)h_i(x,y)=\operatorname{Tr}_{4/2}(x^*M_i y) with MiM_i a 3×33\times3 Hermitian matrix over F4\mathbb{F}_4. Up to linear maps on the output ZZ, only the span SS of M1,…,M4M_1,\ldots,M_4 matters. The block κ\kappa is F4\mathbb{F}_4-bilinear in (xˉ,yˉ)(\bar{x},\bar{y}) and alternating, so it factors through the cross product: κ(x,y)=KT(xˉ×yˉ)\kappa(x,y)=K^{\mathsf{T}}(\bar{x}\times\bar{y}) for a 3×33\times3 matrix KK over F4\mathbb{F}_4. An F4\mathbb{F}_4-linear output map RR sends KK to KRTKR^{\mathsf{T}}, so only the column space VV of KK matters. Since (Px‾)×(Py‾)=det⁡(Pˉ)Pˉ−T(xˉ×yˉ)(\overline{P x})\times(\overline{P y})=\det(\bar{P})\bar{P}^{-\mathsf{T}}(\bar{x}\times\bar{y}), an input map PP sends KK to det⁡(Pˉ)Pˉ−1K\det(\bar{P})\bar{P}^{-1}K. An input map P∈GL⁡(3,4)P\in\operatorname{GL}(3,4) acts by S↦P∗SPS\mapsto P^*SP and V↦Pˉ−1VV\mapsto\bar{P}^{-1}V. For x∈Ux\in U we have β(x,ωx)=(0,h(x,ωx))\beta(x,\omega x)=(0,h(x,\omega x)), and hi(x,ωx)h_i(x,\omega x) vanishes for all ii exactly when x∗Mix=0x^*M_i x=0 for all ii. So APN requires SS to be anisotropic: x∗Mx=0x^*Mx=0 for all M∈SM\in S only if x=0x=0.

  1. Pairs (S,V)(S,V). We list every subspace S⊆Herm⁡3(F4)S\subseteq\operatorname{Herm}_3(\mathbb{F}_4) of dimension at most four, keep the anisotropic ones, and sort them into GL⁡(3,4)\operatorname{GL}(3,4)-orbits. Each orbit is checked to be complete: we compute the stabilizer of SS by brute force over all 181,440 elements of GL⁡(3,4)\operatorname{GL}(3,4), and check ∣Stab⁡(S)∣⋅∣orbit⁡∣=∣GL⁡(3,4)∣|\operatorname{Stab}(S)|\cdot|\operatorname{orbit}|=|\operatorname{GL}(3,4)|. This gives 34 orbits of SS. For each, we split the F4\mathbb{F}_4-subspaces VV of F43\mathbb{F}_4^3 into orbits of Stab⁡(S)\operatorname{Stab}(S). This gives 806 classes of pairs (S,V)(S,V) with SS anisotropic.

  1. Lemma 16. It removes 703 classes; 103 remain.

  1. Normal form of τ\tau. Fix the point f0=(1,0,0)∈Uf_0=(1,0,0)\in U. The map z↦τ(f0,z)z\mapsto\tau(f_0,z) is injective, since β(f0,z)≠0\beta(f_0,z)\ne0 for z≠0z\ne0. Its image XX is a 4-dimensional F2\mathbb{F}_2-subspace of UU, and APN at f0f_0 requires X∩κ(f0,ker⁡h(f0,⋅))=0X\cap\kappa(f_0,\ker h(f_0,\cdot))=0. Input maps on ZZ act freely on the bases of XX, so we may choose the basis z1,…,z4z_1,\ldots,z_4 of ZZ such that τ(f0,zi)\tau(f_0,z_i) is the reduced echelon basis of XX. The F4\mathbb{F}_4-linear output maps that fix κ\kappa act on the possible XX; we keep one representative per orbit, the one with the smallest bitset. A slice is a class of step 2 together with one representative XX. There are 8,056 slices.

  1. Completion. In each slice, the solver enumerates all remaining values of τ\tau and all QQ, 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 AA, to one whose pair (S,V)(S,V) is one of the 806 representatives. By Lemma 16 it is one of the 103. Changing the basis of ZZ and applying an output map that fixes κ\kappa, we reach a slice. The solver is exhaustive within a slice.

The solver was validated on the analogue in dimension six, with U≅F22U\cong\mathbb{F}_2^2 and dim⁡Z=2\dim Z=2. There we fixed the blocks (κ,h)(\kappa,h) of x3x^3 and compared with a brute force over all 2182^{18} completions (τ,Q)(\tau,Q). The brute force finds 144 APN completions, and 6 after the same normalization of τ\tau; the solver finds the same 6, all with the ortho-derivative spectrum of x3x^3. 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 (τ,Q)(\tau,Q) reaches the last level.

Theorem 17 (computer-assisted). No quadratic APN function of F210\mathbb{F}_2^{10} has a self-equivalence of type 47.

The open type: canonical triplicate functions

In type 64, AA is the multiplication by ω\omega on F210=F45\mathbb{F}_2^{10}=\mathbb{F}_4^5 and B=IB=I. So the functions satisfy F(ωx)=F(x)F(\omega x)=F(x), 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 x∗x^* for the conjugate transpose of x∈F45x \in\mathbb{F}_4^5, where conjugation is z↦z2z \mapsto z^2. Let Herm⁡5(F4)\operatorname{Herm}_5(\mathbb{F}_4) be the space of 5×55 \times5 Hermitian matrices over F4\mathbb{F}_4. It is a vector space of dimension 25 over F2\mathbb{F}_2. For H∈Herm⁡5(F4)H \in\operatorname{Herm}_5(\mathbb{F}_4), the map x↦x∗Hxx \mapsto x^*Hx takes values in F2\mathbb{F}_2, and it is invariant under x↦ωxx \mapsto\omega x. Its polar form is (q,x)↦Tr⁡4/2((Hq)∗x)(q,x) \mapsto\operatorname{Tr}_{4/2}((Hq)^*x), where Tr⁡4/2(z)=z+z2\operatorname{Tr}_{4/2}(z)=z+z^2. This polar form is zero only for H=0H=0. So H↦x∗HxH \mapsto x^*Hx is injective modulo affine terms. The quadratic Boolean functions invariant under x↦ωxx \mapsto\omega x, modulo affine terms, also form a space of dimension 25: type 64 has dim⁡W(A,B)=250\dim W(A,B)=250, that is, 25 for each of the ten output coordinates. So these Boolean functions are exactly the Hermitian forms x∗Hxx^*Hx, up to affine terms. So a function of type 64 is given by ten Hermitian matrices H1,…,H10H_1,\ldots,H_{10}:

F(x)=(x∗H1x,…,x∗H10x).F(x)=(x^*H_1x,\ldots,x^*H_{10}x).

Up to EA-equivalence, only their F2\mathbb{F}_2-span VV matters. If FF is APN, then dim⁡V=10\dim V=10. Indeed, the coordinates of FF are linearly independent modulo affine functions exactly when the values of β\beta span F210\mathbb{F}_2^{10}. They span a space of dimension at least 9, since βa\beta_a has rank 9 for a≠0a\ne0, and Lemma 6 with D=F210D=\mathbb{F}_2^{10} excludes dimension 9. On Herm⁡5(F4)\operatorname{Herm}_5(\mathbb{F}_4) we use the nondegenerate F2\mathbb{F}_2-bilinear form ⟨H,K⟩=tr⁡(HK)\langle H,K\rangle=\operatorname{tr}(HK), where tr⁡\operatorname{tr} is the matrix trace, and we write C=V⊥C=V^\perp. Note that x∗Hx=⟨H,xx∗⟩x^*Hx=\langle H,xx^*\rangle.

Proposition 18. Let FF be of type 64 with dim⁡V=10\dim V=10. The following are equivalent.

  1. FF is APN.

  2. Every point of PG⁡(4,4)\operatorname{PG}(4,4) is annihilated by exactly one nonzero matrix of VV.

  3. FF is 3-to-1 on F45∖{0}\mathbb{F}_4^5\setminus\{0\}, with nonzero values.

  4. The space CC contains no nonzero matrix of rank at most two.

Proof. (1)⇔\Leftrightarrow(2). Fix q≠0q\ne0 and consider the F2\mathbb{F}_2-linear map Φq:V→F45\Phi_q:V\to\mathbb{F}_4^5, H↦HqH\mapsto Hq. Since the trace form on F45\mathbb{F}_4^5 is nondegenerate over F2\mathbb{F}_2, the rank of βq\beta_q equals dim⁡Φq(V)=10−dim⁡ker⁡Φq\dim\Phi_q(V)=10-\dim\ker\Phi_q. By Lemma 2, FF is APN if and only if rank⁡βq=9\operatorname{rank}\beta_q=9 for all q≠0q\ne0, that is, if and only if exactly one nonzero H∈VH\in V satisfies Hq=0Hq=0. This condition depends only on the point F4q\mathbb{F}_4q.

(3)⇔\Leftrightarrow(4). We have F(y)=F(z)F(y)=F(z) if and only if ⟨H,yy∗+zz∗⟩=0\langle H,yy^*+zz^*\rangle=0 for all H∈VH\in V, that is, yy∗+zz∗∈Cyy^*+zz^*\in C. Similarly F(y)=0F(y)=0 if and only if yy∗∈Cyy^*\in C. Over F4\mathbb{F}_4, the Hermitian matrices of rank one are the yy∗yy^*, and those of rank two are the yy∗+zz∗yy^*+zz^* with y,zy,z independent, since Hermitian forms of a given rank are congruent. Since F(ωy)=F(y)F(\omega y)=F(y), every nonzero fiber has at least three elements. So (3) says that CC has no element of rank one or two.

(1)⇔\Leftrightarrow(3) is the criterion of Budaghyan, Ivkovic and Kaleyski for triplicate functions [10 Thm. 1]. Its hypotheses hold: F(ωx)=F(x)F(\omega x)=F(x) holds exactly, F(0)=0F(0)=0, and FF is plateaued, as every quadratic function is.

Proposition 18 links type 64 to Hermitian rank-metric codes. Here CC is an additive code of 2152^{15} 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 CC is determined by these parameters [31 Theorems 1 and 3]. By duality, so is the rank distribution of VV; in particular every nonzero element of VV has rank at least four. Then Proposition 18(2) gives the rest: a matrix of rank four annihilates exactly one point of PG⁡(4,4)\operatorname{PG}(4,4) and a matrix of rank five none. So VV has 341 elements of rank 4, one for each point, and 1023−341=6821023-341=682 of rank 5. The code CC 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 VV and CC, for the 16 known classes [22]. Since every nonzero element of VV has rank at least four, the graphs {(x,Hx):x∈F45}\{(x,Hx):x\in\mathbb{F}_4^5\}, H∈VH\in V, pairwise meet in at most a point. In geometric terms, they are 1,024 generators of the Hermitian polar space H(9,4)H(9,4) with this property [32]. Here H(9,4)H(9,4) is defined in F410=F45×F45\mathbb{F}_4^{10}=\mathbb{F}_4^5\times\mathbb{F}_4^5 by the Hermitian form ⟨(x,y),(x′,y′)⟩↦x∗x′+y∗y′\langle(x,y),(x',y')\rangle\mapsto x^*x'+y^*y'; the graph of a Hermitian HH is totally isotropic for it. Trombetti and Zullo study maximum additive Hermitian codes [33]. We found no classification of these codes for 5×55\times5 matrices over F4\mathbb{F}_4. To our knowledge, the realization of type 64 as subspaces of Herm⁡5(F4)\operatorname{Herm}_5(\mathbb{F}_4) and the characterization of APN by the dual code CC (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 F2\mathbb{F}_2-subspaces VV of Herm⁡5(F4)\operatorname{Herm}_5(\mathbb{F}_4) such that every point of PG⁡(4,4)\operatorname{PG}(4,4) is annihilated by exactly one nonzero element of VV. The group ΓL⁡(5,4)\operatorname{ΓL}(5,4) acts on these subspaces by H↦P∗HσPH\mapsto P^*H^\sigma P. Equivalent subspaces give EA-equivalent functions. The converse is not clear, since an EA-equivalence need not respect the F4\mathbb{F}_4-structure.

What is known in type 64

Sixteen of the 29 classes of Theorem 1 lie in type 64. They are the Gold functions x3x^3 and x9x^9, 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 xb+∑k=1tckxekx^b+\sum_{k=1}^{t}c_kx^{e_k}, where the eke_k are tt distinct exponents among the 24 exponents 2i+2j≠b2^i+2^j\ne b with j−ij-i odd, and the ckc_k are nonzero. We ran b=3b=3 with ck∈F4c_k\in\mathbb{F}_4 and 5≤t≤105\le t\le10, b=3b=3 with ck∈F32c_k\in\mathbb{F}_{32} and 1≤t≤41\le t\le4, and b∈{9,33}b\in\{9,33\} with ck∈F4c_k\in\mathbb{F}_4 and 5≤t≤95\le t\le9. The number of candidates is ∑(24t)(q−1)t=219,963,317,255\sum\binom{24}{t}(q-1)^t=219,963,317,255 over these cases. This extends the search of [10 Sec. 9.2] to more terms and to F32\mathbb{F}_{32}. 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 VV. For each of its 174,251 subspaces V8V_8 of dimension 8, we computed by linear algebra all spaces V′≠VV'\ne V of dimension 10 that contain V8V_8 and satisfy Proposition 18(2). This step has no cap. The program excludes VV itself, which is a completion of every V8V_8. It computes the fingerprint of every completion it finds. An independent program recounts the completions on sampled subspaces V8V_8, 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 (V8,V′)(V_8,V'). All of them have the fingerprints of 7 of the 16 classes. Since EA-equivalence need not respect the F4\mathbb{F}_4-structure, one class may contain several inequivalent spaces VV; we switched only from one space per class.

  • Random sparse polynomials. Type 64 is spanned by the 25 monomials x22k+1x^{2^{2k+1}} with kk odd. More than 4⋅1084\cdot10^8 random polynomials with 2 to 14 of these terms, and coefficients in F4\mathbb{F}_4, F32\mathbb{F}_{32} or F1024\mathbb{F}_{1024}, 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 4.5⋅10574.5\cdot10^{57} nodes on type 64.

  • A dedicated solver builds VV point by point in PG⁡(4,4)\operatorname{PG}(4,4), with one matrix of rank four fixed. Its tree has about 4⋅10284\cdot10^{28} nodes, and about 3⋅10273\cdot10^{27} 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 GL⁡(5,4)\operatorname{GL}(5,4) has order about 1.5⋅10151.5\cdot10^{15}. The Knuth estimate of the tree at level eight is about 4⋅10284\cdot10^{28} partial spaces. Dividing by the group order suggests that, even with perfect isomorph rejection, at least about 3⋅10133\cdot10^{13} 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 VV 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 F210\mathbb{F}_2^{10} 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 F210\mathbb{F}_2^{10} 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 F210\mathbb{F}_2^{10} has a nontrivial linear self-equivalence if and only if it is EA-equivalent to one of the 29 classes.

Settled bytypesremarks
proof and search242no APN function
proof only38search too large or not run; no APN function
search only189 empty, 9 with APN functions
open1type 64
total299

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 FF have a self-equivalence of prime order of type t≠64t \ne64. If tt is one of the 280 types of § 4, then FF is not APN. The same holds for the nine empty types settled by search, including type 47 (Theorem 17). Otherwise tt 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.

ClassMMtypes
Gold x3x^3524, 64, 73, 129, 175
Gold x9x^9524, 64, 73, 129, 180
F4 a=1a=1 (x3+Tr⁡(x9)x^3+\operatorname{Tr}(x^9))524, 64, 73
F4 a=ωa=\omega564, 73
F3 i=1i=1464, 73, 170
F3 i=2i=2464, 73, 171
F12, two classes3, 473, 176
F12, four classes3, 4, 3, 4176
F13 k=0k=0, four classes5, 5, 4, 364, 73, 176
F13 k=2k=2364, 73, 129
Beierle–Leander #1373, 231
Beierle–Leander #35176
Beierle–Leander #5473, 129
BIK triplicate #1, #3, #4, #5, #6464, 73
N1373
N2, N3, N4473

Table VIII. The 29 quadratic APN classes of F210\mathbb{F}_2^{10} 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 M<5M < 5 (Table VI). So Theorem 1 gives the following.

Classortho-derivative differential spectrumMM
N10635846 2317181 479085 613540 81725 10145 12300^{635846}\ 2^{317181}\ 4^{79085}\ 6^{13540}\ 8^{1725}\ 10^{145}\ 12^{30}3
N20633636 2320446 479035 612670 81580 10180 1250^{633636}\ 2^{320446}\ 4^{79035}\ 6^{12670}\ 8^{1580}\ 10^{180}\ 12^{5}4
N30635924 2316881 479575 613245 81660 10237 1225 1450^{635924}\ 2^{316881}\ 4^{79575}\ 6^{13245}\ 8^{1660}\ 10^{237}\ 12^{25}\ 14^{5}4
N40634720 2318706 479315 613035 81575 10176 1220 1450^{634720}\ 2^{318706}\ 4^{79315}\ 6^{13035}\ 8^{1575}\ 10^{176}\ 12^{20}\ 14^{5}4

Table VI. The four new quadratic APN classes of F210\mathbb{F}_{2^{10}}. MM 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 FF be a quadratic APN function of F210\mathbb{F}_2^{10} with a linear self-equivalence of prime order, of a type other than 64. Then FF is not CCZ-equivalent to a permutation.

Conclusion

We classified the quadratic APN functions of F210\mathbb{F}_2^{10} 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 5×55 \times5 Hermitian matrices over F4\mathbb{F}_4 such that every point of PG⁡(4,4)\operatorname{PG}(4,4) 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 H(9,4)H(9,4).

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 F210\mathbb{F}_2^{10} has quadratic APN functions without any nontrivial linear self-equivalence.

The four new classes

Let gg be a root of x10+x3+1x^{10}+x^3+1, so that F210=F2(g)\mathbb{F}_{2^{10}}=\mathbb{F}_2(g), and let ω=g7+g6+g5+g3+g2\omega=g^7+g^6+g^5+g^3+g^2. Then ω2+ω+1=0\omega^2+\omega+1=0, so F4={0,1,ω,ω2}\mathbb{F}_4=\{0,1,\omega,\omega^2\}. In the artifact, field elements are integers in the basis 1,g,…,g91,g,\ldots,g^9, so ω\omega is 236 and ω2\omega^2 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].

N1(x)=ωx3+ωx5+ω2x6+ωx10+ω2x20+x24+ωx34+x36+x65+ω2x66+ω2x68+x72+x80+ω2x96+ωx129+x132+x257+ω2x260+ω2x264+ω2x288+x513+ω2x516+ωx544+ω2x576+ω2x640\begin{aligned} N1(x) ={}& \omega x^3+\omega x^5+\omega^2x^6+\omega x^{10}+\omega^2x^{20}+x^{24}+\omega x^{34}\\ &+x^{36}+x^{65}+\omega^2x^{66}+\omega^2x^{68}+x^{72}+x^{80}+\omega^2x^{96}\\ &+\omega x^{129}+x^{132}+x^{257}+\omega^2x^{260}+\omega^2x^{264}+\omega^2x^{288}+x^{513}\\ &+\omega^2x^{516}+\omega x^{544}+\omega^2x^{576}+\omega^2x^{640} \end{aligned}
N2(x)=x3+ω2x5+ωx12+ω2x17+x24+ωx33+ω2x48+x65+x72+x80+x96+ω2x130+ωx132+ω2x144+x192+ωx258+x320+ω2x384+ω2x514+ω2x516+x520+ω2x528+ω2x576+x640\begin{aligned} N2(x) ={}& x^3+\omega^2x^5+\omega x^{12}+\omega^2x^{17}+x^{24}+\omega x^{33}+\omega^2x^{48}\\ &+x^{65}+x^{72}+x^{80}+x^{96}+\omega^2x^{130}+\omega x^{132}+\omega^2x^{144}\\ &+x^{192}+\omega x^{258}+x^{320}+\omega^2x^{384}+\omega^2x^{514}+\omega^2x^{516}+x^{520}\\ &+\omega^2x^{528}+\omega^2x^{576}+x^{640} \end{aligned}
N3(x)=x3+ωx5+ωx6+x9+ωx12+ωx17+ω2x18+ω2x24+x34+ωx36+ωx48+ωx68+x72+x129+ωx130+x132+x136+ω2x160+ω2x260+ω2x272+x288+ωx384+ωx514+ωx520+ω2x544+ω2x640\begin{aligned} N3(x) ={}& x^3+\omega x^5+\omega x^6+x^9+\omega x^{12}+\omega x^{17}+\omega^2x^{18}\\ &+\omega^2x^{24}+x^{34}+\omega x^{36}+\omega x^{48}+\omega x^{68}+x^{72}+x^{129}\\ &+\omega x^{130}+x^{132}+x^{136}+\omega^2x^{160}+\omega^2x^{260}+\omega^2x^{272}+x^{288}\\ &+\omega x^{384}+\omega x^{514}+\omega x^{520}+\omega^2x^{544}+\omega^2x^{640} \end{aligned}
N4(x)=x3+x5+x9+ω2x17+ω2x20+x24+ω2x33+x34+x68+ωx72+ω2x96+ωx130+x132+x136+ω2x257+ω2x258+x272+ωx288+ω2x320+ω2x384+ωx513+ωx514+ωx516+ω2x520+ω2x528+ω2x640\begin{aligned} N4(x) ={}& x^3+x^5+x^9+\omega^2x^{17}+\omega^2x^{20}+x^{24}+\omega^2x^{33}\\ &+x^{34}+x^{68}+\omega x^{72}+\omega^2x^{96}+\omega x^{130}+x^{132}+x^{136}\\ &+\omega^2x^{257}+\omega^2x^{258}+x^{272}+\omega x^{288}+\omega^2x^{320}+\omega^2x^{384}+\omega x^{513}\\ &+\omega x^{514}+\omega x^{516}+\omega^2x^{520}+\omega^2x^{528}+\omega^2x^{640} \end{aligned}

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 W(A,B)W(A,B), 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: F210\mathbb{F}_{2^{10}} is defined by x10+x3+1x^{10}+x^3+1, and F32\mathbb{F}_{32}, in the type-24 solver, by x5+x2+1x^5+x^2+1.

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. [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. [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. [3]C. Carlet, Boolean Functions for Cryptography and Coding Theory. Cambridge: Cambridge University Press, 2021.DOI
  4. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [23]D. E. Knuth, “Estimating the efficiency of backtrack programs,” Math. Comp., vol. 29, no. 129, pp. 121–136, 1975.
  24. [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. [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. [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. [27]K.-T. Wong, “The eigenvalue problem λTx + Sx,” J. Differential Equations, vol. 16, no. 2, pp. 270–280, 1974.DOI
  28. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_xsx5nmk9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude

View statement
Looking for related papers…
Contents