22.10.2021  Ausgabe 6/2021 Open Access
Invariants for EA and CCZequivalence of APN and AB functions
 Zeitschrift:
 Cryptography and Communications > Ausgabe 6/2021
Wichtige Hinweise
This article belongs to the Topical Collection: Boolean Functions and Their Applications V
Guest Editors: Lilya Budaghyan, Claude Carlet, Tor Helleseth and Kaisa Nyberg
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
A vectorial Boolean function, or (
n,
m)function, is any mapping from the vector space
\({\mathbb {F}_{2}^{n}}\) over the finite field
\(\mathbb {F}_{2} = \{ 0, 1 \}\) to the vector space
\({\mathbb {F}_{2}^{m}}\), where
n and
m are arbitrary natural numbers. In the particular case when
m = 1, we refer to (
n,1)functions simply as Boolean functions. In this sense, an (
n,
m)function can be seen as an
mdimensional vector of (
n,1)functions, hence the name. Vectorial Boolean functions are natural objects that have many applications within computer science and mathematics. Perhaps the simplest way to appreciate their utility is to observe that an (
n,
m)function can be interpreted as an operation that accepts
n bits as input, and returns
m bits as output. Since virtually all data can be encoded as sequences of bits, this means that any transformation that operates on data of any kind can be naturally represented in terms of Boolean functions and vectorial Boolean functions. In particular, this is how all data is represented on an electronic computer; and one need look no further than the indicator function of a subset, or the incidence matrix of a graph to find examples of mathematical structures that can be encoded using binary functions. The spectrum of applications of vectorial Boolean functions includes areas as diverse as set theory, artificial intelligence, and algorithm design.
Vectorial Boolean functions also play a crucial role in cryptography, where they are used as building blocks of both stream and block ciphers. In both cases, the properties of the functions used directly influence the ultimate strength of the encryption; and thus, investigating the cryptographic properties of (
n,
m)functions, and finding concrete instances of such functions that provide good resistance against various types of cryptanalytic attacks is an important topic of research. A prominent example is the Rijndael block cipher, selected as the Advanced Encryption Standard (AES) by the US National Institute of Standards and Technology (NIST), which is one of the most secure and arguably the most popular block cipher to date [
29,
30]. One of the major factors contributing to the security of Rijndael is a strong vectorial Boolean function that lies at the core of the encryption. In general, if a particular form of cryptanalysis succeeds because of a cryptographically weak function, this is due to the function having some undesirable property that can be exploited by the attacker. Researchers have identified several properties and statistics that measure the resistance of a function to different kinds of attacks. This quantification of the cryptographic strength of vectorial Boolean functions has the great advantage that it allows the security of a given function to be measured in an objective and systematic way; and, what is of equal importance, provides researchers in the field with a concrete goal, namely to find functions attaining the optimum values of these properties.
Anzeige
Two of the most powerful attacks against modern block ciphers are the socalled differential cryptanalysis [
5] and linear cryptanalysis [
45]. The statistics that measure the resistance of a function
F to these two attacks are called differential uniformity (denoted Δ
_{F}) and nonlinearity (denoted
\(\mathcal {N}{\mathscr{L}}(F)\)), respectively. The differential uniformity of a function should be as low as possible, and the nonlinearity should be as high as possible in order to resist these two attacks. In the case of (
n,
m)functions with
n =
m (which is arguably the most practically significant and, therefore, wellstudied case), the classes of (
n,
n)functions that achieve optimum differential uniformity and nonlinearity are called almost perfect nonlinear (APN) and almost bent (AB) functions, respectively. These two classes were introduced in the early 90’s [
3,
46,
47], and have been the subject of intense study ever since. The fact that these functions are cryptographically optimal implies that they have very little structure or patterns that can be exploited by a malicious attacker; unfortunately, this also means that, in general, they have very few properties that can be used analytically or constructively (we note, however, that we are not claiming that e.g. APN and AB functions must lack any kind of structure whatsoever; and we remark that some cryptographically optimal functions do have strong structural properties; for instance, the earliest known APN functions are monomials, and so they have a very simple polynomial representation). Intuitively, this is one explanation for why their study is difficult, both theoretically and computationally. This is witnessed by the fact that a number of longstanding questions and problems on APN and AB functions remain open to this day. The reader is referred to [
25] for a comprehensive overview of the background and results in the area, including a list of open problems.
One promising vector of attack for resolving some of these problems is to find new instances of APN and AB functions. In this respect, it must be noted that any AB function is necessarily APN; the converse does not hold in general, although any quadratic APN function over
\(\mathbb {F}_{2^{n}}\) with odd
n is AB [
26]. This means that AB functions provide optimum resistance to both differential and linear cryptanalysis; and that searching for APN functions is a natural way to search for AB functions as well. The number of (
n,
n)functions is astronomical even for small values of
n: there are
\((2^{n})^{2^{n}}\) such functions over the finite field
\(\mathbb {F}_{2^{n}}\) for any natural number
n, and so for values as small as
n = 6, an exhaustive search is out of the question at the current level of computational technology. On the one hand, this makes it necessary to use more sophisticated combinations of mathematical characterizations and computational methods in order to find new APN functions; on the other hand, the large number of (
n,
n)functions suggests that the total number of APN functions (despite them being a rather special class of functions) also grows rapidly with the dimension
n, and their enumeration and classification quickly become infeasible.
To make the classification of some given class of objects manageable, a typical approach is to only classify them up to some suitable notion of equivalence that preserves the properties of interest to our study. In the case of APN and AB functions, these are the differential uniformity and the nonlinearity. At present, there are several known notions of equivalence on vectorial Boolean functions that preserve both of these properties. The most general known relation of this type is called CarletCharpinZinoviev equivalence (after the names of its inventors) [
26], or CCZequivalence for short; results on APN and AB functions in the literature are typically given up to CCZequivalence. A less general, but also very frequently used equivalence relation is the extended affine equivalence, or EAequivalence for short. Although it is known to be strictly less general than CCZequivalence (even if we allow taking inverses of permutations in addition to EAequivalence) [
20], it has been shown that CCZ and EAequivalence coincide in the case of quadratic APN functions (in the sense that two quadratic APN functions are CCZequivalent if and only if they are EAequivalent) [
53]; since the vast majority of known APN functions are quadratic, this makes the study of EAequivalence and its properties almost as useful in practice as that of CCZequivalence.
Classifying functions up to CCZequivalence (or EAequivalence) dispenses, at least partly, with the problem of their overwhelming number, but it raises another issue, namely: how to prove the equivalence or inequivalence of two given functions. This is a matter of great practical importance in the study of APN functions, since any “new” function obtained from a computational search or theoretical construction needs to be compared for equivalence against representatives from the equivalence classes of all known APN functions; this “new” function is then genuinely new only in the case that it is not equivalent to any of these representatives. Despite the definitions of both EAequivalence and CCZequivalence being natural and simple, testing whether two given functions are equivalent is a very hard problem. Showing the inequivalence of two functions theoretically is only possible in some special cases, and is still very laborious; see e.g. [
17], which contains a theoretical proof of inequivalence to the Gold, Kasami, and inverse power APN functions of an infinite family of APN binomials. Computationally testing equivalence is quite difficult too: to the best of our knowledge, there is currently no algorithm that can decide the CCZequivalence of any two functions directly from the definition; instead, one typically uses tests relying on the isomorphism of linear codes [
11,
37]. These tests have a number of shortcomings: they are difficult to implement (provided one does not have a working implementation of a test for linear code isomorphism); the computation time and memory consumption is significant; and, at least in the case of some implementations, these tests can give false negatives. More precisely, the procedure that we have available either outputs the form of the isomorphism showing that the linear codes corresponding to the tested functions are equivalent, or it outputs “false” in the case that no such isomorphism can be found; the latter, however, can happen either because the procedure has traversed the entire search space and found no such isomorphism (in which case we can correctly conclude that the functions are inequivalent); or it can be because the procedure has run out of memory and has been forced to abort early, in which case we can still get “false” as a result even though the functions may be equivalent. Despite this, the linear code test remains the only option for testing CCZequivalence in the general case. Other algorithms, operating from first principles, have been published for dealing with specialized cases of CCZ and EAequivalence, such as in the case of affine and linear equivalence [
6], and the socalled restricted EAequivalence [
22,
48]; and, more recently, an algorithm relying on invariants for testing EAequivalence for even dimensions [
42], and an algorithm for testing the EAequivalence of quadratic functions (for both even and odd dimensions) [
23].
Anzeige
The classification of functions into equivalence classes can be significantly simplified and spedup by means of invariants. An invariant is a property or statistic that is preserved under a given equivalence relation. For instance, if
p is an integervalued statistic computable for any (
n,
n)function
F, and is also a CCZinvariant, then for any
\(F, G : {\mathbb {F}_{2}^{n}} \rightarrow {\mathbb {F}_{2}^{n}}\) that are CCZequivalent, we must have
p(
F) =
p(
G). Invariants can facilitate the classification in several ways. Suppose that a tentative new instance of an APN function is obtained via some construction or computer search. First, the values of different invariants for this potentially new function can be computed and compared with those values for representatives from the known classes of APN functions. If the set of values for the new function does not match that of any known representative, then we can immediately conclude that the discovered function is indeed new, and no further tests need to be performed. If, however, the set of values does coincide with that of one or more of the known representatives, then only the representatives with that exact same set of values need to be tested for equivalence against the newly discovered function; this will typically be a significantly smaller set of functions. Most invariants are numerical values, which makes it easier to verify that the computation has produced a meaningful result, and precludes the possibility of false positives or false negatives. Finally, some invariants have a natural interpretation, and describe some property or structure of the function, which can be significant and useful in contexts other than deciding equivalence. Constantly updated tables of the known invariants for all known CCZinequivalent APN representatives can be found online at [
1].
In this paper, we survey the known invariants for (
n,
n)functions, with an emphasis on their utility for the classification of APN and AB functions. We evaluate each invariant with respect to several desirable properties. Ideally, we would like an invariant to be:

simple: in other words, that it should not require any complicated algorithms or special software for its computation; ideally, an invariant would be easily implementable on any general purpose programming language without specialized tools or knowledge;

efficient: that the invariant can be computed quickly, and without using too much memory for a reasonable range of dimensions n;

