In this paper
AbstractIntroductionRelated workQuadratic APN functions and switchingOur contributionOutlinePreliminariesWalsh transformEquivalencesInvariantsThe inverse function and local searchLocal searchStructured families of permutationsButterflies with power-based keyed permutationsCyclotomic mapsExact switching and switching neighbourhoodsSwitching closureThe projection test for CCZ-equivalence to a permutationProjections onto the components with Walsh zerosWalsh zero spaces of functions with affine supportsThe algorithmThe family Computations for Subspaces of the cubes.ExperimentsSetup and reproducibilityThe inverse function and structured permutations (E1, E2)The projection test compared with a generic search (E3, E12)Known quadratic APN classes in dimension ten (E4, E11)The family (E9, E10)Switching closure (E5)Searching for new quadratic APN functions in dimension ten (E6–E8)Symmetry-restricted univariate families (E7).Tree search with prescribed self-equivalences (E8).Conclusions and future workStatements and DeclarationsReferencesWorksComputer Science
Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions
Abstract
Whether almost perfect nonlinear (APN) permutations exist in even dimension is a long-standing open question, the big APN problem. The only example known in even dimension, on six bits, was found from a quadratic APN function that is not itself a permutation, by Carlet–Charpin–Zinoviev (CCZ) equivalence. It is therefore natural to test APN functions for CCZ-equivalence to a permutation. This amounts to finding two complementary -dimensional subspaces among the zeros of the Walsh transform, which lie in . A known necessary condition only uses their projections to and cannot decide every case. We give an exact test for functions whose Walsh supports are affine, including all quadratic functions. It reconstructs the subspaces from their projections, through searches for subspaces of and for constrained bilinear maps. On the benchmarked functions in dimension twelve, it lists them to times faster than the generic search of the commonly used sboxU library. We then study the functions , which Göloğlu and Pavlů proved not to be CCZ-equivalent to permutations when divides . With their result, our computations show that this holds for every even . In dimension the necessary condition is satisfied, and the new test decides the case. We conjecture this for every even dimension. We also compile classes of quadratic APN functions in dimension ten from published instances, with equivalence certificates. No function in these classes or in their switching closure is CCZ-equivalent to a permutation. All code and data are public.
Introduction
A function is almost perfect nonlinear (APN) if, for every nonzero and every , the equation has at most two solutions. APN functions offer the best possible resistance to differential cryptanalysis [1]. They are also related to optimal objects in coding theory, sequence design and finite geometry; see [2] for an account. Many block ciphers, for instance substitution–permutation networks, need invertible S-boxes. In odd dimension APN permutations are plentiful: the Gold functions with [1, 3], the Kasami [4], Welch [5] and Niho [6] functions, and the inverse function are APN permutations of for odd . In even dimension the situation is completely different. There is no APN permutation of [7]. No APN power function and no quadratic APN function is a permutation in even dimension (see [2]). The only APN permutation known in even dimension is the six-bit permutation found by Browning, Dillon, McQuistan and Wolfe [8]. Whether APN permutations exist for some even is known as the big APN problem.
Dillon’s permutation was not found by a search among permutations. It was obtained as a function CCZ-equivalent [9] to the quadratic APN function over , which is not itself a permutation. Two lines of attack on the big APN problem have therefore been pursued. The first constructs permutations with a prescribed structure, such as the butterfly structure that underlies Dillon’s permutation [10, 11, 12]. The second searches for APN functions that are not permutations but are CCZ-equivalent to one. This second approach relies on a characterization due to Canteaut and Perrin [13]. A function is CCZ-equivalent to a permutation if and only if the set of zeros of its Walsh transform contains two -dimensional subspaces with trivial intersection.
Related work
Constructions of permutations.
Perrin, Udovenko and Biryukov [10] decomposed Dillon’s permutation as an open butterfly on . Canteaut, Duval and Perrin [11] generalized the construction to all dimensions , obtaining differential uniformity four for . Canteaut, Perrin and Tian [12] proved that a generalized butterfly is APN only on six bits. Beierle, Brinkmann and Leander [14] classified APN permutations with nontrivial linear self-equivalences in small dimension.
CCZ-equivalence to permutations.
Gölöğlu and Langevin [15] proved that Gold functions are not CCZ-equivalent to permutations in any even dimension. They proved the same for Kasami functions in every dimension divisible by four. These results rest on a necessary condition: if is CCZ-equivalent to a permutation, its non-bent components contain two subspaces whose sum is the whole space. This condition follows directly from an observation of Browning et al. [8]. Gölöğlu and Pavlu [16] turned it into an algorithm, a depth-first search for the largest subspace contained in the set of non-bent components. With it they showed that no member of the families of APN functions known at that time is CCZ-equivalent to a permutation of for even , apart from the known case . They also checked random members of these families up to , and introduced the number of subspaces of the set of non-bent components as an EA-invariant. Moreover, they proved that is not CCZ-equivalent to a permutation when . As reported in [16], Canteaut and Perrin independently designed a similar algorithm. Budaghyan, Ivkovic and Kaleyski [17] extended the result for to all quadratic 3-to-1 APN functions. Bénétéau, Goluboff, Kölsch and Vaghasiya [18] showed that a quadratic function that is CCZ-equivalent to a permutation has at least non-bent components.
When the non-bent components do contain subspaces spanning , the necessary condition is satisfied and therefore inconclusive. One then has to search for Walsh zero spaces in . Chase and Lisoněk [19] constructed Walsh zero spaces for Gold functions in odd dimension. Bonnetain, Perrin and Tian [20] described generic algorithms for finding vector spaces of a given dimension in a set; the test of [13] is one of them. These algorithms, together with a test for CCZ-equivalence to a permutation, are implemented in the library sboxU of Perrin et al. [21]. Most of the works cited below used sboxU to check their functions.
Quadratic APN functions and switching
Edel and Pott [22] introduced the switching construction. With it they found, in dimension six, the only known APN function that is CCZ-inequivalent to both power and quadratic functions.
In dimension eight the only known APN function that is not quadratic is the Kasami function . The known quadratic APN functions form at least 3,808,491 CCZ-classes [23 Theorem 5.1]. Each item below gives the number of classes first found in the given source. The counts of the first four items are those of [24 Section 4].
22: the quadratic functions in the list of Edel and Pott [22], which collects the earlier constructions and includes the Gold functions and .
8,157: Yu, Wang and Li [25], with a matrix method.
10: Weng, Tan and Gong [26].
2: the family of Taniguchi [27].
12,921: Beierle and Leander [24]. They found 12,733 classes by a recursive tree search among functions with prescribed linear self-equivalences, and 188 by switching.
5,412: Yu and Perrin [28], with the same matrix method.
6,368: Beierle, Leander and Perrin [29], by extending quadratic APN functions in dimension seven.
3,775,599: Beierle, Langevin, Leander, Polujan and Rasoolzadeh [23, 30], by extending vectorial bent functions.
The first seven items give the 32,892 classes known before [23]. Beierle et al. estimate the total number of classes at about six million. In a recent preprint, Kuznetsov [31] reports four further classes, which are not included in the count above. In [24] and [23], none of the new functions is CCZ-equivalent to a permutation. For the known infinite families, see [16]. We do not repeat these tests in dimension eight.
In dimension ten the known APN functions that are not quadratic are the Kasami function and the Dobbertin function [32]. § 8.4 shows that the quadratic APN instances we considered form exactly 25 CCZ-classes. For some families we took all parameters and for others random samples, and for [33] we used the instances of the preprint version (§ 8.4). We use the names F3, F4, F12 and F13 of the families in [34 Table 3]. Each item below gives a set of classes and the sources whose functions lie in them.
2 classes: the Gold functions and . The class of also contains members of the relative-trace family of Zheng, Kan, Li, Peng and Tang [33].
2 classes: the family F3 of Budaghyan and Carlet [35]. They also contain Carlet’s bivariate family (see [36 Table 2.1]) and members of the family of [33].
2 classes: the family F4, , of Budaghyan, Carlet and Leander [37].
6 classes: the family F12 of Taniguchi [27].
5 classes: the family F13 of Budaghyan, Helleseth and Kaleyski [38], with parameters in . They also contain the two biprojective families of Göloğlu [39] and the first family of Calderini, Li and Villa [40]. Two of the five instances of Beierle and Leander [24] lie in them. So do two instances and some members of the family of [33], and the second instance of Budaghyan, Ivkovic and Kaleyski [17 Table 2].
3 classes: the other three instances of [24]. One of them also contains the third instance of [33].
5 classes: the other five instances of [17 Table 2], obtained by adding five to seven terms with coefficients in to , or . The class of the first one also contains the function of Li, Zhou, Li and Qu [41]. It also contains the second family of [40].
Budaghyan, Ivkovic and Kaleyski checked with sboxU that none of their functions is CCZ-equivalent to a permutation. Göloğlu and Kölsch [36] determined the equivalences between the biprojective families. Yu, Li, Ichanska and Kaleyski [42] classified the quadratic APN functions in dimension ten with coefficients in . There are three classes, those of , , the last one in . Yu, Kaleyski, Budaghyan and Li [43] did the same for . The same classification is the case of the QAM search of Ichanska, Berg, Kaleyski and Yu [44]. Their search for is only partial, and the new APN function it reports is in dimension eight, so it adds no class in dimension ten.
Budaghyan, Calderini and Villa [45] determined the equivalences between the known families in small dimension. Kaleyski [34] surveyed the invariants for telling classes apart. Kalgin and Idrisova [46] classified the quadratic APN functions in seven variables. This classification is reproduced in the data of Beierle et al. [47], which list the EA-classes of quadratic -APN functions for small . Recently, Göloğlu and Kölsch [48] gave a large family of APN permutations in every odd dimension divisible by three. They also gave quadratic APN functions in even dimension that are not bijective. Their functions are defined on , so none of them has dimension ten.
Our contribution
We study the big APN problem computationally, with an emphasis on exact methods whose results can be checked independently. Our main contributions are the projection test and its application to the family up to dimension 24. The other contributions concern dimensions eight to ten.
We consider functions whose Walsh supports are affine subspaces. These include all quadratic functions. We parametrize the -dimensional subspaces of their Walsh zeros by three objects: a subspace of the components with Walsh zeros, a subspace of of the same dimension, and a bilinear map (Theorem 8). The resulting test for CCZ-equivalence to a permutation, which we call the projection test, searches for and in instead of searching for subspaces of . It complements the necessary condition of [15, 16] (Proposition 7): it decides exactly the cases in which that condition is satisfied and therefore inconclusive. An example is the Gold functions in dimension ten, whose non-bent components contain eleven -dimensional subspaces that pairwise span . We compared it with the generic search of the sboxU library. Listing all Walsh zero spaces is 5 to 18 times faster in dimension ten, and 39 to 55 times faster in dimension twelve (§ 8.3).
The family in dimensions with odd is not covered by the theorem of [16]. For these dimensions we show that the non-bent components contain a line of the Desarguesian spread whenever is a cube (Proposition 11). So their dimension alone cannot exclude a permutation. We decide these cases for by computation, and conclude that no member of the family is CCZ-equivalent to a permutation for even (Corollary 12). In dimension 18 the necessary condition is satisfied, and the case is decided by Theorem 8. Dimension 22 needs a subspace search that exploits the symmetries of the family. We state a conjecture that would settle the family in all even dimensions (Conjecture 14). The case , computed after the conjecture was formed, agrees with it.
We compile 25 classes of quadratic APN functions in dimension ten from the published instances we could examine, and test them. With an explicit EA-equivalence test we show that the published instances we could obtain lie in these 25 classes. These are the instances of the preprint version of [33], those of the bivariate families of [39, 40, 41], and the second instance of [17 Table 2] as printed there. In particular, the function of [41] is EA-equivalent to the first instance of [17 Table 2]. No class is CCZ-equivalent to a permutation. For the families considered in [16] this confirms their result independently, and our values of the largest subspace dimension agree with theirs. The classes found after that work were tested in [24] and [17], so our test is an independent confirmation for them as well. Of the 25 classes, 18 are excluded by the dimension bound, 4 by the spanning condition, and 3 need Theorem 8.
We compute the quadratic switching closure of the source functions listed in Table 5, in dimensions six, eight, nine and ten, with a certified equivalence for every neighbour, and we test every quadratic class found. In dimensions eight to ten the resulting quadratic classes have no non-quadratic switching neighbours. In dimension ten the 25 classes are closed under switching. In dimensions nine and ten this extends the computations of [24], which were performed in dimensions seven and eight.
| Sources | Classes | Neighb. | Certified | deg | Perm. | |
| 6 | , F4, Edel–Pott | 13 | 1,259 | 1,186 | yes (5) | 1 (Kim) |
| 8 | powers, F4 | 17 | 96 | 83 | no | none |
| 9 | powers, F4 | 6 | 14 | 12 | no | (odd ) |
| 10 | powers, 25 classes | 25 | 13 | 18 | no | none |
Table 5. Exact switching closure (E5). “Classes” is the number of pairwise EA-inequivalent quadratic classes in the closure; “Neighb.” is the number of functions formed, one per nonzero class of a quotient ; “Certified” is the number of explicit EA-equivalences proved, between a neighbour or a source and a stored class; “deg ” indicates whether a class of the closure has a switching neighbour of degree at least three (for non-quadratic sources such as the Kasami function, the quotient is trivial in all our cases); “Perm.” gives the classes that are CCZ-equivalent to a permutation.
We search for new quadratic APN functions in dimension ten by symmetry-restricted sampling of univariate polynomials and by the tree search of [24] with a large randomized campaign. Every function found is tested individually, and none is CCZ-equivalent to a permutation. A search over bilinear forms in dimensions six to eight shows that unstructured search does not scale.
We explain why the inverse function is not APN in even dimension. The sets of four points on which it is affine, and which therefore violate the APN condition, are exactly the two-dimensional subspaces , (Proposition 3). We then show for that swapping two entries of the lookup table of the inverse function never brings it closer to the APN property, measured by the cost (1). Here a swap exchanges the outputs and of two inputs . We also enumerate three structured families of permutations: butterflies whose keyed permutations are built from power maps, cyclotomic maps and switched inverse functions. None of them contains a permutation of closer to the APN property than the inverse function. The butterflies of this kind contain none of either (§ 3 and § 4).
We find no APN permutation in dimension eight or ten. We believe that the tools, in particular the projection test, are useful for future searches. We make all code and data available at https://github.com/peacker/ccz-projection-test-apn, together with a script that compares every number reported here with the stored results.
Outline
Section 2 recalls definitions. Section 3 studies the inverse function and local search around it, and Section 4 structured families of permutations. Section 5 recalls exact switching and describes how we compute the switching closure. Section 6 contains the parametrization of Walsh zero spaces and the resulting test for CCZ-equivalence to a permutation, and Section 7 applies it to the family . Section 8 reports the experiments, and Section 9 concludes with open questions.
Preliminaries
We identify with the finite field whenever a field structure is needed. The components of are then also written with . The field coordinate and the bit coordinate of the same component are related by the dual basis of the trace form; the repository contains this conversion. In our computations is represented in a polynomial basis modulo a fixed primitive polynomial, listed in the accompanying repository. For we write for the usual scalar product, and denotes the absolute trace of . An -function is a map ; its components are the Boolean functions , .
Differential properties. For let . The values are even, and is APN if for all and all . To measure how far is from being APN we use
which vanishes exactly when is APN. An entry contributes 1, and an entry 6 contributes 3. A 2-flat is an affine subspace of dimension two, with linearly independent. We say that is affine on a 2-flat if . We write for the number of 2-flats on which is affine. A function is APN if and only if it is affine on no 2-flat.
Walsh transform
The Walsh transform of is for . The Walsh zeros of form the set , which always contains . For the Walsh support of the component is . The component is bent if for all . We write for the set of components that have a Walsh zero. A bent component has no Walsh zero. For plateaued components, in particular for quadratic ones, the converse holds, so for quadratic the set is the set of non-bent components. This is not true in general. For example, the Boolean function on that is at exactly one point has no Walsh zero but is not bent. All our proofs use only the definition of . In general statements we call its elements the components with Walsh zeros. For quadratic functions, where they are exactly the non-bent components, we also use that name. If is quadratic, the component has a linear space , and is a coset of , so that ; see [2].
Equivalences
Two functions are CCZ-equivalent if an affine permutation of maps the graph of onto the graph of [9]. They are EA-equivalent if with affine permutations and affine. CCZ-equivalence preserves the differential spectrum and the extended Walsh spectrum, hence the APN property. For quadratic APN functions CCZ-equivalence coincides with EA-equivalence [49]. The following characterization is the basis of our tests.
Proposition 1 ([13]) is CCZ-equivalent to a permutation if and only if contains two -dimensional linear subspaces with .
Given such and , a permutation in the CCZ-class of is with and . Indeed, the linear map with rows maps the graph of onto a set whose Walsh transform vanishes on both coordinate axes, so that both projections of this set are bijective. Following [19] we call an -dimensional subspace of a Walsh zero space of .
Invariants
To tell CCZ-classes of quadratic APN functions apart we use the ortho-derivative. For , the image of is a hyperplane, and is the nonzero vector orthogonal to it. The differential spectrum and the extended Walsh spectrum of are EA-invariants of [34, 50], hence CCZ-invariants for quadratic APN functions [49]. These invariants are not complete. Two functions with different invariants are inequivalent, but equal invariants do not prove equivalence. We say that a function lies in a class only when we have proved the equivalence by an explicit certificate (§ 8.4). Otherwise we only say that it has the invariant of that class. All CCZ-equivalence tests are applied to every function individually (§ 8). Our conclusions therefore do not depend on the completeness of the invariant.
The inverse function and local search
The cost (1) has a simple geometric meaning.
Lemma 2 For every -function , .
Proof. Fix and . The solutions of come in pairs , and every unordered pair of distinct such pairs , determines the 2-flat , on which is affine. Conversely, let be affine on a 2-flat with direction space . For each of the three nonzero directions of , the two pairs of in direction have the same derivative value. Hence every 2-flat on which is affine is counted exactly three times in (1), once for each nonzero direction. □
Let be the inverse function, with . For even the field contains , and is a vector space over ; we call the sets , , the -lines through the origin. There are of them. The following proposition is a geometric restatement of Nyberg’s computation of the differential spectrum of [1].
Proposition 3 Let be even. The 2-flats on which is affine are exactly the -lines through the origin. In particular and .
Proof. For the equation has at most four solutions, and four solutions only for [1]. The four solutions are : this is clear for , and for we get , using , and symmetrically for . So the 2-flats on which is affine are the sets , each of which is a 2-dimensional linear subspace with nonzero directions ; by Lemma 2 there are of them. □
Proposition 3 says that the inverse function is close to APN in a very regular way: it fails the APN condition only on the subspaces , and all of them contain the point 0. A modification of that produces an APN permutation must destroy all these flats simultaneously without creating new ones. Changing the value to any other value already destroys all of them, since each of these flats contains 0. The result is no longer a permutation, so other values must change as well, and the question is how many new flats are created.
Local search
For we measured how cost changes when two entries of the lookup table are swapped, i.e. under the moves , which exchange the outputs and . With an incremental update of the difference table, one move is evaluated in operations. All transpositions of can then be scanned in a few milliseconds. The result is that no swap of two entries improves . No transposition decreases the cost. The 255 transpositions that leave it unchanged are exactly those involving the position 0. Every other transposition increases the cost by at least 222. None of the 255 permutations reached by the cost-preserving transpositions can be improved by a further transposition. We also ran simulated annealing started at , with plain transpositions or with moves that preserve the involution property of ; recall that Dillon’s permutation is CCZ-equivalent to an involution. It never found a permutation of cost below 255 (§ 8.2). For comparison, simulated annealing started from random permutations of does not get below costs between 4,776 and 4,926.
Structured families of permutations
We considered three families of permutations that contain, or are related to, the known APN permutations. We searched them exhaustively in dimension eight, and the first family also in dimension ten. All results are negative and are collected in Table 1.
| Family | Exp. classes | Perms. | APN | Min. cost | |
| Butterflies | 6 | 2 | 896 | 6 | 0 |
| 8 | 2 | 7,680 | 0 | 8,280 | |
| 10 | 6 | 190,464 | 0 | 71,424 | |
| Cyclotomic | 8 | 24 | 346,800 | 0 | 255 |
| Switched inverse | 8 | 35 | 33,660 | 0 | 255; 4,155 |
Table 1. Structured families of permutations (§ 4). Butterflies use , switched inverses . “Exp. classes” is the number of cyclotomic classes of , or ; “Perms.” counts parameter tuples that give a permutation, without merging equal or equivalent tables; for the switched inverse the second-smallest cost is also given. The cost of is ; a cost of 0 means APN.
Butterflies with power-based keyed permutations
Let and let , , be a family of permutations of . The open butterfly [10]
is a permutation of for every such family. Dillon’s permutation is an open butterfly with and [10]. The generalized butterflies of [11, 12] use with , which requires odd. For the exponent 3 is not available, since is not a permutation of . We therefore allowed
Here runs over one representative of each cyclotomic class of exponents coprime to . Further, runs over (with read as 1 for and as 0 for ), and run over all of , including 0. Every such tuple gives a permutation, and we count tuples, not distinct lookup tables. For six tuples give APN permutations; we did not check how many of them are equivalent. For and the smallest costs are 8,280 and 71,424, compared with 255 and 1,023 for the inverse function.
Cyclotomic maps
For and , a cyclotomic map is with defined on the -th roots of unity. In other words, it is a power function multiplied by a constant that depends on the coset of in modulo the subgroup of index . Both , which is APN but not a permutation for even , and belong to such families. For $n = 8 and , each -line of Proposition 3 meets each of the three cosets in exactly one point, because and 85 is not divisible by three. For and we took one representative of each cyclotomic class with , 24 classes in all, and all with . We kept the maps that are permutations. None of them has cost below 255, and the nontrivial choices of applied to the inverse function have cost at least 4,080.
Switched inverse functions.
Finally we considered for all exponents , up to cyclotomic equivalence, and all . Such a switching modifies on a large set at once. Among the 33,660 parameter tuples that give a permutation, 32,385 give cost 255, the cost of . Every other one has cost at least 4,155.
These experiments indicate that, in contrast with dimension six, the natural structured generalizations of the known constructions do not come close to the APN property in dimensions eight and ten. The inverse function has the smallest cost we observed for a permutation. The modifications of it that we tried either keep its cost or have a much larger one. This motivates the approach of the following sections, which searches for APN functions that are not permutations and tests them for CCZ-equivalence to a permutation.
Exact switching and switching neighbourhoods
Two functions are switching neighbours if for a Boolean function and a nonzero [22]. If is APN, all its APN switching neighbours can be found by linear algebra.
Sketch. fails to be APN iff there are and two distinct pairs , with equal derivatives, i.e. . Since is APN the left-hand side is nonzero, so this happens iff and .
The conditions are linear in the truth table of . So the set of all with APN is a subspace of the space of Boolean functions. We compute it exactly by Gaussian elimination over . In dimension ten the system has unknowns and up to a few hundred thousand equations; with rows packed into machine words it is solved in about a quarter of a second.
always contains the affine Boolean functions, and it contains the components with , for which with the invertible linear map . We call the span of these functions the trivial part of . If and , then is EA-equivalent to : for and we have , so . Hence the switching neighbours of in direction are, up to EA-equivalence, given by the nonzero classes of the quotient , where .
Lemma 5. Let be quadratic and . Then has algebraic degree at least three if and only if the algebraic normal form of contains a monomial of degree at least three. Consequently, let be the subspace of the elements of of degree at most two, and let . Then is the rank of the degree- parts of the algebraic normal forms of a basis of , and has switching neighbours of degree at least three in direction . In particular such neighbours exist if and only if .
Proof. The coordinate functions of are ; those of have degree at most two, and has a nonzero coordinate. The map that sends to the degree- part of its algebraic normal form is linear on , with kernel and image of dimension .
Switching closure
Starting from a list of APN functions, we compute for every source and every . For a power function it suffices to take modulo the -th powers, because of the equivalence . For each we record whether non-quadratic solutions exist (Lemma 5). We then form one function for each nonzero class of . In our computations in dimension six and in dimensions eight to ten, so this is cheap. Each quadratic is compared with the stored functions that have the same ortho-derivative spectra, with the EA-equivalence test of § 8.4. This test is exhaustive and returns an explicit certificate, which is checked separately. If is equivalent to a stored function, it is discarded. Otherwise it becomes a new class, is stored, and is in turn switched. EA-equivalent functions have EA-equivalent switching neighbours: if , then . So it suffices to switch one function per class. The procedure ends when every stored class has been switched. Non-quadratic neighbours are recorded but not switched further. The result is therefore the exact set of quadratic APN classes reachable from the sources by switching paths whose intermediate functions remain quadratic, and the classes in it are pairwise inequivalent. In dimensions eight to ten no quadratic class in the closure has a non-quadratic neighbour, so there the closure is also closed under unrestricted switching. In dimension six it is not, but the known classification shows that all thirteen quadratic classes are reached. Every new class is tested for CCZ-equivalence to a permutation with the test of § 6.
In dimension six we started this procedure from three sources: , the functions with , and , where is a primitive element. It reaches all thirteen classes of quadratic APN functions. Five of them have switching neighbours of degree three. Among them is the last source, whose switching gives the non-quadratic APN function of Edel and Pott [22]. Exactly one of the thirteen classes, the class of the Kim function, is found to be CCZ-equivalent to a permutation by the test of § 6. The procedure thus rediscovers both known exceptional phenomena of dimension six, which serves as a check of the implementation. The results in dimensions eight, nine and ten are reported in § 8.6.
The projection test for CCZ-equivalence to a permutation
By Proposition 1, deciding whether is CCZ-equivalent to a permutation amounts to finding all Walsh zero spaces of , i.e. all -dimensional subspaces of , and testing them for a pair with trivial intersection. For a quadratic APN function in even dimension, contains about a quarter of . In dimension ten this is 262,911 vectors for . A generic search [20] has to find all 10-dimensional subspaces of this set. In this section we assume that the Walsh supports are affine. We show that a Walsh zero space is then described by three objects: a subspace of , a subspace of of the same dimension , and a bilinear map with binary entries. The searches for and take place in . We do not claim an improvement of the worst-case complexity of the generic search; the gain is practical, and we measure it in § 8.3. Throughout, , , denotes the projection onto the second coordinate, and for a Walsh zero space we write .
Projections onto the components with Walsh zeros
Lemma 6. Let be a Walsh zero space of an -function . Then , and .
Proof. If is not in , then , so for every and no vector can lie in . The second statement is the rank-nullity theorem for , whose kernel is .
Proposition 7 ([15, 16]) If is CCZ-equivalent to a permutation, then contains two linear subspaces with . In particular, if denotes the largest dimension of a linear subspace contained in , then , and every Walsh zero space that belongs to a pair with trivial intersection satisfies .
Proof. We recall the short argument for completeness. If for two Walsh zero spaces, then , hence , and both projections lie in by Lemma 6. Then with both dimensions at most .
Proposition 7 is Condition 2 and Corollary 1 of [16]. The condition was used in [15] for Gold and Kasami functions. The number of subspaces of is an EA-invariant [16, 34]. For quadratic , Bénéteau, Goluboff, Kölsch and Vaghasiya [18 Corollary V.6] show two further necessary conditions: , and every -dimensional subspace meets in at least three points. In dimension ten the quadratic APN functions considered below have 341 non-bent components, so the bound on does not exclude them. Budaghyan, Ivkovic and Kaleyski [17 Theorem 7] prove for every quadratic 3-to-1 APN function when . Hence no such function is CCZ-equivalent to a permutation. By [17 Proposition 8], this applies for to all APN monomials and to several infinite families, among them . The case , which contains dimension ten, is left open there.
Computing settles every function with . The computation is inconclusive when contains subspaces spanning . In that case one has to decide whether these subspaces are projections of Walsh zero spaces that intersect trivially. The rest of this section shows how to do so.
Walsh zero spaces of functions with affine supports
We now assume that for every the Walsh support is an affine subspace , with a linear subspace. We set . This holds for every quadratic function, with the linear space of the component (§ 2). Note that does not depend on the choice of when .
Theorem 8. Let have affine Walsh supports. Let and be linear subspaces of the same dimension , and let be a bilinear map. Let be a linear map with for all and , and set
Then:
is an -dimensional subspace of that does not depend on the choice of , with and ;
every -dimensional subspace with equals for exactly one triple, namely , and for any ;
is a Walsh zero space of if and only if for every there exists with .
Proof (1). A map exists because has codimension and is dual to . Two choices of differ by a linear map , which does not change the set . The set is the image of the injective linear map on , so it has dimension . Its projection is and its kernel is . (2) Let be given and , . By the rank–nullity theorem for , whose kernel is , we have , so has dimension . For the fibre is a coset of . So is the same for all in the fibre when , and is well defined and bilinear. The fibres of and of over each are the same coset of , hence the two sets coincide. Conversely , and are determined by , which proves uniqueness.
(3) The fibre over is , and for all . For the fibre consists of Walsh zeros if and only if it is disjoint from . Two cosets and are disjoint if and only if , and . Hence the fibre consists of Walsh zeros if and only if there exists with , that is, . □
In particular a Walsh zero space with projection requires a subspace of dimension that meets nontrivially for every . For quadratic APN functions in even dimension the non-bent components typically have , so this is a strong condition.
Relation to previous work.
Parts (1) and (2) of Theorem 8 are linear algebra: a subspace of is determined by its projection, its kernel and a linear map between them. The new ingredient is part (3). For affine supports the condition that a fibre consists of Walsh zeros involves only and . So the possible subspaces are cut out by the spaces , and by equations that are linear in the typical case. The characterization of Canteaut and Perrin [13] and the generic search of Bonnetain, Perrin and Tian [20] work with the set in . Chase and Lisoněk [19] construct Walsh zero spaces of Gold functions explicitly. The necessary condition of [15, 16] uses only the projections. Our test starts from these projections and decides exactly which of them lift to Walsh zero spaces.
The algorithm
Theorem 8 and Proposition 7 give Algorithm 1, which we call the projection test, since it reconstructs the Walsh zero spaces from their projections. All searches take place in or in , never in .
Proposition 9 Let have affine Walsh supports. Algorithm 1 returns a permutation if and only if is CCZ-equivalent to a permutation, and every permutation it returns is CCZ-equivalent to .
Proof If are Walsh zero spaces with , then and by Proposition 7. By Theorem 8(2) and (3), equals for a subspace and a map that the loops enumerate, and likewise for . So both lie in , and the algorithm returns a permutation. Conversely, every element of is a Walsh zero space by Theorem 8(3). A pair with trivial intersection gives a permutation CCZ-equivalent to by Proposition 1. □
The subspaces are found with a standard vector space search in the set , where every subspace is generated once through its reduced echelon basis.
Algorithm 1. Projection test: CCZ-equivalence to a permutation for functions with affine Walsh supports
for each with compute and a basis of (from , or from the bilinear form if is quadratic)
largest dimension of a subspace of
if then return not CCZ-equivalent to a permutation
end if
for all subspaces with do
for all subspaces , , with for all do
enumerate the bilinear maps satisfying condition (3) of Theorem 8
add every to
end for
end for
if with exist then return the permutation of § 2
else return not CCZ-equivalent to a permutation
end if
The subspaces are built by a depth-first search. At each step it takes the first whose is not yet met by the current partial basis, and adds one of the nonzero vectors of . Once all are met, it completes the basis in all possible ways. Every admissible contains a nonzero vector of the chosen at each step, so no is missed. Every partial and complete subspace is recorded by its reduced echelon basis and visited only once, so every is produced exactly once.
Let be a basis of and a basis of . We store as the binary matrix . If , condition (3) is the linear equation in these entries. If , condition (3) says that the equations , , do not all hold. This is not a linear condition. We solve the linear equations first and check the other conditions on each element of their solution space. If that space is too large to list, we use a depth-first search instead. It chooses the linear forms one at a time and checks condition (3) for every in the span of the basis vectors already treated. An additional mode enumerates all dimensions ; the algorithm then returns the complete list of Walsh zero spaces. We used this mode to compare the algorithm with independent implementations of the generic search (§ 8.3).
Quadratic functions.
For a quadratic the data of Theorem 8 can be obtained without the Walsh transform. The space is the radical of the alternating form , an binary matrix. The vector is any solution of the linear system , . We also split the vector space search in over several threads at its first level. With these improvements the whole test takes about five seconds for the Gold function in dimension 14. In dimension 18 it takes a few minutes, and the dominant cost is the search for 9-dimensional subspaces in a set of 87,381 elements.
Cost. The running time is governed by the number of subspaces in the admissible range, the number of subspaces for each , and the size of the solution spaces for . These numbers depend on the function, and we know no useful worst-case bound for them. The preprocessing stores the sets and , that is, words. The search for also stores the reduced echelon bases of all partial and complete subspaces it visits, and the algorithm stores the Walsh zero spaces it finds. Neither of these is bounded by in general. Both were small for the functions of § 8. § 8.3 reports the running times for the functions we tested.
Scope. Theorem 8 only needs the Walsh supports to be affine. All functions on which we used it are quadratic, so we have not evaluated the test on other functions with affine supports. For functions whose Walsh supports are not affine, such as the Kasami function in dimension ten, Proposition 7 still applies but Theorem 8 does not. For such functions one has to fall back to the generic search.
The family
In this section and . We write for the subgroup of cubes, which has index three since is even. Let be a primitive element of . We study
the family of Budaghyan, Carlet and Leander [37] (family F4 above). Gölöğlu and Pavlů proved that is not CCZ-equivalent to a permutation when is even [16 Theorem 3]. Their proof shows that contains no -dimensional subspace, using that for even the set contains no subspace of dimension [15 Lemma 13]. We study the case of odd , where this fails.
Lemma 10. For we have and . Hence and are linearly equivalent whenever or , and every member of the family is linearly equivalent to or to .
Proof. , and since . The cosets of in are , and , and maps onto .
The components of are . On the hyperplane they coincide with the components of , which are bent exactly when [16 Lemma 1]. For odd we have , so , and is the union of the lines , , of the Desarguesian spread of .
Proposition 11. Let be odd and . Then the -dimensional subspace is contained in . In particular the necessary condition of Proposition 7 does not exclude by dimension alone.
Proof. Let with . Then because and , and , so . The component is therefore the component of the Gold function, which is not bent since .
Here is taken with respect to the trace form, i.e. in the field coordinates of the components . The computations below are carried out in bit coordinates and translated to field coordinates through the dual basis of the trace form.
Computations for
By Lemma 10 it suffices to consider , where and . For we nevertheless computed as well, with the same results as for . Table 2 lists, for each case, the -dimensional subspaces of . In every case there is none of dimension . So , with equality whenever an -dimensional subspace exists. By Proposition 7 a permutation then requires two -dimensional subspaces with . If there is at most one -dimensional subspace, this excludes a permutation. For this follows from the uniqueness of the -dimensional subspace, since a subspace of dimension contains subspaces of dimension . For the set has 87,381 elements. The search for subspaces of dimension nine and ten was split over 128 threads and took about five minutes per value of .
Table 2. Number (#) of -dimensional subspaces of for , , odd. “Lines” means that every such subspace is a line of the Desarguesian spread; “” that one of them is . The necessary condition of Proposition 7 (column “condition”) is inconclusive when two of the subspaces intersect trivially. In every case is not CCZ-equivalent to a permutation.
For the set has 1,398,101 elements, and the plain search is no longer feasible. We therefore used the symmetries of the family. The two identities of Lemma 10 give , and moreover . So, in bit coordinates, is invariant under the transpose of the linear map , which has order 11. For , is also invariant under the transpose of , which has order 22. The subspaces are then searched only through the smallest element of each orbit, removing the orbits already treated, and the results are closed under the group. These searches are independent, so they can be distributed over several machines. For the search over the 63,644 orbit representatives took about 63 hours on 128 threads. For the 127,101 representatives were split over up to three servers with 200 threads each, and every finished representative was saved. This search took about three days.
The orbit-pruned search works as follows. Let be the linear map that generates the group , and let in bit coordinates, so that .
List the smallest elements of the -orbits in , as integers.
For each , let be minus the orbits of . Find all -dimensional subspaces with . Their images in the quotient are the -dimensional subspaces contained in , which we find with the plain search.
Return the union of the -orbits of all subspaces found, deduplicated by reduced echelon bases.
No subspace is missed. Let have dimension , and let be the smallest index such that meets the orbit of , say in with . Then contains , and it meets no orbit of with , because these orbits are -invariant. So is found in step 2 for this , and in step 3. Subspaces with a nontrivial stabilizer need no special treatment. They may be found several times, and step 3 removes the duplicates. The steps for different are independent. For they were run in twelve lanes ( modulo 12), each with a checkpoint file of finished indices. A final check confirms that every index from 1 to 127,101 is present. We also checked the implementation against the plain search with the same groups for (dimensions 5 to 8, with up to 5,348 subspaces) and for (dimensions 9 and 10), for . The two lists of subspaces coincide in every case (§ 8.5).
We also timed a sample of 800 representatives for each value of on the same server, at the same relative positions in the two lists of representatives. A single search costs the same for both values: the ratio of the mean CPU times is 0.97. The total cost is therefore proportional to the number of representatives. It is about 13,000 thread-hours for and 25,000 for , measured as CPU time of the hardware threads of a fully loaded server. The factor of two comes from the symmetry group, whose order is 11 instead of 22.
For and the three subspaces intersect pairwise trivially, so they span in pairs and the necessary condition is satisfied. Algorithm 1 shows that none of them is the projection of a Walsh zero space. Once the subspaces are known, this takes two seconds. The failure occurs in the last step. For each of the three subspaces , every with has dimension two, and there are exactly three admissible subspaces . Each of them meets every in a single nonzero vector. So condition (3) of Theorem 8 is a system of 511 linear equations in the 81 entries of , and this system has no solution. For each of the nine systems the repository contains a witness of infeasibility: a set of 7 to 23 of the equations whose left-hand sides sum to zero and whose right-hand sides sum to one. It also contains the bases of the three subspaces. The same happens for and : each of the three candidate projections has three admissible , and each resulting system of 7 equations in the 9 entries of has no solution. Together with the theorem of Gölöğlu and Pavlů this gives the following statement. It is a computer-assisted result for .
Corollary 12 For every even and every , the function is not CCZ-equivalent to a permutation.
Proof. For this is [16 Theorem 3]; for there is no APN permutation of . For it follows from Lemma 10 and Table 2. □
For and the necessary condition suffices. These cases are therefore within reach of the method of [16], which reports computations for and random members of the known families up to . For and , on the other hand, the necessary condition is inconclusive and no theorem applies. To our knowledge this case is new, and it is decided by Theorem 8.
Subspaces of the cubes.
Behind Table 2 is the structure of the large subspaces of . For and , every subspace of of dimension or lies in a single spread line. There are 11 and 341 such subspaces for , and 43 and 5,461 for . For , in contrast, only 21 of the 28 two-dimensional subspaces do. If this holds for all odd , the proof of [16 Theorem 3] can be followed with contained in one spread line. For one obtains exactly the line of Proposition 11. For the character-sum argument of [16] no longer gives a contradiction, by the following lemma. Here is taken with respect to the trace form.
Lemma 13 Let be odd, , and let be an -dimensional subspace of the spread line . Then .
Proof. Write with a hyperplane of , and let be the trace from to . For and we have . So if and only if , where is the orthogonal of in . Put ; since , if and only if . The kernel of is , and , which gives elements with . Multiplication by preserves and multiplies by . So all nonzero values of are taken equally often on , namely times. The total is . □
The data suggest the following.
Conjecture 14 Let be odd and . If , then contains exactly one subspace of dimension , a line of the Desarguesian spread, equal to if and only if
. If , it contains three such subspaces if and none otherwise, and none of them is the projection of a Walsh zero space of . In particular is not CCZ-equivalent to a permutation for any even .
The case of the conjecture rests on a single value in its range, . The case lies outside the range but behaves in the same way. The case rests on . The case () was computed after the conjecture was formed, and agrees with it for both and . Lemma 13 was also checked numerically for and .
Experiments
Setup and reproducibility
The core routines are written in C and called from Python. They compute difference tables and the cost (1), and implement incremental local search, vector space search, switching kernels, and an APN test for quadratic functions from their bilinear form. The test of § 6, the invariants and the experiment drivers are written in Python with NumPy. Unless stated otherwise, experiments were run on a laptop with an Apple M5 Pro processor (18 cores, 24 GB of memory). The randomized tree-search campaign of § 8.7 and experiments E7, E10 and E12 were run on servers. Each server has two AMD EPYC 7763 processors (128 physical cores, 256 hardware threads and 1 TB of memory), and we ran at low priority, in containers limited to 200 CPUs. The number of worker processes is given with each experiment.
The accompanying repository (https://github.com/peacker/ccz-projection-test-apn) contains one script per experiment (E1–E12 below) and the data files they produce. Running a script recomputes its results. A separate script compares every number reported in this section with the stored results; it does not recompute them. The repository gives the field representations (primitive polynomials) and the bit order. The random seeds are fixed in the scripts.
The checks validate different things.
APN property: every APN function found by our search programs (dimensions six to ten) was checked by computing its full difference table, independently of the method that produced it. In larger dimensions only the functions of known families are used.
Permutations: every permutation produced by the CCZ test was checked to be a bijection and APN.
Equivalences: every EA-equivalence we claim comes with an explicit certificate (), and a separate routine checks that are invertible and that is affine.
Walsh zero spaces: the projection test and sboxU return the same lists for the 14 functions of Table 3.
Completeness of exhaustive searches: this cannot be checked from the output. We rely on cross-checks with independent implementations. sboxU checks the Walsh
| Function | Spaces | perm. | List | Decide | ||||
| Alg. 1 | sboxU | Alg. 1 | sboxU | by | ||||
| 6 | 190 | no | 0.030 | 0.004 | 0.007 | 0.022 | ||
| 6 | Kim function | 222 | yes | 0.036 | 0.006 | 0.009 | 0.034 | perm. |
| 8 | 256 | no | 0.10 | 0.11 | 0.025 | 0.064 | ||
| 8 | 256 | no | 0.11 | 0.12 | 0.025 | 0.065 | ||
| 8 | 256 | no | 0.10 | 0.12 | 0.024 | 0.064 | ||
| 10 | 1,024 | no | 3.37 | 19.9 | 0.24 | 5.47 | ||
| 10 | 1,744 | no | 3.37 | 17.5 | 0.15 | 6.90 | 1 | |
| 10 | 1,024 | no | 3.46 | 19.8 | 0.24 | 5.54 | ||
| 10 | 1,624 | no | 3.21 | 17.6 | 0.15 | 6.56 | 1 | |
| 10 | Beierle–Leander #3 | 1,644 | no | 2.78 | 24.3 | 0.16 | 7.59 | |
| 10 | F3 (one class) | 1,024 | no | 2.26 | 40.8 | 0.14 | 8.63 | |
| 10 | F12 (one class) | 1,024 | no | 2.55 | 34.5 | 0.14 | 7.15 | |
| 12 | 12,286 | no | 81.6 | 3,200 | 0.63 | 744 | ||
| 12 | 8,038 | no | 64.1 | 3,507 | 0.82 | 727 |
Table 3. The projection test (Alg. 1) and the generic search of sboxU [21] on the same machine (E12). “Spaces” is the number of Walsh zero spaces and “perm.” whether the CCZ-class contains a permutation; times are in seconds. “List”: all Walsh zero spaces, one thread for both; “decide”: Alg. 1 with one thread, sboxU (enumerate_permutations_in_ccz_class) with all threads. “By” is a sufficient reason for the answer: the dimension bound, 1 a single candidate projection (with ), the lifting step of Theorem 8, perm. a permutation found.
zero spaces, and the plain search checks the symmetry-reduced search (E10). The known classification in dimension six checks the switching closure (E5).
The code, the experiments and a first draft of the manuscript were prepared with the assistance of a large language model (Claude, Anthropic). The author takes full responsibility for the content. The checks listed above are run by the scripts of the repository.
The inverse function and structured permutations (E1, E2)
For we verified Proposition 3 directly. For every the difference table of has exactly one entry equal to 4, and its four solutions form the line . For we scanned all 32,640 transpositions of . None of them decreases the cost. Exactly 255 leave it unchanged: those involving position 0, each of which replaces 6 entries equal to 4 by two entries equal to 6. All others increase the cost by at least 222. The 255 permutations reached by the cost-preserving moves cannot be improved by a further transposition either. We ran simulated annealing from for moves per run, without restarts. The temperature decreases geometrically from to , with , and a move that increases the cost by is accepted with probability . We used plain transpositions and involution-preserving moves, with three seeds per setting. An involution-preserving move picks two points ; if they form a 2-cycle it splits it into two fixed points, and otherwise it makes a 2-cycle and pairs their former partners. No run found a permutation of cost below 255. With the same budget and , 18 annealing runs started from random permutations end at costs between 4,776 and 4,926. The seeds are fixed in the script.
The families of § 4 were enumerated exhaustively, with the results of Table 1. The butterfly enumeration for (190,464 permutations) takes about three minutes.
The projection test compared with a generic search (E3, E12)
We compared the projection test (Algorithm 1) with the library sboxU [21]. sboxU implements the generic vector space search of [20], and was used to test CCZ-equivalence to permutations in [17, 23, 24]. Both programs ran on the same otherwise idle server (two AMD EPYC 7763 processors), with sboxU at commit bedb6d1. Library loading is not included in the times. We measured two tasks. The first is listing all Walsh zero spaces, with one thread for both programs: the mode of Algorithm 1 that enumerates every dimension , and the function get_WalshZeroesSpaces of sboxU. The second is deciding whether the class contains a permutation: Algorithm 1 with one thread, and the function enumerate_permutations_in_ccz_class of sboxU with all available threads.
Table 3 shows the results. Each time is a single run, so the benchmark is illustrative and we make no statistical claim about the ratios. The two programs find the same Walsh zero spaces for every function, and both find permutations in the class of the Kim function. For both take a fraction of a second, and sboxU is faster for
. From on the projection test is faster. Listing all Walsh zero spaces is the cleanest comparison of the two enumeration methods. The projection test takes 5 to 18 times less time in dimension ten, and 39 to 55 times less in dimension twelve.
For deciding, the column “by” of Table 3 gives a sufficient reason for the answer. For and it is also the step at which our implementation stops. For the two functions marked 1, a single candidate projection already excludes a permutation, because ; our implementation does not use this shortcut and still runs the lifting step. In dimension twelve both functions have , so the dimension bound of Proposition 7 settles them before any projection is examined. The large ratio in that row therefore measures this bound, which sboxU does not apply, and not Theorem 8. A generic search preceded by the same bound would also be fast there. In dimension ten three of the functions need the lifting step of Theorem 8: , and the Beierle–Leander function. For them deciding takes 0.16 to 0.24 seconds, against 5.5 to 7.6 seconds for sboxU, that is, 23 to 47 times less.
Three further points limit this comparison. First, sboxU used all threads and the projection test one. Second, the function of sboxU computes all permutations in the class, not only whether one exists; here, however, there are none except for the Kim function. Third, the projection test applies only to functions with affine Walsh supports. For the Edel–Pott function in dimension six and the Kasami function in dimension eight, whose supports are not affine, we used our own generic search (E3). It finds 25 and 1 Walsh zero spaces, respectively.
Known quadratic APN classes in dimension ten (E4, E11)
We instantiated the families F3, F4, F12 and F13 of [34 Table 3] in dimension ten, together with the Gold functions. For F4 we took with and with a primitive . For F3 and F12 we took 300 random parameter choices each. For F13 we took all functions of the shape with and all ; these 5,760 functions include the family of [38]. Of the 6,366 functions, 1,266 are APN. They have 17 distinct ortho-derivative invariants. We added the five functions of [24, 51]. Two of them have the same invariants as F13-type functions found above (with ), so this gives twenty invariants. The two coincidences are in fact EA-equivalences (E11, see below).
Every distinct APN instance is certified EA-equivalent to the representative of its group by the explicit EA-equivalence test described below. So the twenty groups are exactly twenty classes. None of them is CCZ-equivalent to a permutation. For 13 of them the set of non-bent components contains no subspace of dimension 5. For these, the dimension bound of Proposition 7 already excludes a permutation. Our values of for the families F3, F4, F12 and the Budaghyan–Helleseth–Kaleyski functions agree with those reported in [16 Table 3] (families 6, 7, 12 and 10 there). For the remaining seven classes, the non-bent components contain between one and eleven subspaces of dimension 5. Algorithm 1 shows that none of them is the projection of a Walsh zero space. For four of these classes there is a single candidate, so the spanning condition of Proposition 7 already excludes a permutation. For the other three the necessary condition is satisfied: the two Gold classes and the class with two candidate projections. There the candidate projections intersect pairwise trivially and therefore span , so Proposition 7 is inconclusive and the projection test is needed. For the Gold functions the conclusion also follows from the theorem of [15]. For the other class it was obtained in [24] with sboxU. Algorithm 1 decides these cases in 0.15 to 0.25 seconds, while sboxU takes 5 to 8 seconds on the same machine (§ 8.3).
To make the conclusion independent of the invariant, we applied the test to every distinct APN function of the experiment, 402 functions in total. None is CCZ-equivalent to a permutation, and 256 of them are already excluded by the dimension bound of Proposition 7 (). For the families known at the time, this confirms the result of Gölöğlu and Pavlıu [16] by an independent computation. The F13-type classes with parameters in F4 that have contain instances of [24], which were tested there.
Experiment E11 treats the sources of quadratic APN functions in dimension ten that the list above does not cover. We group their APN instances by the ortho-derivative invariant. Then we prove every coincidence by an explicit EA-equivalence . In that case the ortho-derivatives satisfy , so the equivalence can be recovered through the ortho-derivative, as in [50]. We use a plain depth-first search over the images of a basis under , pruned by point invariants of and . A candidate is accepted only if is affine, which we verify directly. (A general algorithm for this problem is given by Kaleyski and Sunde [52].) By [49], EA- and CCZ-equivalence coincide for quadratic APN functions. The search is exhaustive. It tries every image of a basis under that is compatible with the relation , and the point invariants it uses for pruning are preserved by that relation, so no equivalence is lost. It takes at most a few seconds per pair. The certificates of E4, E5 and E11 are stored in the repository, together with a short script that checks them without the search. Each of the 373 APN instances of E11 is certified to be EA-equivalent to the representative of its class.
Zheng et al. [33]. We used the three instances given explicitly in the preprint version of their paper (arXiv:2101.11535v1, Table III): the function of their family F15 and the two sporadic instances. We took them for every primitive element of up to Frobenius. We also took 200 random members of the family of their Theorem 3.3. The first two instances are APN for every primitive element, the third only for two of the 60 primitive elements up to Frobenius. All of them are EA-equivalent to known functions. The first two lie in the F13-type classes that contain the fourth and the second instance of [24], respectively. The third is equivalent to the third instance of [24]. The APN members of the family lie in the classes of , F3 and F13. We could not access a list of the instances of the journal version, whose abstract mentions two instances of an infinite family.
Gölöğlu’s biprojective families and [39] for all , and the first family of Calderini, Li and Villa [40 Theorem 3] for all parameters. and the latter family give two of the F13-type classes. gives the two F13-type classes that contain the second and fourth instance of [24]. These are the classes of each of and counted in [36 Theorem 5.1]. Random members of Carlet’s family give the two classes of F3.
Budaghyan, Ivkovic and Kaleyski [17 Table 2]. All six functions, instantiated with either primitive element of , are APN. Their ortho-derivatives have exactly the differential spectra printed there. Five of them lie outside the twenty classes above and have pairwise different invariants, so they are five further classes. The second function of their table, as printed, is EA-equivalent to the function , primitive in , of Edel, Kyureghyan and Pott [53]. This is the F13-type class with , , above.
The function of Li, Zhou, Li and Qu ([41]; Theorem 5 of the preprint arXiv:2105.08464v1), and all eleven APN members of the second family of Calderini, Li and Villa [40 Theorem 4], which contains it. They are EA-equivalent to the first function of [17 Table 2].
Yu et al. [42]. The representative of the class of given there is EA-equivalent to , as stated in [42]. The other two classes of that classification are those of and .
For each of the five further classes, the non-bent components contain no subspace of dimension five (). So Proposition 7 excludes a permutation. This agrees with the check made with sboxU in [17], and for these classes our test is an independent confirmation. In total, in the instances we examined we find 25 classes of quadratic APN functions in dimension ten (Table 4). None of them is CCZ-equivalent to a permutation.
Table 4. The 25 classes of quadratic APN functions in dimension ten represented by the instances examined in E4 and E11. is the largest dimension of a subspace of (there are 341 non-bent components in every case). The last column says what excludes a permutation: “” is the dimension bound of Proposition 7; “one projection” means that contains a single 5-dimensional subspace, so the spanning condition of Proposition 7 fails; “Thm. 8” means that the candidate projections span in pairs and the projection test is needed. No class is CCZ-equivalent to a permutation.
The count 25 is exact for the instances we considered, but it is not a classification of the families. For F4 we took representatives of all parameters up to the equivalences of Lemma 10. We took all parameters for F13 with parameters in , for the biprojective families of Gölöglü and for the two families of Calderini, Li and Villa. We also took all published sporadic instances we could obtain. For F3 and F12 we took 300 random parameter choices each, for Carlet’s family 50, and for the family of Zheng et al. 200. For Zheng et al. we used the instances of the preprint version. A class of these sampled families that our samples missed would be a known class that we did not test.
The family (E9, E10)
The computations of Section 7 are experiments E9 and E10. E9 covers and the subspaces of the cubes, on the laptop. E10 covers and , on the servers. For each and each , they list the subspaces of of dimensions and , translate them to field coordinates through the dual basis of the trace form, and run Algorithm 1. For the computation of takes about one minute and the parallel subspace search about five minutes. The final step of Algorithm 1 takes two seconds. The same subspace search on a single core took four hours. The results are those of Table 2. For , E10 uses the symmetry reduction of Section 7. For it ran in one go, in about 63 hours on 128 threads; computing takes 20 minutes. For the orbit representatives were split into 12 lanes that ran on up to three servers. Every finished representative was saved with its index and the subspaces found, so the work could be moved between servers and survive reboots. The repository contains these lane files, the merged result, and a check that every index from 1 to 127,101 is present. A list of SHA-256 hashes of all result files fixes their content.
Two further computations support these results. First, we compared the symmetry-reduced search with the plain search, with the same groups (E10, symmetry check). For we used dimensions 5 to 8 and found up to 5,348 subspaces, in about a minute on the laptop. For we used dimensions 9 and 10; the plain search takes about three minutes per case on 128 threads. The two lists coincide in all 18 cases. Second, for and we recorded where Theorem 8 fails for each of the three candidate projections (Section 7). This takes about one second per projection.
Switching closure (E5)
Table 5 summarizes the switching computations of § 5. In each dimension we computed the switching closure of the sources over switching paths whose intermediate functions remain quadratic, as described in § 5. Every nonzero class of every quotient was formed. Every quadratic neighbour that is not a new class was certified EA-equivalent to a stored class. In dimensions eight, nine and ten no quadratic class in the computed closure has a switching neighbour of degree three or more. Among the power functions only the Gold functions have nontrivial switchings, in all three dimensions and in dimension eight. The Kasami, Welch, Niho, Dobbertin and inverse functions have none in these dimensions. In dimension eight the closure has 17 classes, none of which is CCZ-equivalent to a permutation. This is consistent with [24], where switching was applied to all quadratic APN functions known in dimension eight. In dimension ten the closure of the 25 classes contains no other class. Only , the two F4 classes and four of the five classes of [17] have nontrivial switching neighbours. The classes of F3, F12, F13 and of [24] have none.
Searching for new quadratic APN functions in dimension ten (E6–E8)
Since all 25 classes examined here are excluded, an APN permutation CCZ-equivalent to a quadratic function would have to come from a class outside this tested set. We tried three generators. The first (E6) is a feasibility test in dimensions six to eight. It shows that unstructured search does not scale, so we did not run it in dimension ten. The other two (E7, E8) run in dimension ten.
Search over bilinear forms (E6).
A quadratic function is APN if and only if its alternating bilinear form satisfies for all linearly independent . We build on for increasing . The extension by amounts to choosing a linear map with for all nonzero . We explore these choices by a randomized depth-first search. In dimension six the search reaches all thirteen classes from 3,000 restarts, in three seconds; their 13 invariants are pairwise distinct, so every class is reached. In dimension seven it finds 237 solutions with 194 distinct invariants, hence at least 194 classes, where 488 classes are known [46]. In dimension eight it finds no solution in 36 runs of nodes. Unstructured search is therefore not a viable generator beyond dimension seven. This is consistent with the use of self-equivalences in [24].
Symmetry-restricted univariate families (E7).
We sampled quadratic polynomials , , in 522 families:
coefficients in (Frobenius-invariant functions), with four densities;
coefficients in the subfields and ;
sparse polynomials with two to five terms;
polynomials whose exponents lie in a single residue class modulo , for each divisor of 1023 (functions with for of order ).
For quadratic functions the APN property is decided from the bilinear matrix in about 40 s, and faster for the many candidates rejected early. Of the 522 families, 372 residue families contain no exponent , so they have no candidates; the other 150 families sample. Each of them got a maximum budget of 2,560 batches of 2,000 candidates, with a fixed seed. Before each batch a family stops if it has already found 2,000 APN functions, counted with repetitions; so it ends with fewer than 4,000, and all of them are kept. 56 families stopped in this way, and 94 used their full budget. In total we tested 535,492,000 candidates, out of a maximum of . They gave 166,157 APN functions counted with repetitions, and 105,595 distinct ones; for instance, a family with a single exponent contains at most 1,023 distinct functions. The repository records these numbers for every family, and lists every distinct function with its test result. Every distinct APN function found was tested individually with Algorithm 1. None is CCZ-equivalent to a permutation. Their invariants are those of 11 of the twenty classes of E4, and no other invariant occurs. The run took 15 minutes on 64 server threads.
Tree search with prescribed self-equivalences (E8).
We ran the deterministic tree search of Beierle and Leander [54] for each of the 195 classes of linear self-equivalences of considered in [24], with a time limit of five minutes per class. The search terminated for 69 classes. Solutions were found in six classes, giving 686 APN functions with nine distinct invariants, all among those of the twenty classes of E4. The test applied to each of the 686 functions finds no CCZ-equivalent permutation. For the 126 classes in which the search did not terminate, we then ran the randomized version of the tree search for 24 hours on 128 threads. That is about one CPU-day per class (6,144 runs of 30 minutes). Solutions were again found only in the six classes above. Together with the deterministic runs we obtained 4,638 distinct APN functions with 16 distinct invariants, all among those of the twenty classes of E4. None of the 4,638 functions is CCZ-equivalent to a permutation. In particular, no solution was found in the two classes for which [24] reports that solutions must exist but were not found after 16 CPU-days each.
Conclusions and future work
We gave a parametrization of the Walsh zero spaces of functions with affine Walsh supports. It turns the test for CCZ-equivalence to a permutation into searches for subspaces of and for bilinear maps between them. This projection test decides the cases in which the necessary condition of [15, 16] is inconclusive. For listing all Walsh zero spaces it is 39 to 55 times faster than the generic search of sboxU in dimension twelve, on the functions we measured. With it we settled the family in all even dimensions up to 24, by computation for . This includes a case in dimension 18 that the known necessary condition leaves open.
In dimension ten we checked the 25 classes of quadratic APN functions represented by the published instances we examined. Five of them, from [17], are not in the earlier lists; for these our test confirms the result obtained there with sboxU. We computed the quadratic switching closure of the source functions listed in Table 5 in dimensions eight to ten, and tested every function found by two generators of quadratic APN functions in dimension ten. No APN permutation was found. For , the inverse function fails the APN condition exactly on the two-dimensional subspaces , and swapping two entries of its lookup table never brings it closer to the APN property. The butterflies with power-based keyed permutations, the cyclotomic maps and the switched inverse functions that we enumerated contain no permutation of closer to the APN property than the inverse function.
Several directions remain open.
Conjecture 14. It holds in all computed cases, up to . A proof would settle the family in all even dimensions. It needs two ingredients. The first is a description of the subspaces of dimension and of the cubes for odd . The second is an analysis of the case , where the argument of [16] no longer applies.
Non-affine Walsh supports. Theorem 8 requires affine supports. Plateaued functions need not have affine supports. Proposition 7 still applies to plateaued and general functions, so an extension of the projection test to them would be useful. Natural test cases are the Kasami function in dimension ten, which is not covered by [15] since , and the Dobbertin function .
New quadratic APN functions in dimension ten. The bottleneck of the CCZ approach in dimension ten is the small number of known quadratic APN classes. The complete classification of the functions with coefficients in [42] gives no new class. New classes therefore have to come from larger coefficient fields or other structures. On the functions we tested, the test costs a fraction of a second per function. So any generator that produces many new classes can be combined with it directly, for instance the constructions of Beierle et al. [23] adapted to dimension ten.
Dimension twelve. The two functions we measured in dimension twelve are decided in under a second, by the dimension bound, and listing all their Walsh zero spaces takes about a minute (§ 8.3). Testing all known quadratic APN classes in dimension twelve, and their switching closure, seems a plausible next step. The functions of Gölöğlu and Kölsch [48] in dimension twelve would be natural test cases.
Two-step switching. The switching graph of quadratic APN functions in dimension ten is small. Switching simultaneously in two directions, , leads to quadratic rather than linear systems and is a natural next step.
Program search. Romera-Paredes et al. recently used large language models to search for programs that construct combinatorial objects [55]. A candidate construction of a permutation, given as a program that works in every dimension, can be scored exactly by cost. The big APN problem is therefore a natural target for such methods.
Statements and Declarations
Funding: No dedicated funding was received for conducting this study.
Competing interests: The author has no competing interests to declare that are relevant to the content of this article.
Data and code availability: All scripts, the C and Python sources, the generated data and the expected results are publicly available at https://github.com/peacker/ccz-projection-test-apn (release v1.0, commit 0ac04cd). The repository contains one script per experiment, which recomputes its results, and a script that compares every number reported in this paper with the stored results.
Use of AI tools: The code, the experiments and a first draft of the manuscript were prepared with the assistance of a large language model (Claude, Anthropic). § 8 lists the checks applied to the results and what each of them validates. The author takes full responsibility for the content.
References
- [1]Nyberg, K.: 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. Lecture Notes in Computer Science, vol. 765, pp. 55–64. Springer, Berlin, Heidelberg (1993). https://doi.org/10.1007/3-540-48285-7_6
- [2]Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021). https://doi.org/10.1017/9781108606806
- [3]Gold, R.: Maximal recursive sequences with 3-valued recursive cross-correlation functions (corresp.). IEEE Trans. Inf. Theory 14(1), 154–156 (1968) https://doi.org/10.1109/TIT.1968.1054106
- [4]Kasami, T.: The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes. Inf. Control. 18(4), 369–394 (1971) https://doi.org/10.1016/S0019-9958(71)90473-6
- [5]Dobbertin, H.: Almost perfect nonlinear power functions on GF(2ⁿ): The Welch case. IEEE Trans. Inf. Theory 45(4), 1271–1275 (1999) https://doi.org/10.1109/18.761283
- [6]Dobbertin, H.: Almost perfect nonlinear power functions on GF(2ⁿ): The Niho case. Inf. Comput. 151(1-2), 57–72 (1999) https://doi.org/10.1006/inco.1998.2764
- [7]Hou, X.: Affinity of permutations of F₂ⁿ. Discret. Appl. Math. 154(2), 313–325 (2006) https://doi.org/10.1016/j.dam.2005.03.022
- [8]Browning, K.A., Dillon, J.F., McQuistan, M.T., Wolfe, A.J.: An APN permutation in dimension six. In: Finite Fields: Theory and Applications. Contemporary Mathematics, vol. 518, pp. 33–42. American Mathematical Society, Providence, RI (2010). https://doi.org/10.1090/conm/518/10194
- [9]Carlet, C., Charpin, P., Zinoviev, V.A.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr. 15(2), 125–156 (1998) https://doi.org/10.1023/A:1008344232130
- [10]Perrin, L., Udovenko, A., Biryukov, A.: Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem. In: Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9815, pp. 93–122. Springer, Berlin, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_4
- [11]Canteaut, A., Duval, S., Perrin, L.: A generalisation of Dillon’s APN permutation with the best known differential and nonlinear properties for all fields of size 2⁴ᵏ⁺². IEEE Trans. Inf. Theory 63(11), 7575–7591 (2017) https://doi.org/10.1109/TIT.2017.2676807
- [12]Canteaut, A., Perrin, L., Tian, S.: If a generalised butterfly is APN then it operates on 6 bits. Cryptogr. Commun. 11(6), 1147–1164 (2019) https://doi.org/10.1007/s12095-019-00361-x
- [13]Canteaut, A., Perrin, L.: On CCZ-equivalence, extended-affine equivalence, and function twisting. Finite Fields Their Appl. 56, 209–246 (2019) https://doi.org/10.1016/j.ffa.2018.11.008
- [14]Beierle, C., Brinkmann, M., Leander, G.: Linearly self-equivalent APN permutations in small dimension. IEEE Trans. Inf. Theory 67(7), 4863–4875 (2021) https://doi.org/10.1109/TIT.2021.3071533
- [15]Göloğlu, F., Langevin, P.: Almost perfect nonlinear families which are not equivalent to permutations. Finite Fields Their Appl. 67, 101707 (2020) https://doi.org/10.1016/j.ffa.2020.101707
- [16]Göloğlu, F., Pavlů, J.: On CCZ-inequivalence of some families of almost perfect nonlinear functions to permutations. Cryptogr. Commun. 13(3), 377–391 (2021) https://doi.org/10.1007/s12095-021-00476-0
- [17]Budaghyan, L., Ivkovic, I., Kaleyski, N.S.: Triplicate functions. Cryptogr. Commun. 15(1), 35–83 (2023) https://doi.org/10.1007/s12095-022-00587-2
- [18]Bénéteau, S.H., Goluboff, N., Kölsch, L., Vaghasiya, D.: On the Walsh spectra of quadratic APN functions. IEEE Trans. Inf. Theory 72(7), 5207–5216 (2026) https://doi.org/10.1109/TIT.2026.3695003 . Preprint: arXiv:2510.12008
- [19]Chase, B., Lisonek, P.: Construction of APN permutations via Walsh zero spaces. Cryptogr. Commun. 14(6), 1345–1357 (2022) https://doi.org/10.1007/s12095-022-00580-9
- [20]Bonnetain, X., Perrin, L., Tian, S.: Anomalies and vector space search: Tools for s-box analysis. In: Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part I. Lecture Notes in Computer Science, vol. 11921, pp. 196–223. Springer, Berlin, Heidelberg (2019). https://doi.org/10.1007/978-3-030-34578-5_8
- [21]Perrin, L., Alich, J., Baudrin, J., Boeuf, A., Bonnetain, X., Couvreur, A., Fruchon, M., Joly, M., Galissant, P., Stennes, L.: sboxU: black-box analysis of discrete functions. Software, https://github.com/lpp-crypto/sboxU. Commit bedb6d1 (2026)
- [22]Edel, Y., Pott, A.: A new almost perfect nonlinear function which is not quadratic. Adv. Math. Commun. 3(1), 59–81 (2009) https://doi.org/10.3934/amc.2009.3.59
- [23]Beierle, C., Langevin, P., Leander, G., Polujan, A.A., Rasoolzadeh, S.: Millions of inequivalent quadratic APN functions in eight variables. CoRR abs/2508.04644 (2025) https://doi.org/10.48550/arXiv.2508.04644 . Version 2, August 2026
- [24]Beierle, C., Leander, G.: New instances of quadratic APN functions. IEEE Trans. Inf. Theory 68(1), 670–678 (2022) https://doi.org/10.1109/TIT.2021.3120698
- [25]Yu, Y., Wang, M., Li, Y.: A matrix approach for constructing quadratic APN functions. Des. Codes Cryptogr. 73(2), 587–600 (2014) https://doi.org/10.1007/s10623-014-9955-3
- [26]Weng, G., Tan, Y., Gong, G.: On quadratic APN functions and their related algebraic objects. In: International Workshop on Coding and Cryptography (WCC 2013), Bergen, Norway, pp. 48–57 (2013)
- [27]Taniguchi, H.: On some quadratic APN functions. Des. Codes Cryptogr. 87(9), 1973–1983 (2019) https://doi.org/10.1007/s10623-018-00598-2
- [28]Yu, Y., Perrin, L.: Constructing more quadratic APN functions with the QAM method. Cryptogr. Commun. 14(6), 1359–1369 (2022) https://doi.org/10.1007/s12095-022-00598-z
- [29]Beierle, C., Leander, G., Perrin, L.: Trims and extensions of quadratic APN functions. Des. Codes Cryptogr. 90(4), 1009–1036 (2022) https://doi.org/10.1007/s10623-022-01024-4
- [30]Beierle, C., Langevin, P., Leander, G., Polujan, A., Rasoolzadeh, S.: Millions of inequivalent quadratic APN functions in eight variables. Dataset, Zenodo (2025). https://doi.org/10.5281/zenodo.16752428
- [31]Kuznetsov, O.: Quadratic APN functions in dimension 8 via Gröbner basis search in a self-equivalence subspace. CoRR abs/2606.11967 (2026) https://doi.org/10.48550/arXiv.2606.11967
- [32]Dobbertin, H.: Almost perfect nonlinear power functions on GF(2^n): A new case for n divisible by 5. In: Finite Fields and Applications, Fifth International Conference on Finite Fields and Applications Fq5, Augsburg, Germany, August 2-6, 1999, pp. 113–121. Springer, Berlin, Heidelberg (2001). https://doi.org/10.1007/978-3-642-56755-1_11
- [33]Zheng, L., Kan, H., Li, Y., Peng, J., Tang, D.: Constructing new APN functions through relative trace functions. IEEE Trans. Inf. Theory 68(11), 7528–7537 (2022) https://doi.org/10.1109/TIT.2022.3186899 . Preprint: arXiv:2101.11535
- [34]Kaleyski, N.S.: Invariants for EA- and CCZ-equivalence of APN and AB functions. Cryptogr. Commun. 13(6), 995–1023 (2021) https://doi.org/10.1007/s12095-021-00541-8
- [35]Budaghyan, L., Carlet, C.: Classes of quadratic APN trinomials and hexanomials and related structures. IEEE Trans. Inf. Theory 54(5), 2354–2357 (2008) https://doi.org/10.1109/TIT.2008.920246
- [36]Göloğlu, F., Kölsch, L.: Equivalences of biprojective, almost perfect nonlinear functions. Comb. Theory 5(3) (2025) https://doi.org/10.5070/C65365555 . Preprint: arXiv:2111.04197
- [37]Budaghyan, L., Carlet, C., Leander, G.: Constructing new APN functions from known ones. Finite Fields Their Appl. 15(2), 150–159 (2009) https://doi.org/10.1016/j.ffa.2008.10.001
- [38]Budaghyan, L., Helleseth, T., Kaleyski, N.S.: A new family of APN quadrinomials. IEEE Trans. Inf. Theory 66(11), 7081–7087 (2020) https://doi.org/10.1109/TIT.2020.3007513
- [39]Göloğlu, F.: Biprojective almost perfect nonlinear functions. IEEE Trans. Inf. Theory 68(7), 4750–4760 (2022) https://doi.org/10.1109/TIT.2022.3157798
- [40]Calderini, M., Li, K., Villa, I.: Extending two families of bivariate APN functions. Finite Fields Their Appl. 88, 102190 (2023) https://doi.org/10.1016/j.ffa.2023. 102190 . Preprint: arXiv:2204.07462
- [41]Li, K., Zhou, Y., Li, C., Qu, L.: Two new families of quadratic APN functions. IEEE Trans. Inf. Theory 68(7), 4761–4769 (2022) https://doi.org/10.1109/TIT.2022.3157810 . Preprint: arXiv:2105.08464
- [42]Yu, Y., Li, J., Ichanska, N., Kaleyski, N.S.: Classification of quadratic APN functions with coefficients in F₂ in dimension 10. Appl. Algebra Eng. Commun. Comput. (2025) https://doi.org/10.1007/s00200-025-00711-8 . Online first. Preprint: Cryptology ePrint Archive, Paper 2024/1778
- [43]Yu, Y., Kaleyski, N.S., Budaghyan, L., Li, Y.: Classification of quadratic APN functions with coefficients in F₂ for dimensions up to 9. Finite Fields Their Appl. 68, 101733 (2020) https://doi.org/10.1016/j.ffa.2020.101733
- [44]Ichanska, N., Berg, S., Kaleyski, N.S., Yu, Y.: Pushing the QAM method for finding APN functions further. Cryptogr. Commun. 18(3), 727–762 (2026) https://doi.org/10.1007/s12095-025-00851-1 . Preprint: Cryptology ePrint Archive, Paper 2024/1838
- [45]Budaghyan, L., Calderini, M., Villa, I.: On equivalence between known families of quadratic APN functions. Finite Fields Their Appl. 66, 101704 (2020) https://doi.org/10.1016/j.ffa.2020.101704
- [46]Kalgin, K., Idrisova, V.: The classification of quadratic APN functions in 7 variables and combinatorial approaches to search for APN functions. Cryptogr. Commun. 15(2), 239–256 (2023) https://doi.org/10.1007/s12095-022-00588-1
- [47]Beierle, C., Langevin, P., Leander, G., Polujan, A., Rasoolzadeh, S.: Classification of quadratic APN functions up to EA-equivalence. Dataset, Zenodo (2026). https://doi.org/10.5281/zenodo.22010376
- [48]Göloğlu, F., Kölsch, L.: Triprojective almost perfect nonlinear permutations and functions. CoRR abs/2605.17545 (2026)arxiv.org/abs/2605.17545
- [49]Yoshiara, S.: Equivalences of quadratic APN functions. J. Algebraic Combin. 35(3), 461–475 (2012) https://doi.org/10.1007/s10801-011-0309-1
- [50]Canteaut, A., Couvreur, A., Perrin, L.: Recovering or testing extended-affine equivalence. IEEE Trans. Inf. Theory 68(9), 6187–6206 (2022) https://doi.org/10.1109/TIT.2022.3166692
- [51]Beierle, C., Leander, G.: New Instances of Quadratic APN Functions in Small Dimension. Dataset, Zenodo, version 2.1 (2021). https://doi.org/10.5281/zenodo.4738942
- [52]Kaleyski, N.S., Sunde, J.: Efficiently deciding and recovering CCZ and EA equivalence for arbitrary vectorial Boolean functions using the partition refinement framework. Cryptology ePrint Archive, Paper 2026/940 (2026). https://eprint.iacr.org/2026/940
- [53]Edel, Y., Kyureghyan, G.M., Pott, A.: A new APN function which is not equivalent to a power mapping. IEEE Trans. Inf. Theory 52(2), 744–747 (2006) https://doi.org/10.1109/TIT.2005.862128
- [54]Beierle, C.: quadratic.apn: Tree Search for Quadratic APN Functions, v1.0. Software, Zenodo (2020). https://doi.org/10.5281/zenodo.4305864
- [55]Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M.P., Dupont, E., Ruiz, F.J.R., Ellenberg, J.S., Wang, P., Fawzi, O., Kohli, P., Fawzi, A.: Mathematical discoveries from program search with large language models. Nat. 625(7995), 468–475 (2024) https://doi.org/10.1038/s41586-023-06924-6