useful: that it should take many different values for APN functions from distinct equivalence classes.
2 Preliminaries
Let
n,
m be natural numbers. An (
n,
m)
function, or
vectorial Boolean function is a mapping between the vector spaces
\({\mathbb {F}_{2}^{n}}\) and
\({\mathbb {F}_{2}^{m}}\) over the finite field with two elements,
\(\mathbb {F}_{2}\). In the following, we concentrate on the case
n =
m, but we remark in passing that (
n,1)functions are called simply
Boolean functions (as opposed to vectorial Boolean functions). An (
n,
m)function
F can be seen as a vector
\(F = (f_{1}, f_{2}, \dots , f_{m})\) of Boolean (
n,1)functions, each function
f
_{i}(
x) giving the value of the
ith coordinate of
F(
x) for
\(x \in {\mathbb {F}_{2}^{n}}\). The functions
f
_{i} are called the
coordinate functions of
F. The
component functions of
F are all nonzero linear combinations of its coordinate functions. For
\(b \in {\mathbb {F}_{2}^{m}}\), the component function corresponding to the linear combination defined by
b is denoted by
F
_{b}; that is,
\(F_{b} = {\sum }_{i = 1}^{m} b_{i} f_{i}\), where
\(b = (b_{1}, b_{2}, \dots , b_{m})\) and
f
_{i} are the coordinate functions of
F. As we shall see in Section
2.2, some cryptographic properties of an (
n,
m)function
F are expressed in terms of the Hamming distance between its components and certain other functions. We recall that the
Hamming distance
d
_{H}(
F,
G) between two (
n,
m)functions
F and
G is the number of inputs
\(x \in {\mathbb {F}_{2}^{n}}\) on which the values of
F and
G are distinct, i.e.
\(d_{H}(F,G) = \# \{ x \in {\mathbb {F}_{2}^{n}} : F(x) \ne G(x) \}\).
In the discussion of some of the invariants, we will use the notion of a multiset. Intuitively, a multiset is an unordered collection of elements in which the same element can occur multiple times. We will refer to the number of times that an element
e occurs in a multiset
M as the
multiplicity of
e in
M, and will refer to the collection of the multiplicities of all elements in
M as the
multiplicities of
M. Multisets will be denoted by square brackets, e.g. [
a,
b,
c], in contrast to ordinary sets, which are denoted by curly braces, e.g. {
a,
b,
c}.
2.1 Representation of vectorial Boolean functions
A vectorial Boolean function
F from
\({\mathbb {F}_{2}^{n}}\) to
\({\mathbb {F}_{2}^{m}}\) can be represented in several different ways. Perhaps the simplest is the socalled truthtable representation, which is simply an exhaustive list of the values
F(
x) for all possible inputs
\(x \in {\mathbb {F}_{2}^{n}}\). The truth table for a (3,3)function is given as an example in Table
1. The truthtable representation is rather efficient for implementing vectorial Boolean functions on a computer; in fact, the straightforward implementations of most invariants work best if the input (
n,
n)function is given as a truthtable. Nonetheless, it has a number of serious shortcomings that make other representations preferable: the size of the table grows exponentially with
n and
m; it is difficult to observe any properties of the function from its truth table without performing nontrivial computations; and it is difficult to express infinite families and constructions via truth tables.
Table 1
Truth table of a (3,3)function
x

F(
x)


000

000

001

101

010

110

011

111

100

100

101

011

110

001

111

010

Any (
n,
m)function can be uniquely represented as a multivariate polynomial of the form
where
\(a_{I} \in {\mathbb {F}_{2}^{m}}\) for all
\(I \subseteq \{1, 2, \dots , n \}\) and the variables
\(x_{1}, x_{2}, \dots , x_{n}\) take values in
\(\mathbb {F}_{2}\). This representation is known as the
algebraic normal form (ANF) of
F. In some cases, the ANF allows for a significantly more compact representation of an (
n,
n)function (when the dimensions
n and
m are large, so that the size of the truth table becomes prohibitive; while the number of terms with a nonzero coefficient in the ANF is small). The degree of the ANF (as a multivariate polynomial) is called the
algebraic degree of
F; due to the uniqueness of the ANF, this notion is well defined. The algebraic degree has cryptographic significance (it must be large in order to resist higherorder differential attacks) and, as we shall see later, it is invariant under EAequivalence (but not under CCZequivalence).
$$ F(x_{1}, x_{2}, \dots, x_{n}) = \underset{I \subseteq \{ 1, 2, \dots, n \} }{\sum} a_{I} \underset{i \in I}{\prod} x_{j}, $$
A function of algebraic degree at most 1, resp. 2, resp. 3 is called
affine, resp.
quadratic, resp.
cubic. Any affine (
n,
n)function
A satisfies
for any
\(x,y,z \in {\mathbb {F}_{2}^{n}}\), and thus this notion coincides with the usual definition of affinity. If an affine function
L satisfies
L(0) = 0 so that
for any
\(x,y \in {\mathbb {F}_{2}^{n}}\), it is called
linear. Affine and linear functions as defined here behave in the same way as they do over any vector space, and so all familiar notions and principles from linear algebra can be carried over to the case of vectorial Boolean functions.
$$ A(x) + A(y) + A(z) = A(x+y+z) $$
$$ L(x) + L(y) = L(x+y) $$
For example, the function given by its truthtable in Table
1 has the ANF
We can immediately see that its algebraic degree is 2; in other words, this is a quadratic function. In this particular case, the size of the ANF is not significantly smaller than that of the truthtable; but as the dimension
n increases, the disparity between the size of the two representations becomes more pronounced.
$$ \begin{array}{@{}rcl@{}} F(x_{1}, x_{2}, x_{3}) &=& (0,1,1) x_{1} x_{2} + (0,1,0) x_{1} x_{3} + (1,0,0) x_{2} x_{3} + \\ &&(1,0,0) x_{1} + (1,1,0) x_{2} + (1,0,1) x_{3}. \end{array} $$
(1)
Let
\(\mathbb {F}_{2^{n}}\) denote the finite field with 2
^{n} elements for some natural number
n. Recall that
\(\mathbb {F}_{2^{n}}\) can be represented as an
ndimensional vector space over the prime field
\(\mathbb {F}_{2}\). Thus,
\({\mathbb {F}_{2}^{n}}\) can be identified with
\(\mathbb {F}_{2^{n}}\), and (
n,
n)functions can be seen as mapping from
\(\mathbb {F}_{2^{n}}\) to itself. This allows any (
n,
n)function to be represented as a univariate polynomial of the form
where
\(a_{i} \in \mathbb {F}_{2^{n}}\) for 0 ≤ 1 ≤ 2
^{n} − 1. This is known as the
univariate representation of
F; just like the ANF, it always exists and is uniquely defined. The algebraic degree can be obtained directly from the univariate representation as the maximum binary weight of an exponent
i with a nonzero coefficient
a
_{i}. The
binary weight (also called 2weight) of a natural number
i, denoted by
w
_{2}(
i), is the number of distinct powers of 2 in its binary decomposition; that is, if we write
i as
\(i = {\sum }_{j} a_{j} 2^{j}\) for
a
_{j} ∈{0,1}, then
\(w_{2}(i) = {\sum }_{j} a_{j}\). Equivalently,
w
_{2}(
i) is the number of nonzero bits in the binary representation of
i (for instance,
w
_{2}(11) = 3 since 11 can be written as 2
^{3} + 2
^{1} + 2
^{0}, or as 1011 in binary). The algebraic degree of
F is then
We also remark that the component functions of
F can be expressed using the absolute trace function
\(\text {Tr} : \mathbb {F}_{2^{n}} \rightarrow \mathbb {F}_{2}\) as the Boolean functions
F
_{b} :
x↦Tr(
b
F(
x)) for all nonzero
\(b \in \mathbb {F}_{2^{n}}\). We recall that the absolute trace is defined by
$$ F(x) = \sum\limits_{i = 0}^{2^{n}1} a_{i} x^{i}, $$
$$ \deg(F) = \max \{ w_{2}(i) : 0 \le i \le 2^{n}1, a_{i} \ne 0 \}. $$
$$ \text{Tr}(x) = x + x^{2} + x^{2^{2}} + {\dots} + x^{2^{n1}}. $$
The univariate representation is by far the most widely used at the moment. A decisive reason for this is that many of the known APN functions (including infinite constructions and families) have a very simple form under this representation; a classic example is the Gold function
x
^{3}, which is known to be APN over
\(\mathbb {F}_{2^{n}}\) for any natural number
n [
38,
46]. Indeed, the (3,3)function represented by Table
1 and the ANF in (
1) is precisely
x
^{3} over
\(\mathbb {F}_{2^{3}}\). At the time of writing, most known infinite constructions of APN functions are expressed in the univariate representation; there are also a few constructions based on the socalled bivariate representation (that we do not treat here, but briefly discuss below). A list of the known infinite families of APN monomials is given in Table
2, and a list of the known infinite polynomial APN families is given in Table
3.
Table 2
Known infinite families of APN power functions over
\(\mathbb {F}_{2^{n}}\)
Family

Exponent

Conditions

Algebraic degree

Source


Gold

2
^{i} + 1

\(\gcd (i,n) = 1\)

2


Kasami

2
^{2i} − 2
^{i} + 1

\(\gcd (i,n) = 1\)

i + 1


Welch

2
^{t} + 3

n = 2
t + 1

3

[
33]

Niho

2
^{t} + 2
^{t/2} − 1,
t even

n = 2
t + 1

(
t + 2)/2

[
32]

2
^{t} + 2
^{(3t+ 1)/2} − 1,
t odd

t + 1


Inverse

2
^{2t} − 1

n = 2
t + 1

n − 1


Dobbertin

2
^{4i} + 2
^{3i} + 2
^{2i} + 2
^{i} − 1

n = 5
i

i + 3

[
34]

Table 3
Known infinite families of quadratic APN polynomials over
\(\mathbb {F}_{2^{n}}\)
ID

Functions

Conditions

Source


F1F2

\(x^{2^{s}+1}+u^{2^{k}1}x^{2^{ik}+2^{mk+s}}\)

\(n = pk, \gcd (k,3) = \gcd (s,3k) = 1, p \in \{3,4\}, i = sk\text { mod } p, m = p i, n \ge 12, u \text { primitive in } \mathbb {F}_{2^{n}}^{*}\)

[
17]

F3

\(sx^{q+1}+x^{2^{i}+1}+x^{q(2^{i}+1)}+cx^{2^{i}q+1}+c^{q}x^{2^{i}+q}\)

q = 2
^{m},
n = 2
m,
g
c
d(
i,
m) = 1,
\(c\in \mathbb {F}_{2^{n}}, s \in \mathbb F_{2^{n}} \setminus \mathbb {F}_{q}, X^{2^{i}+1}+cX^{2^{i}}+c^{q}X+1 \text { has no solution } x\) s.t.
x
^{q+ 1} = 1

[
15]

F4

\(x^{3}+a^{1} \text {Tr}_{n} (a^{3}x^{9})\)

a≠ 0

[
18]

F5

\(x^{3}+a^{1} \text {Tr}_{n}^{3} (a^{3}x^{9}+a^{6}x^{18})\)

3
n,
a≠ 0

[
19]

F6

\(x^{3}+a^{1} \text {Tr}_{n}^{3}(a^{6}x^{18}+a^{12}x^{36})\)

3
n,
a≠ 0

[
19]

F7F9

\(ux^{2^{s}+1}+u^{2^{k}} x^{2^{k}+2^{k+s}}+vx^{2^{k}+1}+wu^{2^{k}+1}x^{2^{s}+2^{k+s}}\)

\(n=3k, \gcd (k,3)=\gcd (s,3k)=1, v, w\in \mathbb {F}_{2^{k}}, vw \ne 1, 3(k+s), u \text { primitive in } \mathbb {F}_{2^{n}}^{*}\)

[
9]

F10

\((x+x^{2{^{m}}})^{2^{k}+1}+u^{\prime }(ux+u^{2^{m}} x^{2^{m}})^{(2^{k}+1)2^{i}}+u(x+x^{2^{m}})(ux+u^{2^{m}} x^{2^{m}})\)

\(n=2m, m\geqslant 2\) even,
\(\gcd (k, m)=1\) and
\( i \geqslant 2\) even,
\(u\text { primitive in } \mathbb {F}_{2^{n}}^{*}, u^{\prime } \in \mathbb {F}_{2^{m}} \text { not a cube }\)

[
57]

F11

\(a^{2}x^{2^{2m+1}+1}+b^{2}x^{2^{m+1}+1}+ax^{2^{2m}+2}+bx^{2^{m}+2}+(c^{2}+c)x^{3}\)

\(n=3m, m \ \text {odd}, L(x)=ax^{2^{2m}}+bx^{2^{m}}+cx\) satisfies the conditions of Lemma 8 of [
14]

[
14]

F12

\(u(u^{q} x + x^{q} u)(x^{q} + x) + (u^{q} x + x^{q} u)^{2^{2i} + 2^{3i}} + a(u^{q} x + x^{q} u)^{2^{2i}} (x^{q} + x)^{2^{i}} + b(x^{q} + x)^{2^{i}+1}\)

\(q = 2^{m}, n = 2m, \gcd (i,m) = 1\),
\(x^{2^{i}+1} + ax + b\) has no roots in
\(\mathbb {F}_{2^{m}}\)

[
52]

F13

\(x^{3} + a (x^{2^{i} + 1})^{2^{k}} + b x^{3 \cdot 2^{m}} + c (x^{2^{i+m} + 2^{m}})^{2^{k}}\)

n = 2
m = 10, (
a,
b,
c) = (
β, 1, 0, 0),
i = 3,
k = 2,
β primitive in
\(\mathbb {F}_{2^{2}}\)

[
21]

n = 2
m,
m odd,
\(3 \nmid m\), (
a,
b,
c) = (
β,
β
^{2}, 1),
β primitive in
\(\mathbb {F}_{2^{2}}\),
i ∈{
m − 2,
m, 2
m − 1, (
m − 2)
^{− 1} mod
n}

The above is by no means an exhaustive list of known representations of vectorial Boolean functions. Nonetheless, it should provide sufficient context for the sequel, and we shall not go into any further details on the topic of representation of (
n,
n)functions. We will, however, mention the bivariate representation, in which a (2
n,2
n)function can be represented as pair of polynomials (
F
_{1}(
x,
y),
F
_{2}(
x,
y)) in two variables (see e.g. [
25], p.47); the representation of a quadratic function by means of a socalled quadratic APN matrix (QAM) [
56]; and the representation of a function by means of the values of its firstorder derivatives [
50].
2.2 APN and AB functions
Let
F be an (
n,
m)function for some natural number
n, and denote by
δ
_{F}(
a,
b) the number of solutions
\(x \in \mathbb {F}_{2^{n}}\) to the equation
for some
\(a,b \in \mathbb {F}_{2^{n}}\). Note that the equation expresses the difference between two outputs of
F whose corresponding inputs are at distance
a. If for some given
a, some value of
b is significantly more likely to occur than all others, an attacker can exploit this to derive a correlation between the input and output of the function. This is the basic idea of differential cryptanalysis, which is one of the most powerful known attacks against block ciphers [
5]. In order to be resistant to such attacks, the number of solutions to (
2) should be as uniform as possible over all possible choices of
\(b \in \mathbb {F}_{2^{n}}\) for any fixed nonzero
\(a \in \mathbb {F}_{2^{n}}\). The
differential uniformity of
F, denoted by Δ
_{F}, is the largest value of
δ
_{F}(
a,
b) over all choices of
\(0 \ne a \in \mathbb {F}_{2^{n}}\) and
\(b \in \mathbb {F}_{2^{n}}\). Symbolically:
The differential uniformity should be as low as possible in order to resist differential cryptanalysis, and since
x +
a is a solution to (
2) whenever
x is, the differential uniformity of any (
n,
n)function can be no lower than two. A function is called
almost perfect nonlinear (APN) if it achieves this trivial lower bound with equality.
$$ F(x+a) + F(x) = b $$
(2)
$$ {\Delta}_{F} = \max \{ \delta_{F}(a,b) : a,b \in \mathbb{F}_{2^{n}}, a \ne 0 \}. $$
The
differential spectrum
\(\mathcal {D}_{F}\) of
F is the multiset of the values of
δ
_{F}(
a,
b) over all
\(a, b \in \mathbb {F}_{2^{n}}\) with
a≠ 0; that is,
Clearly, a function is APN if and only if its differential spectrum consists of the two values 0 and 2. The differential spectrum is, in fact, invariant under CCZequivalence, but it is practically useless for the purpose of distinguishing inequivalent APN functions. It does, however, take a much more prominent role as an invariant of the orthoderivatives of quadratic APN functions, as described in Section
4.6.
$$ \mathcal{D}_{F} = [ \delta_{F}(a,b) : a,b \in \mathbb{F}_{2^{n}}, a \ne 0 ]. $$
We remark that the function
D
_{a}
F(
x) =
F(
x +
a) +
F(
x) is called the (discrete firstorder)
derivative of
F in direction
\(a \in \mathbb {F}_{2^{n}}\). An APN function can be equivalently defined as a function all of whose derivatives
D
_{a}
F for
a≠ 0 are 2to1 functions.
Another powerful attack against block ciphers is linear cryptanalysis [
45], which attempts to approximate the behavior of a function by means of linear functions. Intuitively, a function
F should be as far away from all linear functions as possible in order to be resistant to this attack. The nonlinearity of a Boolean function
\(f : \mathbb {F}_{2^{n}} \rightarrow \mathbb {F}_{2}\) is defined as the minimum Hamming distance between
f and any affine (
n,1)function. This notion can then be naturally generalized to the case of vectorial Boolean functions through the nonlinearity of their component functions. The
nonlinearity of an (
n,
n)function
F, denoted by
\(\mathcal {N}{\mathscr{L}}(F)\), is defined as the minimum Hamming distance between any component function of
F, and any affine (
n,1)function. The nonlinearity should be as high as possible in order to resist linear cryptanalysis, and it has been shown [
27,
51] that it satisfies
for any (
n,
n)function
F. The functions that attain this upper bound with equality are called
almost bent (AB) functions. Note that AB functions exist only for odd values of
n. In the case of even
n, functions with nonlinearity 2
^{n− 1} − 2
^{n/2} are known, and they are conjectured to be optimal with respect to nonlinearity; nonetheless, the exact upper bound on the nonlinearity for (2
n,2
n)functions remains an open question.
$$ \mathcal{N}\mathcal{L}(F) \le 2^{n1}  2^{(n1)/2} $$
It is also known that any AB function is necessarily APN. The converse does not hold in general, although it is known that any quadratic APN (
n,
n)function is AB when
n is odd [
26]. Thus, AB functions provide optimal resistance against both linear and differential cryptanalysis. In particular, constructing new instances and families of APN functions is a natural approach to finding new constructions of AB functions.
Besides providing the best possible resistance to differential and linear cryptanalysis, respectively, APN and AB functions correspond to optimal objects in other areas of mathematics and computer science, including coding theory, combinatorics, projective geometry, and sequence design. Developments in the study of cryptographic vectorial Boolean functions therefore naturally lead to progress in other areas; and results and methods used in these related fields of study can be applied to the investigation of APN and AB functions. In essence, the natural definitions of APN and AB functions make them significant, universal objects that transcend the immediate practical needs of cryptography and have a much broader relevance.
In addition to the differential uniformity and nonlinearity, the algebraic degree of an (
n,
n)function is also one of its important cryptographic properties; it should be high in order to provide good resistance against higherorder differential attacks. In addition, there are quite a few other statistics and properties for measuring the cryptographic strength of a function against various kinds of attacks. Since in this paper we mostly focus on invariants with respect to the classification of APN and AB functions, we do not go into further details here. We refer the reader to [
25] for a more comprehensive treatment of the subject.
2.3 Equivalence relations
Equivalence relations on (
n,
n)functions that preserve the differential uniformity and nonlinearity are used to reduce the number of functions that need to be studied and classified. Currently, CCZequivalence is the most general known equivalence relation preserving these properties, and so classification and computational results on APN and AB function are typically given up to CCZequivalence.
The notion of the CCZequivalence of two functions is expressed in terms of their graphs. Let
F and
G be (
n,
n)functions for some natural number
n. The graph of
F is the set
\({\Gamma }_{F} = \{ (x,F(x)) : x \in \mathbb {F}_{2^{n}} \}\). Note that for any (
n,
n)function
F, its graph Γ
_{F} is contained in the set
\(\mathbb {F}_{2^{n}}^{2}\) of pairs of elements from
\(\mathbb {F}_{2^{n}}\). The latter can be identified with
\(\mathbb {F}_{2^{2n}}\), and thus we can assume that Γ
_{F} is contained in
\(\mathbb {F}_{2^{2n}}\). Then
F and
G are said to be
CarletCharpinZinoviev equivalent, or
CCZequivalent for short, if there exists an affine permutation
A of
\(\mathbb {F}_{2^{2n}}\) mapping Γ
_{F} to Γ
_{G}, i.e.
$$ \{ A(x) : x \in {\Gamma}_{F} \} = {\Gamma}_{G}. $$
In Section
3, we will concentrate on properties that are left invariant by CCZequivalence. For the time being, we remark that CCZequivalence preserves neither the algebraic degree, nor the bijectivity of the function. This is noteworthy, as both of these can (and have) been used constructively. In 2010, John Dillon constructed the only currently known instance of an APN (
n,
n)permutation for even
n by traversing the CCZequivalence class of a known (nonbijective) APN function over the same field [
12]. In a similar vein, most of the known instances of APN functions listed in the literature are quadratic. As pointed out in Section
2.2, it is desirable for the algebraic degree to be high in order to resist higherorder differential attacks. Traversing the CCZclass of a quadratic APN function may yield functions of higher algebraic degree that are CCZequivalent to it (and hence also APN).
A special case of CCZequivalence is the socalled extended affine equivalence, or EAequivalence for short. Two (
n,
n)functions
F and
G are said to be
EAequivalent if there exist affine (
n,
n)functions
A
_{1},
A
_{2},
A with
A
_{1} and
A
_{2} bijective such that
CCZequivalence is strictly more general than EAequivalence combined with taking inverses of permutations [
20]. Nonetheless, the two equivalence relations coincide in the case when both
F and
G are quadratic; that is, if
F and
G are quadratic APN (
n,
n)functions, then
F and
G are CCZequivalent if and only if they are EAequivalent [
53]. In practice, this makes EAequivalence (and hence, properties that are invariant under EAequivalence) almost as useful as CCZequivalence in the case of APN functions, since all known APN instances are equivalent to quadratic functions or monomials, with only a single known exception for
n = 6 [
36].
$$ A_{1} \circ F \circ A_{2} + A = G. $$
(3)
Further specializations of EAequivalence can be obtained by imposing additional restrictions on
A
_{1},
A
_{2} and
A. If
A = 0 in (
3), we say that
F and
G are
affine equivalent. If
A = 0 and
A
_{1}(0) =
A
_{2}(0) = 0 (so that
A
_{1} and
A
_{2} are linear instead of merely affine), we say that
F and
G are
linear equivalent. Further restrictions have been investigated, such as the socalled restricted EAequivalence [
22,
48]. These relations are of limited interest in the APN case, and so we mostly concentrate on the notions of EA and CCZequivalence.
For the sake of completeness, we also mention a special kind of equivalence that can be defined for two power functions. If
\(F(x) = x^{e_{1}}\) and
\(G(x) = x^{e_{2}}\) are (
n,
n)functions for some natural numbers
e
_{1} and
e
_{2}, then we say that
F and
G are
cyclotomic equivalent if there exists a natural number
k such that 2
^{k}
e
_{1} =
e
_{2}(mod 2
^{n} − 1) or
\(2^{k} e_{1}^{1} = e_{2} (\text { mod }{2^{n}1})\), where
\(e_{1}^{1}\) is the multiplicative inverse of
e
_{1} modulo 2
^{n} − 1 (if it exists). We note that this is a special case of affine equivalence and taking inverses of permutations, since the function
\(x^{e_{2}}\) with 2
^{k}
e
_{1} =
e
_{2}(mod 2
^{n} − 1) can be obtained from
\(x^{e_{1}}\) by composing the latter with the linear permutation
\(x \mapsto x^{2^{k}}\). It is known that if two power functions are CCZequivalent, they are necessarily cyclotomic equivalent [
31,
54]. This greatly reduces the complexity of deciding equivalence in the case of power functions since, unlike EA and CCZequivalence, testing cyclotomic equivalence is simple and amounts to solving modular equations.
2.4 Testing equivalence via linear codes
The simplicity of the definitions of the equivalence relations in Section
2.3 belies the complexity of testing them in practice. Indeed, doing so by exhaustive search (for instance, over all affine permutations of
\(\mathbb {F}_{2^{n}}^{2}\) in the case of CCZequivalence) is only feasible for very small dimensions. On the other hand, no efficient algorithm for deciding CCZ or EAequivalence from first principles in the general case is known; the algorithm for testing EAequivalence from [
42] is only effective for even dimensions; the one from [
23] concerns only quadratic functions; and the methods described in [
6,
22,
48] apply to certain special cases of EAequivalence. We note that cyclotomic equivalence is a notable exception since deciding it involves verifying the solvability of a small number of modular equations; this can be done efficiently even for very high dimensions.
Testing CCZequivalence is typically done by means of linear codes as described in [
11,
37]. Given any (
n,
n)function
F, we can associate with it a linear code
\(\mathcal {C}_{F}\) with the paritycheck matrix
where
α is a primitive element of
\(\mathbb {F}_{2^{n}}\). Then two (
n,
n)functions
F and
G are CCZequivalent if and only if their associated codes
\(\mathcal {C}_{F}\) and
\(\mathcal {C}_{G}\) are isomorphic, i.e. if there is a permutation
π of
\(\{1,2,\dots ,2^{n}\}\) such that
\((x_{1}, x_{2}, \dots , x_{n})\) is a codeword of
\(\mathcal {C}_{F}\) if and only if
\((x_{\pi (1)}, x_{\pi (2)}, \dots , x_{\pi (2^{n})})\) is a codeword of
\(\mathcal {C}_{G}\).
$$ M_{F} = \left( \begin{array}{cccccc} 1 & 1 & 1 & 1 & {\cdots} & 1 \\ 0 & 1 & \alpha & \alpha^{2} & {\cdots} & \alpha^{2^{n}2} \\ F(0) & F(1) & F(\alpha) & F(\alpha^{2}) & {\cdots} & F(\alpha^{2^{n2}}) \end{array} \right), $$
(4)
The problem of deciding the isomorphism of two linear codes is itself quite difficult. The advantage of the above reduction is that coding theory is a very well developed area, and algorithms for testing the isomorphism of linear codes are known and well studied. Mathematical libraries and programming languages (such as
Magma [
8]) typically have a working implementation of such algorithms, and implementing a CCZequivalence test then amounts to simply constructing the paritycheck matrices in (
4) and passing them to the relevant codingtheoretic framework.
Testing EAequivalence can be done in the same way, except that a different associated code is used [
37]. In this case, the paritycheck matrix has a different form; once again, two functions are EAequivalent if and only if their associated codes are isomorphic. In practice, the associated codes in the case of EAequivalence have a larger length than those for CCZequivalence, and so testing EAequivalence in this way is computationally more difficult. In practice, one typically uses the test for CCZequivalence in the case of quadratic APN functions since then two functions are CCZequivalent if and only if they are EAequivalent. In the same paper, it is shown that affine equivalence can be tested in the same way as well; however, the length of the associated code is even larger than in the case of EAequivalence, and since vectorial Boolean functions are typically classified up to CCZ or EAequivalence, this last result is of limited practical utility.
Thus, deciding the CCZequivalence of two (
n,
n)functions is currently only possible via the isomorphism of linear codes. Unfortunately, this has certain shortcomings. For one, the computation time and memory requirements increase exponentially with the dimension
n. In practice, we are only able to test functions up to
n = 10 on our server; for higher dimensions, the memory consumption becomes prohibitive. Another problem is that the current implementation of the isomorphism test in
Magma can give false negatives if it runs out of memory during the computation. This behavior occurs only if the dimension is high; but it is possible for this to occur for dimensions as low as
n = 9 in some cases.
Table
4 give some sample running times (in seconds) for verifying that two arbitrarily selected APN functions from among the known CCZinequivalent representatives over
\(\mathbb {F}_{2^{n}}\) are indeed CCZinequivalent for 6 ≤
n ≤ 10. These sample times are measured by selecting some pairs of functions at random from among the known APN functions, and running the linear code isomorphism on them; the times given in the table are averaged over the tested pairs. The computation time in the case of CCZequivalent functions is typically less, since the algorithm terminates as soon as an equivalence is found; while in the case of inequivalent functions, all possibilities have to be exhausted before a negative answer can be given. The computation time also depends on the concrete pair of functions being tested; if one of the functions is a monomial, the computation is generally faster. For some pairs of functions, the running time can be significantly longer or shorter; the data given in Table
4 (as well as all other tables in this paper that contain computation times) are only meant to provide a general idea of how long the computation lasts in higher dimensions when compared to lower ones (of course, the actual computation depends on a lot of other factors, such as the computational equipment used, the concrete implementation, the number of processes running in parallel, etc.). We stress that the running times given in the following tables are only meant to give a general idea of the efficiency of different methods, and make no claims about the experiments being statistically accurate.
Table 4
Sample times (in seconds) for verifying CCZinequivalence over
\(\mathbb {F}_{2^{n}}\) via the linear code equivalence test
n

6

7

8

9

10


time (s)

0.020

7.170

0.180

8311.830

40.880

One remarkable observation that we can make from the table is that testing CCZequivalence for odd dimensions takes significantly longer than doing so for even dimensions; for instance, we can see that although 8 is greater than 7, the running time for comparing functions over
\(\mathbb {F}_{2^{7}}\) is typically several times longer than the time for doing the same over
\(\mathbb {F}_{2^{8}}\). A possible intuitive explanation for this surprising behavior could be that the known APN functions over fields of odd extension degree are much more “similar” to each other (and thus, harder to distinguish) than those over fields of even extension degree. Indeed, the vast majority of APN functions that we know over any finite field (regardless of the parity of its extension degree) are quadratic; and we know that any quadratic APN function over
\(\mathbb {F}_{2^{n}}\) for odd
n is AB. Furthermore, AB functions behave more “predictably” than APN functions in some sense (for instance, they have a fixed value of the nonlinearity, and do not have any bent components; the number of bent components is actually one of the invariants under EAequivalence discussed in Section
4.3, and can take many distinct values across the known quadratic APN functions over
\(\mathbb {F}_{2^{n}}\) for even values of
n). As we will observe in Sections
3 and
4, some invariants behave similarly, in the sense that they can taken many distinct values for APN functions over finite fields of even extension degree (and can thus be useful for distinguishing between EA or CCZinequivalent ones); while the same invariants almost always take the same value for the known APN functions over
\(\mathbb {F}_{2^{n}}\) with
n odd, and so are practically useless in this respect.
The above considerations further underline the practical importance of invariants. Computational searches can easily produce thousands of functions and, especially in the case of higher dimensions where testing equivalence can take a long time, partitioning the functions according to the values of an efficiently computable invariant can save a lot of computation time. In the case that two inequivalent functions have different values for a certain invariant (or a combination of invariants), this precludes any possibility of a false negative.
2.5 A note on the computational results
In the following Sections
3 and
4, we survey the most frequently used invariants for classifying APN and AB functions up to CCZ and EAequivalence, and report on some computational results for measuring how quickly these invariants can be computed, and how well they can distinguish between distinct CCZ and EAequivalence classes. In this section, we describe the computational equipment that we used and the sets of functions that we tested the invariants on.
Computations in C and Python were performed on an HP EliteDesk 800 G2 SFF computer, with a quad core 3.2 GHz processor with 15 GB of memory. Computations in
Magma were performed on a server with 56 3.2 GHz cores and 500 GB of memory.
All the experiments that we conduct are for dimensions
n ≥ 6 since the classification of APN functions for
n < 6 is already complete [
10]. In the case of
n = 6, we use the 14 CCZinequivalent representatives from the switching classes [
36]; 13 of them are quadratic and represent all CCZclasses of quadratic functions over
\(\mathbb {F}_{2^{6}}\) [
35], while the remaining function is the only known example of an APN instance CCZinequivalent to monomial and quadratic functions. For
n = 7, we use the list of 390 functions from [
55,
56] along with the newly found quadratic APN function from [
43]; as shown in [
43], the quadratic representatives therein encompass all possible CCZclasses of quadratic APN functions over
\(\mathbb {F}_{2^{7}}\). For
n = 8, we use the 8181 functions from [
55]; we note that recently more than 12 000 new inequivalent APN instances have been discovered in
\(\mathbb {F}_{2^{8}}\) [
2], but we do not involve these in the computations since the goal is to give an empiric idea of how efficient the various invariants are in distinguishing distinct CCZclasses (rather than to do a complete classification); a constantly updated list of invariants for the known functions is available at [
1]. For
n = 9 and
n = 10, we take CCZinequivalent representatives from the known infinite APN families along with the new functions found in [
2]; this is necessary, since some invariants tend to take a lot of different values among the known APN instances, but only one or two values for instances belonging to the currently known APN families. Since no classification of APN functions is available for dimensions
n ≥ 11, we restrict ourselves to only computing invariants for a few select functions in order to estimate the computation time, without making any claims about the distinguishing power of the invariants in those dimensions.
3 Invariants under CCZequivalence
3.1 Trivial invariants
The differential uniformity (and, more generally, the differential spectrum) and nonlinearity are invariant under CCZequivalence, but this does not help with the classification of APN and AB functions, since by definition they have a fixed value of the differential uniformity and nonlinearity, respectively.
3.2 The extended Walsh spectrum
3.2.1 Definition
The Walsh transform
\(W_{F} : \mathbb {F}_{2^{n}}^{2} \rightarrow \mathbb {Z}\) is an integervalued function that can be associated with any (
n,
n)function
F. More precisely, the
Walsh transform of
F is defined as
where “⋅” denotes a scalar product, or dot product on
\(\mathbb {F}_{2^{n}}\) (or, equivalently, on
\({\mathbb {F}_{2}^{n}}\)). The properties of the Walsh transform do not depend on the concrete choice of the scalar product. There are at least two frequently used choices:
The former realization tends to be more suitable for implementing the Walsh transform in a generalpurpose programming language, while the latter is typically used in theoretical proofs and constructions.
$$ W_{F}(a,b) = \underset{x \in \mathbb{F}_{2^{n}}}{\sum} (1)^{b \cdot F(x) + a \cdot x}, $$
(5)

if the multiplicands \(a = (a_{1}, a_{2}, \dots , a_{n})\) and \(b = (b_{1}, b_{2}, \dots , b_{n})\) are viewed as ndimensional binary vectors in \({\mathbb {F}_{2}^{n}}\), the product can be defined as \(a \cdot b = a_{1} b_{1} + a_{2} b_{2} + {\dots } + a_{n} b_{n}\), with addition and multiplication being over \(\mathbb {F}_{2}\);

the product can also be defined as a ⋅ b = Tr( a b), where \(\text {Tr} : \mathbb {F}_{2^{n}} \rightarrow \mathbb {F}_{2}\) is the absolute trace function from \(\mathbb {F}_{2^{n}}\) to the prime field \(\mathbb {F}_{2}\); in this case, the operands a and b are multiplied in the finite field, and then this product is mapped onto \(\mathbb {F}_{2}\) via the trace.
The values
W
_{F}(
a,
b) of the Walsh transform are referred to as
Walsh coefficients. The
Walsh spectrum of an (
n,
n)function
F is the multiset of the values of its Walsh coefficients for all possible
\(a,b \in \mathbb {F}_{2^{n}}\). The
extended Walsh spectrum
\(\mathcal {W}_{F}\) of
F is the multiset of the absolute values of all of the Walsh coefficients of
F, that is
The extended Walsh spectrum is invariant under CCZequivalence.
$$ \mathcal{W}_{F} = [ W_{F}(a,b) : a,b \in \mathbb{F}_{2^{n}} ]. $$
As we will see in the evaluation below, the extended Walsh spectrum is not a very useful invariant in terms of its distinguishing power. Nonetheless, it is a good idea to compute it as a first step in analyzing a function, since the computation of several of the following invariants either require, or are facilitated by, knowledge of all values of the Walsh transform. Furthermore, it does become useful in distinguishing inequivalent quadratic APN functions when applied to their orthoderivatives rather than to the functions themselves; orthoderivatives are described in Section
4.6.
3.2.2 Evaluation
The Walsh transform can be implemented easily on any programming language; its computation from (
5) requires nothing more complicated than basic arithmetic operations (addition, modulation, and XOR, and possibly finite field multiplication depending on how the scalar product is implemented). On algebra systems such as
Magma [
8] that include builtin functionality for computations over finite fields, both implementations can be easily realized. Furthermore, there are more sophisticated methods such as the socalled butterfly transform allowing the set of all Walsh coefficients of a given function to be computed even more efficiently (see Algorithm 9.3 on p. 276 in [
41]).
Depending on the implementation, the Walsh transform can be computed very efficiently. A straightforward implementation in C taking the truth table of an (
n,
n)function as input needs around 20 seconds to compute the entire Walsh spectrum for
n = 10; further measurements are provided in Table
5 below. The memory consumption is negligible.
Unfortunately, the extended Walsh spectrum does not do a good job of distinguishing between inequivalent functions. Among all known APN instances
F over
\(\mathbb {F}_{2^{n}}\) for odd values of
n, there are only two possible values of
W
_{F}: all known APN functions except for the inverse power function
\(x^{2^{n}2}\) and the Dobbertin power function
\(x^{2^{4i} + 2^{3i} + 2^{2i} + 2^{i}  1}\) for
n = 5
i have the socalled Goldlike spectrum (that is, the same as the Gold function
x
^{3}); while the inverse power function and the Dobbertin power function share the same extended Walsh spectrum which is distinct from that of any other known APN function. We note that the Dobbertin power function is only defined for dimensions
n that are divisible by 5 (so that the first two odd dimensions for which it is defined are
n = 5 and
n = 15), and so its characteristic Walsh spectrum is not reflected in Table
5, which only accounts for the values of the Walsh spectra in the range 6 ≤
n ≤ 10.
Table 5
Time for computing the extended Walsh spectrum in C
n

6

7

8

9

10

11

12


time (s)

0.023

0.076

0.391

2.863

22.566

171.602

1410.009

total

14

491

21 115

46

21

–

–

values

2

2

6

2

2

–

–

For
n = 6 and
n = 10, we observe a similar partition. More precisely, all known APN functions over
\(\mathbb {F}_{2^{6}}\) have a Goldlike spectrum, except for one (function 2.5 from [
36]); and all functions over
\(\mathbb {F}_{2^{10}}\) have a Goldlike spectrum, except for the Dobbertin power function
x
^{339}. For
n = 8, the situation is a bit more varied. We know more than 20 000 CCZinequivalent APN functions over
\(\mathbb {F}_{2^{8}}\) [
2], and these have six distinct values of the extended Walsh spectrum. Still, the vast majority of the known APN functions have a Goldlike spectrum; and it is remarkable that the same is true for all known polynomial (as opposed to monomial) APN functions (regardless of the dimension
n) that have been classified into infinite families.
3.3 Invariants from associated designs
3.3.1 Definition
An
incidence structure is a triple
\((\mathcal {P}, {\mathscr{B}}, \mathcal {I})\), where
\(\mathcal {P} = \{ p_{1}, p_{2}, \dots , p_{m} \}\) is a set of points,
\({\mathscr{B}} = \{ b_{1}, b_{2}, \dots , b_{n} \}\) is a set of blocks, and
\(\mathcal {I} \subseteq \mathcal {P} \times {\mathscr{B}}\) is an incidence relation. Typically, we assume that the blocks in
\({\mathscr{B}}\) are subsets of
\(\mathcal {P}\), and the incidence relation
\(\mathcal {I}\) is set membership. The notion of an incidence structure is quite natural and general; the field of combinatorial design theory studies incidence structures called block designs. We can associate to any incidence structure a socalled
incidence matrix, which is a binary
m ×
n matrix
M representing the incidence relation
\(\mathcal {I}\). More precisely, for any
i,
j in the range 1 ≤
i ≤
m and 1 ≤
j ≤
n, the element
M
_{i,j} on the
ith row and
jth column of
M is equal to 1 if
\((p_{i}, b_{j}) \in \mathcal {I}\); and is equal to 0 otherwise. We refer the reader to [
4] or [
28] for more background on incidence structures and combinatorial designs.
Given any (
n,
n)function
F, two designs can be associated with it [
36]. In both cases, the set of points is simply
\(\mathbb {F}_{2^{n}}^{2}\), that is, the set of all pairs of elements from the finite field. The first design is denoted by
d
e
v(
G
_{F}), and its blocks are of the form
for
\(a,b \in \mathbb {F}_{2^{n}}\). The second design is denoted by
d
e
v(
D
_{F}), and its blocks are the sets
for
\(a,b \in \mathbb {F}_{2^{n}}\). The rank of the incidence matrix of
d
e
v(
G
_{F}) is called the Γ
rank of
F, and the rank of the incidence matrix of
d
e
v(
D
_{F}) is called the Δ
rank of
F. The Γ and Δrank are shown to be invariant under CCZequivalence, and are two of the currently most widely used invariants in practice.
$$ \{ (x+a, F(x) + b) : x \in \mathbb{F}_{2^{n}} \} $$
$$ \{ (x+y+a, F(x) + F(y) + b) : x,y \in \mathbb{F}_{2^{n}} \} $$
The orders of the automorphism groups of
d
e
v(
G
_{F}) and
d
e
v(
D
_{F}) are also CCZinvariant, but their computation is only feasible for small dimensions, and so they are not quite as useful as the Γ and Δrank. Nonetheless, these automorphism groups give rise to a CCZinvariant that can be quite useful in practice: the order of the socalled multiplier group. The
multiplier group is the subgroup of the automorphism group of
d
e
v(
G
_{F}) consisting of automorphisms of a special form; its order, denoted by
\({\mathscr{M}}(G_{F})\), is invariant under CCZequivalence, and can be computed much more efficiently than the order of the full automorphism group. We note that the formal definition of the multiplier group is somewhat technical, and does not contribute anything to the discussion; we omit it, and refer the reader to [
36] instead.
3.3.2 Evaluation
The definition of these invariants is conceptually simple, although it does require familiarity with the notion of a combinatorial design and its incidence matrix (and automorphism group, in the case of the
\({\mathscr{M}}(G_{F})\)). In the case of the Γ and Δrank, the incidence matrix corresponding to
d
e
v(
G
_{F}) and
d
e
v(
D
_{F}) can be constructed quite easily. The main issue is the computation of its rank, which requires a sophisticated implementation in order to be efficiently computable in practice. In both cases, we need to compute the rank of a binary 2
^{2n} × 2
^{2n} matrix (whose construction takes significant time and which occupies a lot of memory, especially for higher dimensions), and a straightforward implementation of say Gaussian elimination is not nearly fast enough. One is thus forced to rely on software libraries or algebra systems (such as
Magma) that implement efficient algorithms for computing the rank of a matrix; or, otherwise, to implement such highly nontrivial algorithms oneself.
Computing the Γ and Δrank is fairly efficient for small dimensions, but the time complexity grows exponentially; for
n = 10, computing a single Γrank can take more than a week. A summary of the average computation times (in seconds) is given in Table
6. The real bottleneck, however, is the memory consumption; the 500 GB of memory available on our server suffice only for computing Γranks up to dimension 10, and Δranks up to dimension 9.
Table 6
Computation times (in seconds) for the Γrank, the Δrank, and the order of
\({\mathscr{M}}(G_{F})\)
n

6

7

8

9

10


Γrank

2

15

138

4229

899024

Δrank

2

20

308

6976

–

\({\mathscr{M}}(G_{F})\)

0.010

0.120

0.100

11.330

8.710

Despite these shortcomings, the Γrank, Δrank, and the order
\({\mathscr{M}}(G_{F})\) of the multiplier group are rather useful invariants, as they can take on a lot of distinct values for the known functions. Table
7 gives a summary of the number of distinct values that the Γrank, Δrank, and
\({\mathscr{M}}(G_{F})\) can take individually, and the number of distinct combinations of values that they can take on together. Note that computing Δranks for
n ≥ 10 and computing any of the invariants from this section for
n ≥ 11 is currently impossible due to insufficient memory on our server.
Table 7
Number of distinct design invariants for some known APN functions
n

no. of functions

Γranks

Δranks

\({\mathscr{M}}(G_{F})\)

combinations


6

14

9

3

7

11

7

491

14

6

5

20

8

8192

24

11

10

49

9

46

31

15

8

41

10

16

15

–

7

15

The values of the design invariants for the 35 new functions over
\(\mathbb {F}_{2^{9}}\) and the 5 new functions over
\(\mathbb {F}_{2^{10}}\) from [
2] are given below in Tables
8 and
9. The functions are indexed in the order in which they appear in the dataset associated to [
2]. A complete listing is available online at [
1].
Table 8
Design invariants for the 35 new APN functions over
\(\mathbb {F}_{2^{9}}\) [
2]
ID

Γrank

Δrank

\({\mathscr{M}}(G_{F})\)

ID

Γrank

Δrank

\({\mathscr{M}}(G_{F})\)


1

48864

940

2560

19

48564

944

3584

2

48860

938

2560

20

48612

936

3584

3

48618

942

3584

21

48624

930

3584

4

48626

944

3584

22

48622

940

3584

5

48602

930

3584

23

48594

944

3584

6

48624

942

3584

24

48564

942

3584

7

48630

944

3584

25

48594

942

3584

8

48610

930

3584

26

48622

944

3584

9

48558

932

3584

27

48610

942

3584

10

48620

944

3584

28

48594

942

3584

11

48602

932

3584

29

48620

944

3584

12

48616

944

3584

30

48554

922

10752

13

48562

942

3584

31

48624

930

10752

14

48578

940

3584

32

48602

940

3584

15

48626

944

3584

33

48596

942

3584

16

48628

940

3584

34

48228

926

75264

17

48602

942

3584

35

48228

926

75264

18

48580

930

3584

Table 9
Design invariants for the 5 new APN functions over
\(\mathbb {F}_{2^{10}}\) [
2]
ID

Γrank

\({\mathscr{M}}(G_{F})\)


1

163400

31744

2

163398

31744

3

163308

158720

4

164026

31744

5

164026

31744

3.4 The distance invariant
3.4.1 Definition
A lower bound on the Hamming distance between an APN function
F and the closest APN function to it in terms of Hamming distance is shown in [
16]. The value of this lower bound is calculated from the minimum value contained in a multiset π
_{F} of natural numbers that can be associated with any (
n,
n)function
F. The multiset π
_{F} is shown to be invariant under CCZequivalence in the case of APN functions; that is, if
F and
G are CCZequivalent APN functions, then π
_{F} = π
_{G}. One can, however, easily find counterexamples to π
_{F} being invariant in the case when
F and
G are not APN.
The multiset π
_{F} is defined as follows. Let
F be an (
n,
n)function for some natural number
n. For any
\(b,c \in \mathbb {F}_{2^{n}}\), we define a set
That is,
π
_{F}(
b,
c) contains all directions
\(a \in \mathbb {F}_{2^{n}}\) for which the derivative
D
_{a}
F(
x) =
F(
x +
a) +
F(
x) maps to
F(
a +
c) +
b. The multiset π
_{F} then consists of the cardinalities of
π
_{F}(
b,
c) for all possible choices of
\(b,c \in \mathbb {F}_{2^{n}}\); symbolically:
As indicated above, if
F and
G are APN and CCZequivalent, then we must necessarily have π
_{F} = π
_{G}. The lower bound on the Hamming distance mentioned previously can be computed as
\(\lceil ({\min \limits } {\Pi }_{F}) / 3 \rceil + 1\), where
\({\min \limits } {\Pi }_{F}\) is the smallest value in π
_{F}. It is also shown in [
16] that the lower bound is not, in general, tight for
n ≥ 5. It is remarkable that while this lower bound is CCZinvariant, the exact value of the Hamming distance to the closest APN function is not.
$$ \pi_{F}(b,c) = \{ a \in \mathbb{F}_{2^{n}} : (\exists x \in \mathbb{F}_{2^{n}}) F(x) + F(a+x) + F(a+c) = b \}. $$
$$ {\Pi}_{F} = [ \# \pi_{F}(b,c) : b,c \in \mathbb{F}_{2^{n}} ]. $$
If
F is quadratic, it is shown that
for any
\(c, c^{\prime } \in \mathbb {F}_{2^{n}}\). It is thus sufficient to compute only the reduced multiset
which then completely determines the full multiset π
_{F}. Recall that the quadratic case is by far the most practically significant, as almost all known APN instances are quadratic, or at least CCZequivalent to quadratic ones. This reduction is then quite valuable, as it allows us to reduce the time for computing this invariant by a factor of 2
^{n}.
$$ [ \# \pi_{F}(b,c) : b \in \mathbb{F}_{2^{n}} ] = [ \# \pi_{F}(b,c^{\prime}) : b \in \mathbb{F}_{2^{n}} ] $$
$$ {{\Pi}_{F}^{0}} = [ \# \pi_{F}(b,0) : b \in \mathbb{F}_{2^{n}} ], $$
3.4.2 Evaluation
Computing π
_{F} (or
\({{\Pi }_{F}^{0}}\)) is simple as it only requires summing finite field elements (which can be implemented via the binary XOR operation on most programming languages) and counting how many times a certain value occurs.
The computation time is quite fast, especially in the case of quadratic functions when only the reduced multiset
\({{\Pi }_{F}^{0}}\) has to be computed. Table
10 shows some example computation times (in seconds) of a straightforward C implementation for functions over
\(\mathbb {F}_{2^{n}}\) for 5 ≤
n ≤ 11. The last two columns give the total number of functions on which the invariant was tested and the number of distinct values that π
_{F} takes over those functions, respectively.
Table 10
Computation times and number of distinct values of π
_{F} for some known APN instances
n

\({{\Pi }_{F}^{0}}\)

π
_{F}

all

values


5

0.002

0.064

3

2

6

0.003

0.192

14

5

7

0.004

0.512

491

2

8

0.004

1.024

8181

6669

9

0.005

2.56

11

2

10

0.031

31.744

21

4

11

0.066

135.168

13

2

As indicated by Table
10, this invariant is not very effective for distinguishing inequivalent functions for odd dimensions. Indeed, for all odd
n in the range 5 ≤
n ≤ 11, we observe only two values of π
_{F}; one is attained by the inverse power function, while all the remaining known APN functions take the second value. This is particularly remarkable for
n = 7, where we know a large number of CCZinequivalent APN instances. Furthermore, as shown in [
10,
43], the considered representatives for
n = 5 and
n = 7 cover all CCZclasses of quadratic APN functions over
\(\mathbb {F}_{2^{5}}\) and
\(\mathbb {F}_{2^{7}}\), respectively; we can thus conclude that all quadratic APN functions over
\(\mathbb {F}_{2^{5}}\) and
\(\mathbb {F}_{2^{7}}\) have a Goldlike value of π
_{F}.
In the case of even dimensions, on the other hand, π
_{F} proves to be quite useful for distinguishing between CCZequivalence classes. For
n = 8, we get 6669 distinct values for the tested 8181 functions from [
55]. What is particularly noteworthy, is that instances over even dimensions from the known infinite polynomial (as opposed to monomial) APN families always take the same value of π
_{F} as the Gold function
x
^{3}. All the other values of π
_{F} that we observe correspond to instances discovered by computational searches that have not been classified into infinite families yet. As in the case of the extended Walsh spectrum, the Dobbertin power function for
n = 5 has the same value of π
_{F} as the inverse power function. Thus, the inverse and Dobbertin power functions are currently the only known infinite families of APN functions to have a value of π
_{F} distinct from that of the Gold functions.
4 Invariants under EAequivalence
Despite EAequivalence being strictly less general than CCZequivalence, we know that two quadratic APN functions are CCZequivalent if and only if they are EAequivalent. Since almost all known APN functions are CCZequivalent to monomials or to quadratic functions, this makes tests and invariants for EAequivalence almost as useful in practice as ones for the more general CCZequivalence.
4.1 Trivial invariants
Since EAequivalence is a particular case of CCZequivalence, any two functions that are EAequivalent are also CCZequivalent. Consequently, all invariants described in Section
3 remain invariants under EAequivalence as well.
4.2 Algebraic degree and minimum degree
The algebraic degree of any (
n,
n)function is invariant under EAequivalence since the composition of an arbitrary function
F with an affine function does not change the algebraic degree of
F. Since the majority of known APN functions are quadratic, and since most computational searches tend to produce quadratic APN functions, the algebraic degree is of somewhat limited use in practice. In particular, we note that APN functions are typically classified up to CCZequivalence, and a major reason for the study of the less general EAequivalence and its associated invariants is due to the fact that the two notions of equivalence coincide for quadratic APN functions; that is, two quadratic APN functions are CCZequivalent if and only if they are EAequivalent. If the functions involved are not of algebraic degree 2, then EAequivalence no longer coincides with CCZequivalence in this sense. However, the algebraic degree can be a useful invariant if we truly need to classify functions up to EAequivalence (instead of using EAequivalence as an indirect method for testing CCZequivalence as in the case of quadratic APN functions). In particular, the CCZclass of a quadratic APN function can contain functions of various algebraic degrees, and the latter can be used to distinguish EAinequivalent functions. The algebraic degree can play a prominent role in theoretical arguments and, in particular, proofs of inequivalence; as a noteworthy example, it was used to show that CCZequivalence is strictly more general than EAequivalence combined with taking inverses [
20].
A related invariant is the minimum degree, introduced in [
20]. The
minimum degree of an (
n,
n)function
F, denoted
\({\min \limits } d^{\circ }(F)\), is the minimum algebraic degree of a component function of
F:
In general, the minimum degree and algebraic degree of an (
n,
n)function can be different. Furthermore, as long as the minimum degree is greater than 1, it is invariant under EAequivalence. As in the case of the algebraic degree, the minimum degree is not useful for distinguishing between quadratic functions, but can be effective in other contexts. In [
20], for instance, the first infinite families of APN and AB functions inequivalent to power functions are constructed, and the minimum degree is used in the proof of this inequivalence.
$$ \min d^{\circ}(F) = \min \{ \deg(F_{b}) : 0 \ne b \in \mathbb{F}_{2^{n}} \}. $$
4.3 Number of subspaces in the set of nonbent components
4.3.1 Definition
Recall that a Boolean (
n,1)function
f is called bent if its nonlinearity equals 2
^{n− 1} − 2
^{n/2 − 1}. Equivalently,
f is bent if and only if its Walsh transform satisfies
W
_{f}(
a) = ± 2
^{n/2} for all
\(a \in \mathbb {F}_{2^{n}}\). Given an (
n,
n)function
F, we can define the set
\(\mathcal {S}_{F}\) of those elements
\(b \in \mathbb {F}_{2^{n}}\) for which the component function
F
_{b} = Tr(
b
F(
x)) is not bent; symbolically, we can write
or, equivalently,
in the case of quadratic
F.
$$ \mathcal{S}_{F} = \{ b \in \mathbb{F}_{2^{n}} : (\exists a \in \mathbb{F}_{2^{n}}) W_{F}(a,b) \ne \pm 2^{n/2} \}, $$
$$ \mathcal{S}_{F} = \{ b \in \mathbb{F}_{2^{n}} : (\exists a \in \mathbb{F}_{2^{n}}) W_{F}(a,b) = 0 \} $$
If we now denote by
n
_{F}(
i) the number of
idimensional linear subspaces contained in
\(\mathcal {S}_{F}\), the value
n
_{F}(
i) is an EAinvariant for any natural number
i; that is, if
F and
G are EAequivalent, then
n
_{F}(
i) =
n
_{G}(
i) for all
i [
13,
39]. This is easy to see from the fact that if
G =
A
_{1} ∘
F ∘
A
_{2} +
A, with all involved functions defined as in (
3), then
\(b \in \mathcal {S}_{F}\) if and only if
\(A_{1}^{\prime }(b) \in \mathcal {S}_{G}\), where
\(A_{1}^{\prime }(x)\) is the adjoint operator of
A
_{1}(
x) +
A
_{1}(0). Clearly, if
n
_{F}(
i) = 0 for some
i, then
n
_{F}(
j) = 0 for all
j ≥
i as well. This allows us to compute
\(\mathcal {S}_{F}\) and the values of
n
_{F}(
i) for
\(i = 1, 2, 3, \dots \) until an
\(i^{\prime }\) is found for which
\(n_{F}(i^{\prime }) = 0\), and to use the vector
\(N_{F} = (n_{F}(1), n_{F}(2), \dots , n_{F}(i^{\prime }1))\) for distinguishing between EAclasses.
Note that this invariant is only useful in the case of even dimensions. In the case of odd
n, any quadratic APN (
n,
n)function is AB, so that we have
\(\{ W_{F}(a,b) : a \in \mathbb {F}_{2^{n}} \} = \{ 0, \pm 2^{(n+1)/2} \}\) for any
\(0 \ne b \in \mathbb {F}_{2^{n}}\). Consequently,
\(\mathcal {S}_{F} = \mathbb {F}_{2^{n}}\), and
N
_{F} has no distinguishing power.
4.3.2 Evaluation
Implementing
N
_{F} as an invariant is simple and easily doable in any generalpurpose programming language. As observed in Section
3.2, the Walsh transform can be readily implemented via standard arithmetic and logic operations, and the entire Walsh spectrum of a given function can be computed quite quickly. In this case, the entire Walsh spectrum does not need to be computed (for every
\(b \in \mathbb {F}_{2^{n}}\), we can stop computing
W
_{F}(
a,
b) as soon as we find an
\(a \in \mathbb {F}_{2^{n}}\) which witnesses that
F
_{b} is not bent), so the computation of
\(\mathcal {S}_{F}\) is even faster. In particular, if the Walsh spectrum or extended Walsh spectrum has already been computed for the given function (say, in the process of computing some other invariant),
\(\mathcal {S}_{F}\) can be determined almost immediately.
Computing the number
n
_{F}(
i) of subspaces of a given dimension
i is the most computationally heavy part of the calculation. The simplest possible approach is to perform an exhaustive search, which is usually sufficiently fast, and does not require anything more complicated than using finite field (or, equivalently, vector space) addition via XOR, and verifying that a set of elements is closed under addition. Furthermore, an algorithm for recovering the subspaces contained in a given set of elements has been developed recently [
7], and can be used to further speed up the computations.
The memory consumption is also very modest, although the computation time does increase exponentially with the dimension. Table
11 shows the time (in seconds) for computing
N
_{F} for
x
^{3} over
\(\mathbb {F}_{2^{n}}\) for all even dimensions
n in the range 6 ≤
n ≤ 12 on a simple implementation in C.
Table 11
Computation times and number of distinct values for
N
_{F} for some known APN instances
n

6

8

10

12


time (s)

0.004

0.168

11.508

1151.773

number of functions

14

8181

21

–

values

6

641

11

–

4.4 The thickness spectrum
4.4.1 Definition
The notion of the thickness of a vector space is introduced in [
24]. Given an (
n,
n)function
F, we begin by finding the set
\(\mathcal {Z}_{F}\) of its Walsh zeros, that is, the pairs
\((a,b) \in \mathbb {F}_{2^{n}}^{2}\) on which the Walsh transform of
F evaluates to zero:
The
thickness of any subspace
\(V \subseteq \mathcal {Z}_{F}\) is defined as the dimension of its projection onto
\(\{ (0,x) : x \in \mathbb {F}_{2^{n}} \}\). Equivalently, if
V is an
ndimensional space and
L is a linear permutation of
\(\mathbb {F}_{2^{2n}}\) mapping
\(\{ (x,0) : x \in \mathbb {F}_{2^{n}} \}\) to
V, we can write
L in matrix form as
The thickness of
V is then the rank of
c.
$$ \mathcal{Z}_{F} = \{ (a,b) : a,b \in \mathbb{F}_{2^{n}}, W_{F}(a,b) = 0 \}. $$
$$ L = \left[ \begin{array}{cc} a & b \\ c & d \end{array} \right]. $$
Let
i be any natural number, and let us denote by
t
_{F}(
i) the number of
ndimensional subspaces of
\(\mathcal {Z}_{F}\) that have thickness
i. The
thickness spectrum of
F is then the vector
\(T_{F} = (t_{F}(1), t_{F}(2), \dots , t_{F}(i))\), where
i is the smallest natural number for which
t
_{F}(
i) = 0. As with the number
n
_{F}(
i) of subspaces in the set of nonbent components, if
t
_{F}(
i) = 0 for some
i, then
t
_{F}(
j) = 0 for all
j ≥
i as well, so the previous definition is justified. The thickness spectrum can then be shown to be invariant under EAequivalence.
4.4.2 Evaluation
The computation of the thickness spectrum involves computing
\(\mathcal {Z}_{F}\) (which essentially involves computing the Walsh spectrum of
F), then going through all
ndimensional subspaces of
\(\mathcal {Z}_{F}\) and computing the thickness of each subspace. Finding these subspaces can be done using the same approaches used in the computation of
N
_{F} discussed in Section
4.3. The rest of the implementation is conceptually simple: after finding the
ndimensional subspaces, it is trivial to project them onto
\(\{ (0,x) : x \in \mathbb {F}_{2^{n}} \}\) by restricting the coordinates on the lefthand side to zero; and computing the dimension of the projections amounts to counting the number of elements that they contain.
On the other hand, the time for computing
T
_{F} is longer than that for computing
N
_{F}, since we have to work over a 2
ndimensional (instead of
ndimensional) vector space. It is intuitively clear that if
k <
l <
n are natural numbers, then finding all
kdimensional subspaces in a set of elements from
\(\mathbb {F}_{2}^{2n}\) is easier than finding all
ldimensional subspaces. In the case of
N
_{F}, one might restrict to the computation of
n
_{F}(
i) for only small values of
i, and still hope to obtain a useful invariant. In the case of
T
_{F}, all
ndimensional subspaces have to be found before any further computations can take place. Table
12 gives a summary of the time (in seconds) needed for computing the thickness spectrum of
x
^{3} over
\(\mathbb {F}_{2^{n}}\) with 6 ≤
n ≤ 10 using the SboxU library [
49]. As we can see from Table
11, the running times for computing
N
_{F} and
T
_{F} are comparable; however,
N
_{F} tends to have more distinguishing power than the thickness spectrum.
Table 12
Computation time and number of values of the thickness spectrum for some known APN instances
n

6

7

8

9

10


time (s)

0.86

1.12

0.92

188.174

8.91

total

14

–

8181

46

21

values

8

–

185

40

7

4.5 A family of invariants based on zero sums
4.5.1 Definition
An algorithm for computationally testing two given (
n,
n)functions
F and
G for EAequivalence is developed in [
42]. The algorithm is based on computing two multisets, one for
F and one for
G, which contain some information about the mapping
A
_{1} from (
3). More precisely, each element of
\(\mathbb {F}_{2^{n}}\) occurs in each of the two multisets with a certain multiplicity, and it is shown that
x and
A
_{1}(
x) must have the same multiplicity for any
\(x \in \mathbb {F}_{2^{n}}\) if (
3) holds. In particular, the multiplicities of the two associated multisets must be the same, i.e. they are invariant under EAequivalence.
To make this more precise, we let
k be a natural number, and define
in other words,
\({{\Sigma }_{F}^{k}}\) is the multiset of the sums of
F on all
ktuples of elements adding up to 0. If
F and
G are EAequivalent, and
k is even, then the multiplicities of
\({{\Sigma }_{F}^{k}}\) and
\({{\Sigma }_{G}^{k}}\) are the same. Note that it does not matter whether these
ktuples are taken to be ordered, unordered, or whether we allow repetitions among their elements; all of these variations lead to what is essentially the same invariant.
$$ {{\Sigma}_{F}^{k}} = [ F(x_{1}) + F(x_{2}) + {\dots} + F(x_{k}) : x_{1}, x_{2}, \dots, x_{k} \in \mathbb{F}_{2^{n}}, x_{1} + x_{2} + {\dots} + x_{k} = 0 ]; $$
The smallest possible value for which the invariants make sense is
k = 4 (for
k = 2, the multiset
\({{\Sigma }_{F}^{2}}\) would consist only of zeros). The multiplicities of
\({{\Sigma }_{F}^{k}}\) can always be computed via the Walsh transform; if
\({m_{F}^{k}}(s)\) denotes the multiplicity of
\(s \in \mathbb {F}_{2^{n}}\) in
\({{\Sigma }_{F}^{k}}\), then
This method for computing the multiplicities has the advantage that its time complexity does not depend on the choice of
k, which only affects the power to which the Walsh coefficients in (
6) have to be raised.
$$ {{m}_{F}^{k}}(s) = \frac{1}{2^{2n}} \underset{a,b \in \mathbb{F}_{2^{n}}}{\sum} (1)^{b \cdot s} {W_{F}^{k}}(a,b). $$
(6)
The proof of the above statement can be found in the full version of the conference paper [
42], which is under review at
Cryptography and Communications at the moment; for the sake of completeness, we describe the basic idea below. The statement follows by straightforward manipulations using the properties of the Walsh transform. We have
$$ \begin{array}{@{}rcl@{}} {\sum}_{a,b} (1)^{b \cdot s} {W_{F}^{k}}(a,b) &= & \underset{a,b}{\sum} \underset{x_{1}, x_{2}, \ldots, x_{k}}{\sum} (1)^{b \cdot (F(x_{1}) + F(x_{2}) + {\dots} + F(x_{k}) + s) + a \cdot (x_{1} + x_{2} + {\dots} + a_{k})} \\ &= & 2^{2n} \# \{ (x_{1}, x_{2}, \dots, x_{k}) \in \mathbb{F}_{2^{n}}^{k} : \sum\limits_{i = 1}^{k} x_{i} = 0, \sum\limits_{i = 1}^{k} F(x_{i}) = s \}, \end{array} $$
which then easily implies (
6).
It must be noted that in the case of APN functions, the
\({{\Sigma }_{F}^{k}}\) invariant is essentially the same as the π
_{F} invariant described in Section
3.4; that is, if
F and
G are both APN, then π
_{F} = π
_{G} if and only if
\({{\Sigma }_{F}^{k}}\) and
\({{\Sigma }_{G}^{k}}\) have the same multiplicities. An advantage of
\({{\Sigma }_{F}^{k}}\) is that it remains invariant for functions of any differential uniformity, while π
_{F} is invariant only in the case of APN functions;
\({{\Sigma }_{F}^{k}}\) also provides information about what the EAequivalence between the two tested functions might look like, while π
_{F} does not. On the other hand, π
_{F} is invariant under CCZequivalence (and it is easy to find counterexamples showing that
\({{\Sigma }_{F}^{k}}\) is not), and provides a lower bound on the distance between
F and the closest APN function.
4.5.2 Evaluation
One of the advantages of the algorithm in [
42] is that it does not require any complicated mathematical or algorithmic machinery, and can be implemented from first principles (as opposed to the linear code test for CCZequivalence). Regardless of whether the computation is done from the definition, or via the Walsh transform, it only requires finite field (or vector space) addition, which can be represented as XOR, and counting multiplicities of elements from the finite field. If the Walsh spectrum of
F is available, computing the multiplicities of
\({{\Sigma }_{F}^{k}}\) via (
6) is quite straightforward. For the sake of completeness, we mention also the recently published algorithm for testing the EAequivalence of quadratic functions [
23].
As noted above, π
_{F} and
\({{\Sigma }_{F}^{4}}\) have the same distinguishing power in the case of APN functions. In particular, these invariants are only useful in the case of even dimensions, in which case they can take a lot of distinct values. Once again, representatives from the known infinite families of APN functions (with the notable exception of the inverse power function over odd dimensions) have the same value of
\({{\Sigma }_{F}^{4}}\) as the Gold function
x
^{3}.
4.6 Orthoderivatives
4.6.1 Definition
The concept of an orthoderivative is introduced in [
23,
49], and appears to be quite useful for partitioning quadratic APN functions into EAequivalence classes. Given a quadratic (
n,
n)function
F, an
orthoderivative of
F is any (
n,
n)function
π
_{F} such that
for all
\(x \in \mathbb {F}_{2^{n}}\). In this sense,
π
_{F} is orthogonal to all values of the expression
F(
x +
a) +
F(
x) +
F(
a) +
F(0) =
D
_{a}
F(
x) +
D
_{a}
F(0). Note that orthoderivatives can be defined for any (
n,
n)function
F; however,
F is APN if and only if
π
_{F}(
a) is uniquely defined for all nonzero
\(a \in \mathbb {F}_{2^{n}}\). Thus, in the APN case, a unique (
n,
n)function
π
_{F} can be associated with any quadratic APN (
n,
n)function
F. Furthermore, it is known that if
F and
G are two EAequivalent (
n,
n)functions via
A
_{1} ∘
F ∘
A
_{2} +
A =
G, then
thus, the orthoderivatives of two EAequivalent APN functions are EAequivalent themselves. The advantage is that the orthoderivatives have a much more “varied” structure than the APN functions that they are associated with; as pointed out in [
23], it seems that the algebraic degree of
π
_{F} is
n − 2 whenever
F is an APN (
n,
n)function. This is intuitively one of the reasons that the orthoderivatives can take on many different values for the various invariants under EAequivalence and CCZequivalence, and the latter become immensely more useful for partitioning functions into EAclasses.
$$ \pi_{F}(a) \cdot (F(x) + F(a+x) + F(a) + F(0) ) = 0 $$
(7)
$$ \pi_{G} = {A}_{1}^{1} \circ \pi_{F} \circ A_{2}; $$
4.6.2 Evaluation
Computing the truth table of the orthoderivative itself is a very easy task; the simplest way involves guessing the value of
π
_{F}(
a) for each
\(0 \ne a \in \mathbb {F}_{2^{n}}\). For every possible candidate for the value of
π
_{F}(
a), it suffices to verify that (
7) is satisfied. Computing (
7), on other hand, requires nothing more than vector space addition and the implementation of the scalar product. The truth table of
π
_{F} can thus be reconstructed very quickly, even for relatively large dimensions. Table
13 gives some sample running times (in seconds) for computing the orthoderivative of
x
^{3} using SboxU. The row labeled “functions” gives the number of functions that were tested (all of them being CCZinequivalent to each other); while “values” gives the number of distinct values obtained across all of these functions. The set of functions used for the tests consists of all known quadratic APN functions over
\(\mathbb {F}_{2^{n}}\) for the appropriate value of
n. We note that there are only two known cases in which CCZinequivalent functions can have an orthoderivative with the same differential spectrum and the same Walsh spectrum: these are the Gold functions
x
^{3} and
x
^{9} over
\(\mathbb {F}_{2^{7}}\), and the Gold functions
x
^{3} and
x
^{33} over
\(\mathbb {F}_{2^{9}}\). The CCZclasses of all other known quadratic APN functions (including the other Gold functions, e.g.
x
^{5},
x
^{9} and
x
^{17} over
\(\mathbb {F}_{2^{9}}\)) can be distinguished with the help of orthoderivatives in this way.
Table 13
Computation time for finding the truth table of
π
_{F}, and number of values of the Walsh and differential spectra of
π
_{F} for some known APN instances
n

6

7

8

9

10

11

12


time (s)

0

0.00021

0.0006

0.002

0.34

0.22

0.84

functions

14

488

21 103

42

19

–

–

values

14

487

21 103

41

19

–

–

Once the orthoderivative is computed, it remains to apply some of the previously examined invariants, such as the Walsh spectrum and differential spectrum, to distinguish between the EAclasses of the orthoderivatives. The number of values in Table
13 refers to the number of distinct combinations of the Walsh spectrum and differential spectrum observed among the orthoderivatives. Note that the orthoderivatives themselves are not APN, and so the differential spectrum becomes a useful invariant. In fact, as indicated by the data in Table
13, this is sufficient to distinguish between all currently known classes of quadratic APN functions (with the exception of some Gold functions). Thus, a partitioning by means of the orthoderivatives appears to have the same strength in practice as an EAequivalence test. Nonetheless, invariants can only be used to disprove the equivalence between two functions; and so, if two (
n,
n)functions
F and
G have the same invariants for
π
_{F} and
π
_{G}, this does not constitute a proof of their EAequivalence. It would thus be very interesting to find more examples of EAinequivalent functions whose orthoderivatives have the same spectrum of invariant values.
Despite this, as indicated by Table
13, the combination of the extended Walsh spectrum and the differential spectrum of the orthoderivative is sufficient to distinguish between any pair of EAinequivalent quadratic APN functions (with the exception of the Gold functions).
5 Conclusion
We have surveyed some known invariants on (
n,
n)functions under CCZ and EAequivalence. The list of invariants is not meant to be complete, but aims to include all invariants that are commonly used in the classification of APN and AB functions in practice. Each of the invariants is evaluated in terms of how easy it is to implement in a generalpurpose programming language, how efficient it is to compute, and how well it can distinguish between distinct equivalence classes of (
n,
n)functions.
The considered CCZinvariants include:

the differential uniformity and nonlinearity (trivial);

the extended Walsh spectrum \(\mathcal {W}_{F}\);

the invariants from the associated combinatorial designs d e v( G _{F}) and d e v( D _{F}), viz. the Γrank, Δrank, and order of the multiplier group, as well as the orders of the automorphism groups of d e v( G _{F}) and d e v( D _{F});

the multiset π _{F} used in the computation of the lower bound on the Hamming distance between two APN functions (invariant only for APN functions).
The considered EAinvariants include:

all CCZinvariants;

the algebraic degree \(\deg (F)\) and the minimum degree \({\min \limits } d^{\circ }(F)\);

the number n _{F}( i) of idimensional subspaces in the set \(\mathcal {S}_{F}\) of nonbent components of F;

the number t _{F}( i) of ndimensional subspaces of thickness i in the set \(\mathcal {Z}_{F}\) of Walsh zeros of F;

the multiplicities of the elements in the multiset \({{\Sigma }_{F}^{k}}\) for all even k, i.e. the number of times that each element of \(\mathbb {F}_{2^{n}}\) can be expressed as a sum \(F(x_{1}) + F(x_{2}) + {\dots } + F(x_{k})\) with \(x_{1} + x_{2} + {\dots } + x_{k} = 0\);

the orthoderivatives π _{F} (or, to be more precise, the EAequivalence class of the orthoderivative).
For each invariant, we have used a straightforward implementation in a suitable programming language (typically C in the case of the invariants that can be defined and computed from first principles, and
Magma when more sophisticated mathematical structures or algorithms are involved) and have given example running times over the range of dimensions
n in which the invariant can be reasonably used in practice. We have also counted how many different values each invariant can take over some of the known APN instances in each dimension, and have remarked on the further properties and significance of some of the invariants.
Acknowledgements
The research presented in this paper was supported by the Trond Mohn Foundation.
I would like to express my gratitude to the anonymous reviewers for their thorough proofreading and helpful comments. I would also like to thank Lilya Budaghyan and Christof Beierle for various useful remarks and discussions.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit
http://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.