Christina Boura
email: christina.boura@uvsq.fr

Anne Canteaut
email: anne.canteaut@inria.fr

Jérémy Jean
email: jeremy.jean@ssi.gouv.fr

Valentin Suder
email: valentin.suder@uvsq.fr

Two Notions of Differential Equivalence on Sboxes

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Block ciphers are central primitives in symmetric encryption schemes. Modern block ciphers are designed based on a methodology which guarantees that the cipher is resistant against all classical attacks. The differential cryptanalysis, presented by Biham and Shamir in 1990 [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF], is one of the most prominent attacks against block ciphers, and a precise evaluation of its complexity has led to some design criteria on the building blocks in the cipher. The main criterion, which has been introduced by Nyberg and Knudsen [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF][START_REF] Nyberg | Provable security against differential cryptanalysis (rump session)[END_REF], is the so-called differential uniformity of the Sbox, i.e., of the nonlinear mapping used in the cipher. This parameter should be as small as possible in order to maximize the complexity of differential attacks, and the mappings with the lowest differential uniformity, named APN mappings, have been investigated in many works during the last twenty-five years. Indeed, these mappings are highly relevant for cryptographic applications and they are also optimal combinatorial objects of independent interest. Therefore, this design criterion is at the origin of a whole line of research, including the search for infinite families of permutations with a low differential uniformity, the study of their properties or some classification work (e.g. [START_REF] Browning | An APN permutation in dimension six[END_REF][START_REF] Carlet | Codes, Bent Functions and Permutations Suitable For DES-like Cryptosystems[END_REF][START_REF] Chabaud | Links between differential and linear cryptoanalysis[END_REF][START_REF] Dobbertin | Almost Perfect Nonlinear Power Functions on GF(2 n ): The Welch Case[END_REF][START_REF] Edel | A new APN function which is not equivalent to a power mapping[END_REF][START_REF] Hernando | Proof of a conjecture on the sequence of exceptional numbers, classifying cyclic codes and APN functions[END_REF][START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF]).

However, besides the differential uniformity of the Sbox, the whole differential spectrum and even the form of the difference distribution table (DDT) are important when the resistance against several variants of differential cryptanalysis is quantified. Obviously, the number of occurrences of the differential uniformity in the DDT of the Sbox corresponds to the number of one-round differentials with the highest probability and should then be minimized. Also, the whole differential spectrum of the Sbox is involved in all known upper-bounds on the maximal expected differential probability over two rounds of an SPN cipher [START_REF] Canteaut | On the behaviors of affine equivalent sboxes regarding differential and linear attacks[END_REF][START_REF] Park | Improving the upper bound on the maximum differential and the maximum linear Hull probability for SPN structures and AES[END_REF]. Not only the number, but also the location within the DDT of these maximal values may influence the resistance of the cipher against multiple differential cryptanalysis [START_REF] Blondeau | Multiple differential cryptanalysis: Theory and practice[END_REF] or truncated differential attacks [START_REF] Knudsen | Truncated and higher order differentials[END_REF] (see e.g. [2, Section 3.2] for a discussion). When designing block ciphers, it would then be of major interest to be able to start from a desired DDT which guarantees a high resistance against all variants of differential cryptanalysis, and to construct Sboxes having this specific DDT. Instead, the main technique currently available to the designers consists in randomly choosing Sboxes until one with a suitable DDT is found. However, constructing Sboxes from a prescribed DDT is a difficult problem, related to many open issues in the area. The characterization of the valid DDT, i.e. for which there exists at least one function with these particular DDT, is also open. In the case of APN functions, this general problem corresponds to the problem of determining the differential equivalence class of a given function, introduced by Gorodilova [START_REF] Gorodilova | On a remarkable property of APN Gold functions[END_REF]. It has also been raised by Carlet in the case of APN functions [START_REF] Carlet | Open questions on nonlinearity and on APN functions[END_REF]Pb. 3.11]. It is obviously related to the so-called Big APN problem, i.e., the existence of APN permutations operating on an even number of variables. Indeed, it has been long conjectured that bijective APN functions do only exist in odd dimension, until the first ever counter-example over F 6 2 was presented by Dillon et al. [START_REF] Browning | An APN permutation in dimension six[END_REF]. However, the conjecture still stands for any even dimension n ≥ 8.

Our Contributions. In this work, we provide a new algorithm for computing the differential equivalence class corresponding to a prescribed DDT. We applied this algorithm to find several equivalence classes. Most notably, one of the main problems we focus on is to determine whether the differential equivalence class of a permutation over F n 2 can contain more than 2 2n elements. In other words, we wonder whether two permutations F and G with the same DDT necessarily satisfy G(x) = F (x⊕c)⊕d for some c, d ∈ F n 2 . As a result, we found permutations F whose differential equivalence classes contain other elements than the functions x → F (x ⊕ c) ⊕ d. However, we conjecture that this is only the case when some rows of the corresponding DDT are equals. We also discuss some properties of the DDT of an APN permutation, adding some constraints on the valid DDT for such permutations.

Even if the following properties hold in the general case, our work mainly focuses on vectorial Boolean functions with the same number of inputs and outputs, i.e., on functions from F n 2 into itself. Cryptographic Sboxes are examples of such functions that usually verify additional properties for cryptographic applications, most notably nonlinearity. Although we focus on Sboxes in the remainder of this paper, most of the results can be adapted to general vectorial Boolean functions.

The differential properties of a vectorial Boolean function are related to its derivatives.

Definition 1 (Derivative of a function). Let F be a function from

F n 2 into F n 2 .
The derivative of F with respect to a ∈ F n 2 is the function

∆ a F : x ∈ F n 2 → F (x ⊕ a) ⊕ F (x).
The multi-sets corresponding to the images of the derivatives of F are usually represented as a two-dimensional array called the difference distribution table.

Definition 2 (DDT and its characteristics). Let F be a function from

F n 2 into F n 2 . The difference distribution table (DDT) of F is the two-dimensional table defined by δ F (a, b) = #{x ∈ F n 2 : ∆ a F (x) = b}, ∀a, b ∈ F n 2 .
Two important characteristics of the DDT, introduced in [START_REF] Carlet | Codes, Bent Functions and Permutations Suitable For DES-like Cryptosystems[END_REF][START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF] respectively, are as follows:

the differential uniformity of F is the highest value in the DDT, i.e. The previous properties then lead to two different notions of equivalence between Sboxes. We say that -F and G are DDT-equivalent if they have the same DDT; -F and G are γ-equivalent if their DDTs have the same support, or equivalently if

γ F = γ G .
The notion of γ-equivalence has been investigated under the name differential equivalence by Gorodilova [START_REF] Gorodilova | On a remarkable property of APN Gold functions[END_REF]. It must not be confused with the differential equivalence introduced in [START_REF] Suder | Antiderivative functions over F2n[END_REF][START_REF] Suder | Antiderivative functions over F2n[END_REF], which refers to another property. Obviously, DDT-equivalence implies γ-equivalence. However, the converse also holds in some particular cases.

Proposition 1. Let F and G be two functions from F n 2 into itself which are γequivalent. Assume that, for each derivate of F and G, there exists some integer λ such that the derivative is a λ-to-1 function. Then, F and G are DDT-equivalent. Most notably, this situation holds for quadratic functions or for APN functions.

Proof. The result comes from the fact that, in this case, the DDT of the function is entirely determined by its support. Assume that, for any a ∈ F n 2 , a = 0, ∆ a F is a λ-to-1 function (where λ may depend on a). Then, the entries of the row in the DDT corresponding to ∆ a F belong to {0, λ}. Since the sum of all entries within a row equals 2 n , we deduce that λ is a power of 2, and its value can be deduced from the number of elements b such that γ F (a, b) = 1 which equals 2 n λ -1 . Then, the row corresponding to ∆ a F is entirely deduced from γ F . When F is a quadratic function, its derivatives have degree at most 1. Then, ∆ a F is a 2 d -to-1 function where d is the dimension of the kernel of ∆ a F .

The previous proposition obviously includes the case of quadratic APN functions studied in [START_REF] Gorodilova | On a remarkable property of APN Gold functions[END_REF] and in [START_REF] Yu | A matrix approach for constructing quadratic APN functions[END_REF], implying that the γ-equivalent APN functions exhibited in [START_REF] Gorodilova | On a remarkable property of APN Gold functions[END_REF] are also DDT-equivalent.

In general, the two notions of differential equivalence do not coincide. The following example exhibits two γ-equivalent functions with different DDTs.

Example 1. Let F and G : F 4 2 → F 4 2 be represented by their value tables: In this work, we mainly focus on the sizes of the DDT-equivalence classes and γ-equivalence classes. A lower bound on these sizes is given in the following proposition.

F = [0x0,0x1,0x2,0x3,0x4,0x5,0x6,0x7,0x8,0x9,0xA,0xB,0xC,0xD,0xF,0xE], G = [0x0,0x1,0x3,0x2,0x5,0x4,0x7,0x6,0x8,0x9,0xA,0xB,0xC,0xD,0xE,0xF].
Proposition 2. Let F be a function from F n 2 into itself and let denote the dimension of its linear space, i.e., of the space formed by all a ∈ F n 2 such that ∆ a F is constant. Then, the DDT-equivalence class of F contains the 2 2n-distinct functions of the form

x → F (x ⊕ c) ⊕ d, c, d ∈ F n 2 . (1)
Proof. The fact that all functions F c,d :

x → F (x ⊕ c) ⊕ d
∈ F n 2 , F (x ⊕ c 1 ) ⊕ F (x ⊕ c 2 ) = d 1 ⊕ d 2 , which means that ∆ c1⊕c2 F = d 1 ⊕ d 2 , i.e. (c 1 ⊕ c 2 ) is a linear structure and d 2 = d 1 ⊕ ∆ c1⊕c2 F . Then, the number of distinct functions F c,d equals 2 2n-.
In the sequel, we consider that two functions are trivially DDT-equivalent if they satisfy the Relation (1) from the above Proposition 2. Moreover, we say that a DDT-equivalent class is trivial if its size matches the lower-bound given in Proposition 2.

Another important property of the size of these equivalence classes is the following result proved in [START_REF] Gorodilova | On a remarkable property of APN Gold functions[END_REF] for γ-equivalence, which can easily be generalized to DDT-equivalence. Proposition 3. Let F and G be two functions which are EA-equivalent, i.e., there exist three affine functions A 0 , A 1 , A 2 where A 1 and A 2 are bijective such that G = A 2 •F •A 1 ⊕A 0 . Then, the DDT-equivalence classes (resp. γ-equivalence classes) of F and of G have the same size. Moreover, the class of

G is composed of all A 2 • F • A 1 ⊕ A 0 where F varies in the class of F .
It follows that the sizes of these differential-equivalence classes can be computed for one representative in each EA-equivalence class only.

Computation of the γ-Equivalence and DDT-Equivalence Classes

We present in this section an algorithm that takes as input a 2 n × 2 n table D filled with nonnegative integers and returns all functions F from F n 2 into itself, if any, whose difference distribution table has the same indicator (see Definition 2) as the one of D, which we denote γ D . In other words, our algorithm retrieves the γ-equivalence class of functions of a given table D. Note that one can also derive the DDT-equivalent functions from this class, by post-filtering the functions returned by the algorithm.

Throughout the following sections, we denote binary vectors of F n 2 by integers and make an extensive use of this notation. The algorithm determines all possible values for F (i), i = 0, . . . , 2 n -1, by taking into account the constraints imposed by the table D and the values F (j), j < i, that have already been computed. It essentially implements a tree-traversal algorithm, where each Level i contains the nodes corresponding to the possible values that F (i) can take. The tree therefore has depth 2 n . There is a natural incentive to implement such algorithms using recursion, which we adopt in the sequel.

From now on, we denote by R i = {y : D[i][y] = 0} the set of column indices of non-zero elements on D's ith row. The algorithm starts running and tries to determine all possible values for F (0), F (1), . . . , F (2 n -1). By assuming that all values F (0), F (1), . . . , F (i -1) have already been set, the value F (i) can be computed according to the following relations:

-F (i) ⊕ F (0) = ∆ i F (0) must lie in R i , -F (i) ⊕ F (1) = ∆ i⊕1 F (1) must lie in R i⊕1 , -F (i) ⊕ F (2) = ∆ i⊕2 F (2) must lie in R i⊕2 , -. . . -F (i) ⊕ F (i -1) = ∆ i⊕(i-1) F (i -1) must lie in R i⊕(i-1) .
Thus, F (i) should lie in the intersection of the sets

{x ⊕ F (0) : x ∈ R i } ∩ {x ⊕ F (1) : x ∈ R i⊕1 } ∩ • • • ∩ {x ⊕ F (i -1) : x ∈ R i⊕(i-1) }.
If this intersection is empty, then the algorithm backtracks and picks another value for F (i -1), from the set of possible values. Otherwise, F (i) is set to the smallest element in the intersection and the algorithm continues by searching for possible values for F (i + 1). At this point, it has to be noticed that F (0) can take any given value. However, we explain now a pruning observation that prevents the algorithm from trying all possible 2 n values for F (0) and all possible values for F (1).

Pruning. We can reduce the search space of the algorithm by pruning some branches. The procedure starts, without restriction, by the determination of the images of 0 and 1. We explain now why it is possible to fix those two values and still recover all the other functions for different values of these images.

First, recall that a function F (x) and F (x) ⊕ d, for any d ∈ F n 2 , have the same DDT. This implies that there are at least 2 n functions having a certain DDT for any image of 0. We can therefore fix the image of 0 to any particular value, and query the algorithm for functions having this first defined point. All the other functions will then be recovered by translation.

Second, for a defined image of 0, it is not necessary to ask the algorithm to look for every possible image of 1. Indeed, the functions F (x) and F (x⊕c)⊕F (0)⊕F (c), for any c ∈ F n 2 , have the same DDT. This means that, once F (0) has been fixed, there are as many solutions for any value of F (1) as long as F (0) ⊕ F (1) ∈ R 1 . Moreover, remark that there is an even number of functions having the same DDT and the same images in 0 and 1: the functions F (x) and F (x ⊕ 1) ⊕ F (0) ⊕ F (1) are equal in 0 and 1.

One Example. Before giving the pseudo-code of the algorithm, we show a small example of its execution for the 2 3 × 2 3 table shown in Figure 1, which corresponds to the DDT of the PRINTcipher Sbox [START_REF] Knudsen | PRINTcipher: A block cipher for IC-printing[END_REF].

Here are the main steps performed by the algorithm (also see Figure 2): and add it to a list of solutions. We then backtrack to find the other solutions.

1. Set F (0) = 0 2. Set F (1) = 1, as 1 is the minimal value of the set R 1 = {1, 3, 5, 7} 3. As F (2) ⊕ F (0) ∈ R 2 = {2, 3, 6, 7} and F (2) ⊕ F (1) ∈ R 3 = {1, 2, 5, 6}, F (2) ∈ {2, 3, 6, 7} ∩ {0, 3, 4, 7} = {3, 7}. Set F (2) = 3. 4. As F (3) ⊕ F (0) ∈ R 3 = {1, 2, 5, 6}, F (3) ⊕ F (1) ∈ R 2 = {2, 3, 6, 7} and F (3) ⊕ F (2) ∈ R 1 = {1, 3, 5, 7}, F (3) ∈ {1, 2, 5, 6} ∩ {2, 3, 6, 7} ∩ {0, 2, 4, 6} = {2, 6}. Set F (3) = 2. 5. As F (4) ⊕ F (0) ∈ R 4 = {4, 5, 6, 7}, F (4) ⊕ F (1) ∈ R 5 = {1, 3, 4, 6}, F (4) ⊕ F (2) ∈ R 6 = {2, 3, 4, 5} and F (4) ⊕ F (3) ∈ R 7 = {1, 2,
The two solutions found with the restrictions F (0) = 0 and F (1) = 1 are F = (0, 1, 3, 6, 7, 4, 5, 2) and F = (0, 1, 7, 2, 5, 6, 3, 4) as it can be seen in Figure 2. All the γ-equivalent functions can be found by computing

F (x ⊕ c) ⊕ d and F (x ⊕ c) ⊕ d for all c, d ∈ F 3 2 .
At the end, we obtain 2 6 γ-equivalent functions.

Figure2: Example of the algorithm's execution on the table of Figure 1.

Algorithm 1 Main

Input: A table D of size 2 n × 2 n Output: A list F of all functions F : F n 2 → F n 2 γ-equivalent to the indicator of D 1: F ← {∅} Globaly defined 2: S ← [0, min{R1}, 0, . . . , 0] len(S) = 2 n 3: RecursifSearch(S, 2) 4: return F Algorithm 2 RecursifSearch Input: A table S of size 2 n , an integer i 1: if i < 2 n then 2: L ← 0≤k<i {x ⊕ S[k] : x ∈ R k } 3: else 4: if γS = γD then
Or DDT(S) = D if we test the DDT-equivalence 5:

Append S to F 6:

return 7: if L = ∅ then 8:
for all x ∈ L do 9:

S[i] ← x 10:
RecursifSearch(S, i + 1) 11: else 12: return Algorithm. In the algorithm, we take the pruning observation into account and only look for functions such that the image of 0 is 0 and the image of 1 is the first possible value. From now on, we denote by S a table of dimension 2 n used to store the intermediate possible images. Then, we denote by F a solution returned by the algorithm, obtained when all the cells of S have been set.

Hence, at the beginning, S[0] is set to 0 and S [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] is set to min{R 1 }. The recursive Algorithm 2 is then called for i = 2, where i means that the algorithm is searching for candidate values for S[i]. It starts by computing the possible values for S[i] on Line 2 and store them in a set L. If this set is not empty, the algorithm tries to compute the next value, S[i + 1], for every possible value of S[i]. The procedure is repeated until either S[2 n -1] has been set or L is empty. In the latter case, the algorithm backtracks to the next possible value in L at a certain Level i as there was no solution in this branch. In the former case, all the values for S have been set. At this point, we verify (Line 4) whether the function found has the same γ indicator as the table D (resp. it has D as a DDT). Indeed, it is possible that the support of γ S is strictly included in the one of the indicator of D.

One of the questions we are interested in is the existence of two DDT-equivalent permutations F and G, which are not related by G(x) = F (x ⊕ c) ⊕ d for some c, d. It is worth noticing that, in the case of non-bijective mappings, such pairs of functions exist. For instance, in [START_REF] Gorodilova | On a remarkable property of APN Gold functions[END_REF], 2 2n+n/2 quadratic functions have been exhibited, which are γ-equivalent (and thus DDT-equivalent) to the Gold function x 2 n/2+1 +1 over F 2 n when n is a multiple of 4.

Results for some Known Functions

Using the algorithm described in the previous section, we have been able to compute the γ-equivalence classes and the DDT-equivalence classes of some cryptographically relevant functions.

It is clear from Proposition 3, that it is sufficient to run the algorithm for a single representative in each EA-equivalence class. Hence, after computation, we can affirm that the size of the DDT-equivalence classes of all APN permutations over F n 2 , with n ≤ 6, is 2 2n . This equivalently means that each class is only obtained by translating the input and output of the representative function. More precisely, these representative permutations for each dimension n correspond to:

for n = 6: the so-called Dillon permutation [START_REF] Browning | An APN permutation in dimension six[END_REF], for n = 5: the five APN permutations described by Brinkmann and Leander in [4, Table 1], for n = 3: the Gold permutation.

We have also examined all permutations of dimension n = 4 with optimal differential uniformity (equal to 4) and nonlinearity from the 16 different affineequivalence classes given in [START_REF] Leander | On the Classification of 4 Bit S-Boxes[END_REF]. The γ-equivalence class for each of them contains exactly 2 8 elements. Since none of these functions has a linear structure, we deduce from Proposition 2 that these 2 8 elements also form their DDT-equivalence class.

Then, none of the permutations with the lowest possible differential uniformity in dimension n < 6 has a DDT-equivalence class with size bigger than 2 2n . However, it is possible to construct such permutations when we increase the differential uniformity.

An Example of Non-Trivially DDT-Equivalent Permutations

In this paragraph, we exhibit a permutation F over F 5 2 , such that some elements in its DDT-equivalence class are not of the form F (x ⊕ c) ⊕ d for any c, d ∈ F 5 2 . We consider the table D, composed by 2 × 2 blocks of the form 16 16 16 16 everywhere on the diagonal except for the first block which is 32 0 0 32 . By running our algorithm on this table, we recovered 56 × 2 8 permutations having this DDT. Even by considering the fact that the permutations corresponding to this DDT will necessarily have a linear structure, this number is still higher than the number of distinct functions of the form F (x ⊕ c) ⊕ d, which equals 2 2×5-1 as shown in Proposition 2.

In Table 1 are presented two functions F and F whose DDT is D but for which there is no pair (c, d) such that F (x) = F (x ⊕ c) ⊕ d for all x.

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

F (x)

A Conjecture on the Size of DDT-Equivalence Classes

We then know two examples of functions having a non-trivial DDT-equivalence class (in the sense that they contain more functions than the ones obtained by translations): some Gold functions studied in [START_REF] Gorodilova | On a remarkable property of APN Gold functions[END_REF] and the functions we exhibited above. The common point between these two examples is that they both have nondistinct rows in their DDTs. Besides this property, they seem to have very different characteristics. Indeed, the second ones are permutations with a linear structure, while the first ones are non-bijective and are APN. Moreover, as previously noticed, the APN permutations seem to not have larger DDT-equivalence classes (at least for small dimensions), and the permutations studied in Example 1 have a linear structure but its DDT-equivalence classes are trivial. These remarks, combined with the computations we have performed using our algorithm, lead us to the statement of the following conjecture.

Conjecture 1. The DDT-equivalence class of a permutation F , such that the rows in its DDT are pairwise distinct, only contains permutations of the form

F (x ⊕ c) ⊕ d, with c, d ∈ F n 2 (i.e. is trivial).
It is worth noticing that Example 1 shows that the same conjecture does not hold for γ-equivalence.

Hoping to make a step towards the proof of this conjecture, we show in the next section that APN permutations cannot have two equal rows in their DDTs.

Since the DDTs having at least two equal rows seem to play an important role, a natural question is the following: Is it possible that this situation occurs for some remarkable families of Sboxes? As a partial answer, we prove in this section that all the rows in the DDT of any APN permutation are distinct.

Let F be an APN permutation of F n 2 . We start by stating two simple remarks. The first remark is due to the fact that F is a permutation while the second one is a result of F being APN.

Remark 1. F (x) ⊕ F (y) = F (x) ⊕ F (z), for x, y, z ∈ F n 2 pairwise distinct.
Indeed, if we suppose that for some pairwise distinct x, y, z ∈ F n 2 , we have that F (x) ⊕ F (y) = F (x) ⊕ F (z), this would imply that F (y) = F (z), which is a contradiction by the fact that F is a permutation.

Remark 2. ∆ a F (x) = ∆ a F (y), for x, y, a ∈ F n 2 with y = {x, x ⊕ a} and a = 0.

Assuming an equality between the left and the right handsides of the equation, would imply an equality between two images of ∆ a F not trivially equal, which cannot occur as F is APN.

Theorem 1. Let F be an APN permutation of F n 2 . Then, the rows of the DDT of F are pairwise distinct.

Proof. We prove this result by contradiction. Indeed, suppose that the row of the DDT corresponding to the image set of ∆ a F equals the row corresponding to the image set of ∆ b F , for some a, b ∈ F n 2 \ {0} with a = b. The proof then tries to match the values ∆ a F (x), for x ∈ F n 2 with the values ∆ b F (x), for x ∈ F n 2 and to show that this is impossible to do. For this, we show that it is impossible to create a chain of values x 0 , x 1 , . . . , x 2 n -1 such that

∆ a F (x 0 ) = ∆ b F (x 1 ) ∆ a F (x 1 ) = ∆ b F (x 2 ) . . . ∆ a F (x 2 n -2 ) = ∆ b F (x 2 n -1 ).
We start by proving the following statement by induction.

Let x 0 , . . . , x k-1 ∈ F n 2 such that ∆ a F (x i ) = ∆ b F (x i+1 ) for all 0 ≤ i < k -1. Then, there are at most 2 n -4k possibilities for choosing x k such that ∆ a F (x k-1 ) = ∆ b F (x k ). More precisely, x k does not take any of the 4k values x i , x i ⊕ a, x i ⊕ b, x i ⊕ a ⊕ b, for i = 0, . . . , k -1. Basis. Let k = 1. Suppose that ∆ a F (x 0 ) = ∆ b F (x 1 )
. Then, the variable x 1 cannot take any of the four values x 0 , x 0 ⊕ a, x 0 ⊕ b and x 0 ⊕ a ⊕ b. Indeed, if we suppose for example that ∆ a F (x 0 ) = ∆ b F (x 0 ), this translates to F (x 0 ) ⊕ F (x 0 ⊕ a) = F (x 0 ) ⊕ F (x 0 ⊕ b) which is impossible by Remark 1. We use Remark 1 to prove in the same way the impossibility of the remaining three values. Therefore, there are at most 2 n -4 possible values for x 1 .

Inductive step. Suppose that for all i < k there are at most 2 n -4i possibilities for choosing x i and that x i cannot take any of the values in the set {x j , x j ⊕ a, x j ⊕ b, x j ⊕ a ⊕ b|0 ≤ j < i}. We show in the following that there are at most 2 n -4k possibilities for choosing x k .

We have that ∆ a (x k-1 ) = ∆ b (x k ). By Remark 1, we get that x k = {x k-1 , x k-1 ⊕ a, x k-1 ⊕ b, x k-1 ⊕ a ⊕ b}. We show now that x k / ∈ {x i , x i ⊕ a, x i ⊕ b, x i ⊕ a ⊕ b | 0 ≤ i ≤ k -2}. Indeed, suppose for example that x k = x i for some 0 ≤ i ≤ k -2. We have that

∆ a F (x i-1 ) = ∆ b F (x i ), ∆ a F (x k-1 ) = ∆ b F (x i ).
By adding these equations, we get that ∆ a F (x i-1 ) = ∆ a F (x k-1 ). By the induction hypothesis, x k-1 = x i-1 and since F is APN we get a contradiction by Remark 2. The other contradictions are obtained in a similar way by the induction hypothesis and Remark 2.

We show now that it is impossible to construct such a sequence x 0 , . . . , x 2 n -1 . Indeed, we can see, that for choosing for example a value for x k for k = 2 n-2 , there are 2 n -4 • 2 n-2 = 0 choices left. Therefore, we conclude that if F is an APN permutation of F n 2 all rows of the DDT must be pairwise distinct.

Conclusion

In this paper, we investigated two different notions of differential equivalence, the DDT-equivalence and the γ-equivalence, and provided an algorithm to compute both equivalence classes for a given vectorial Boolean function. During our experiments, we encountered permutations over F n 2 whose differential equivalence class contains more than 2 2n elements. We conjectured in this paper that functions having a non-trivial DDT-equivalence class may relate to the number of distinct rows in their DDT. Finally, an interesting future direction would be to study the differential equivalence classes, and in particular the sizes, of functions either in higher dimensions and/or without any particular structure.

max a,b∈F n 2

 2 ,a =0 δ F (a, b). The lowest possible value for the differential uniformity of a function from F n 2 into itself is 2 and the functions with differential uniformity 2 are called almost perfect nonlinear (APN). the indicator of the DDT is the Boolean function of 2n variables defined by γ F (a, b) = 0 if and only if δ F (a, b) = 0 or a = 0.

Both12 12 4 .

 4 DDTs are diagonal with 2 × 2 blocks, the first block being 16 G, half of the blocks only are of this shape, the other ones are 4 It is then clear that F and G are γ-equivalent, but are DDT-inequivalent.

6 .

 6 Go back to Step 4 and set F (3) = 6. Compute now any possible values for F (4) by repeating Step 5, with F (3) = 6. 7. . . . 8. Once F (7) has been fixed, we verify that γ F is equal to the indicator of D

  Difference distribution table of dimension 2 3 × 2 3 corresponding to the PRINTcipher Sbox.

	∆out
	0 1 2 3 4 5 6 7
	0 8 . . . . . . .
	1 . 2 . 2 . 2 . 2
	2 . . 2 2 . . 2 2
	∆in 3 . 2 2 . . 2 2 .
	4 . . . . 2 2 2 2
	5 . 2 . 2 2 . 2 .
	6 . . 2 2 2 2 . .
	7 . 2 2 . 2 . . 2
	Figure1:
	4, 7}, F (4) ∈
	{4, 5, 6, 7} ∩ {0, 2, 5, 7} ∩ {0, 1, 6, 7} ∩ {0, 3, 5, 6} = ∅.

Table 1 :

 1 Two non-trivially DDT-equivalent permutations.

		0 1 2 3 4 5 6 7 8 9 10 11 13 12 15 14
	F (x) 0 1 2 3 4 5 6 7 8 9 10 11 13 12 15 14
	x	16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
	F (x) 16 17 19 18 20 21 23 22 25 24 26 27 28 29 31 30
	F (x) 16 17 19 18 21 20 22 23 24 25 27 26 28 29 31 30


Xavier Bonnetain
email: xavier.bonnetain@inria.fr

Quantum Key-Recovery on full AEZ

Keywords: CAESAR competition, symmetric cryptanalysis, quantum cryptanalysis, authenticated encryption, AEZ, Simon's algorithm

AEZ is an authenticated encryption algorithm, submitted to the CAESAR competition. It has been selected for the third round of the competition. While some classical analysis on the algorithm have been published, the cost of these attacks is beyond the security claimed by the designers. In this paper, we show that all the versions of AEZ are completely broken against a quantum adversary. For this, we propose a generalisation of Simon's algorithm for quantum period finding that allows to build efficient attacks.

Introduction

Post-quantum cryptography studies the weaknesses of cryptographic systems against quantum adversaries. The consequences of a quantum computer would be catastrophic in cryptography. Indeed, due to Shor's algorithm [START_REF] Shor | Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[END_REF], most widely used cryptographic primitives would be completely broken. The situation is different in symmetric cryptography. We know since 1996 that Grover's algorithm [START_REF] Grover | A Fast Quantum Mechanical Algorithm for Database Search[END_REF] gives a quadratic speedup on exhaustive search, which lead to the common belief that doubling the key length would be enough to attain a suitable level of security against quantum computers. The work on dedicated cryptanalysis is much more recent, with many results [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF][START_REF] Kuwakado | Security on the quantum-type Even-Mansour cipher[END_REF][START_REF] Anand | Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation[END_REF] showing that we need to study further the implications of quantum computation in symmetric cryptography.

Authenticated encryption aims at providing both secrecy and authenticity. It can be achieved by a classical symmetric primitive in a specific mode of operation (OCB, GCM) [START_REF] Rogaway | OCB: a block-cipher mode of operation for efficient authenticated encryption[END_REF][START_REF] Mcgrew | Galois Counter Mode[END_REF], or with a dedicated primitive. The CAESAR competition, launched in 2014, aims to standardise a portfolio of authenticated encryption algorithms. It has been quite successful in driving the community to work on this subject, with more than 50 submissions, and many cryptanalytic results on these submissions, like for instance [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF][START_REF] Chaigneau | Cryptanalysis of NORX v2.0[END_REF]. AEZ [START_REF] Hoang | Robust Authenticated-Encryption AEZ and the Problem That It Solves[END_REF] is one of these proposals, still in the competition in the 3rd round of the selection process. The candidate AEZ has been tweaked several times to counter some proposed analysis [START_REF] Fuhr | Collision Attacks Against CAESAR Candidates -Forgery and Key-Recovery Against AEZ and Marble[END_REF][START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF]. The current version is AEZ version 5, denoted AEZv5. AEZ claims to be a robust authenticated encryption scheme, being secure even in nonce misuse scenarios. The designers however limited their security claims to 2 44 blocks of data used with the same key. This unusually small limit renders the attacks from [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF][START_REF] Fuhr | Collision Attacks Against CAESAR Candidates -Forgery and Key-Recovery Against AEZ and Marble[END_REF] inapplicable, and their security claims remain unaffected. The published analysis consider only a classical adversary. In this paper, we study the resistance against quantum adversaries.

There has been some previous work on authenticated encryption in a quantum setting, for instance SPHINCS, by Berstein et al. [START_REF] Bernstein | SPHINCS: Practical Stateless Hash-Based Signatures[END_REF]. Kaplan et al. [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF] showed some existential forgeries in OCB, GCM and many CAESAR canditates (including AEZ). Soukharev et al. have proposed a security model for authenticated encryption against quantum adversaries [START_REF] Soukharev | Post-Quantum Security Models for Authenticated Encryption[END_REF], where the challenges are classical, but the adversary can make queries in quantum superposition to an encryption (or decryption, if available) oracle, with a classical chosen randomness. Our attacks performs in this model, where the chosen queries are quantum, except for the nonce, which should be classical (it can be chosen or known, this has no impact on our quantum attacks).

This is a strong model, as the attacker has not only quantum computation capabilities, but can perform quantum queries to an oracle that computes a classical function f : that is, from an arbitrary superposition

∑ |x⟩ |0⟩, get ∑ |x⟩ |f (x)⟩.
It has the advantage of encompassing any other, more constrained, model, and if a primitive is safe in this model, it is safe in the others. Moreover, it may become plausible. We can for example think of white-box cryptography: if you have access to a program that computes a function, you can implement it on a quantum computer. Finally, this model is non-trivial: it is possible to build constructions secure in this model.

In this paper, we show how the key-recovery of [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF] can be dramatically accelerated in a quantum setting to break AEZv4. We also show of to adapt the attack for a key-recovery of AEZv5 and a universal forgery with AEZ10. All these attacks use quantum period finding and have a cost in data of around 2 10 blocks, which is far below the 2 44 limit claimed by the designers.

From a quantum algorithmic's point of view, we propose a more powerful and precise analysis than the one in [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF]. We also show how to take advantage of a quantum multiple period finding, that allows to reduce even more the data complexity in some cases. The results are summarised in table 1.

Preliminaries

In this section, we describe the primitive we're attacking and our main cryptanalytic tool, Simon's algorithm.

Description of AEZ

E i,j K AEZ-hash AEZ-prf AEZ-tiny AEZ-core PRF Encryption Encrypt Fig. 1.
High-level view of the components of AEZ AEZ [START_REF] Hoang | Robust Authenticated-Encryption AEZ and the Problem That It Solves[END_REF] is a tweakable block cipher for authenticated encryption, and its components have been tweaked in the different versions of the algorithm. It uses a master key K of 384 bits, decomposed in 3 subkeys (I,J,L) of 128 bits each. AEZ has at its core a tweakable function E i,j K used in the intermediate function AEZ-hash. The user calls the external function Encrypt, that calls, depending on the message length, AEZ-prf, AEZ-tiny or AEZ-core. AEZ-tiny and AEZ-core are symmetric ciphers, AEZ-tiny is used for messages of less than 32 bytes (one block), AEZ-core is used for longer messages. AEZ-prf is a pseudo-random function (PRF) called when the message is empty that takes some associated data and a length τ in argument, and that outputs a tag of the desired length that can be used to authentify the associated data. Our attacks will use AEZ-prf, and its components are described below. We also need AEZ-core for a part of the attack against AEZ version 4, but as its description is more complex and the attack uses the same principles, we refer to [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF] for a description of AEZ-core.

Associated data. The associated data is seen as a bidimensional vector of 128-bit blocks. An example for 7 blocks can be represented as:

A 1 1 A 1 2 A 1 3 A 2 3 A 3 3 A 1 4 A 2 4 that we note (A 1 1 , A 1 2 , (A 1 3 , A 2 3 , A 3 3 ), (A 1 4 , A 2 4 )).
The associated data can contain any number of lines, and each line can have any length. In practice, we have two constraints. The first line A 1 contains the output length τ of the PRF, in bits. As we'll only have output lengths smaller than 2 128 bits, the first line will only contain one block. The second line contains the nonce N . The specification recommends a nonce smaller than 128 bits, which also limits this line to one block. However, as this is only a recommendation, we can also study what happens if we allow longer nonces.

Finite field. AEZ uses a multiplication in F 2 128 , seen as

F 2 [X]/(X 128 + X 7 + X 2 + X + 1
). As we are in a field, we can invert any non-zero number. Moreover, knowing the polynomial, we can do it efficiently.

Core function. The core of the algorithm is the function E i,j K , which is a permutation on 128 bits. It is concretely a tweaked version of 4 or 10 rounds of AES [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF] (AES4 and AES10). The exact function depends on the version of the algorithm and the values of i and j. These versions of AES don't use the normal key schedule but one of the subkeys (I, J, L) at each round.

Table 2 shows the value of E i,j K in AEZv4, depending on the parameters i and j, with α j = 2 3+⌊(j-1)/8⌋ + ((j -1) mod 8) and β i = 2 i-3 . The multiplication is done in the finite field.

i j E i,j K (X) -1 N AES10(X ⊕ jJ) 0 N AES4(X ⊕ jI) 1 N AES4(X ⊕ αjI) 2 N AES4(X ⊕ αjI) 1 ≥ 3 0 AES4(X ⊕ βiL) ⊕ βiL ≥ 3 ≥ 1 AES4(X ⊕ βiL ⊕ αjJ) ⊕ βiL ⊕ αjJ Table 2. E i,j K in AEZv4
The function is simpler in AEZv5:

-E -1,j K (X) = AES10(X ⊕ jL) -E i,j K (X) = AES4(X ⊕ iJ ⊕ 2 ⌈j/8⌉ I ⊕ (j mod 8)L)
Since version 2, AEZ also proposes an alternative algorithm named AEZ10 where the master key K has 128 bits and is directly used as an AES key,

I = AES K (0), J = AES K (1) and E i,j K = AES K (X ⊕ jI ⊕ iJ).
AEZ-hash. This function takes as input the associated data A and the key K and outputs 128 bits.

A 1 1 = τ E 3,1 K A 1 2 = N E 4,1 K A 1 3 E 5,1 K A 2 3 E 5,2 K . . . A j i E i+2,j K ∆ Fig. 2. AEZ-hash scheme AEZ-hash(K, A) = ∆ = ⊕ i,j E i+2,j K (A j i )
in both v4 and v5.

AEZ-prf. This function is a PRF of arbitrary output length which can be used to authentify the associated data. It takes as input an output length τ , some associated data A and the key K, and outputs τ bits.

It computes ∆ = AEZ-hash(K, A), and outputs the first τ bits of the sequence

E -1,3 K (∆), E -1,3 K (∆ ⊕ 1), E -1,3 K (∆ ⊕ 2)
. . . The most interesting property of this function is that its value (for τ fixed) depends only on the value of AEZ-hash, and in particular, that a collision in AEZ-hash implies a collision in AEZ-prf.

Encrypt. This function takes as input the key K, the associated data A and a variable-length message M . For empty messages, it is a direct call to AEZ-prf(K, A, τ ).

Simon's algorithm

Simon's algorithm [START_REF] Simon | On the power of quantum computation[END_REF] aims at solving the following problem:

Simon's problem. Given a function f : {0, 1} n → {0, 1} n and the promise that there exists s ∈ {0, 1} n such that for all (x, y)

∈ ({0, 1} n ) 2 , f (x) = f (y) ⇔ x ⊕ y ∈ {0, s}, find s.
We say that f has the period s. We have a 2-to-1 function such that for each output, the xor of the 2 preimages is always the same value, and we want to find this value. Classically, we can solve this problem by searching for collisions, in time Ω ( 2 n/2 ) . In our quantum model, where we allow quantum queries to the function, Simon's algorithm solves that problem in O(n) quantum queries and time, using the circuit in figure 3. It also needs a polynomial-time classical post-processing, that we will neglect. We have access to the oracle O f : |x⟩ |y⟩ → |x⟩ |f (x) ⊕ y⟩. We also use the Hadamard transform H ⊗n : |x⟩ → ∑ y (-1) x•y |y⟩, with • the inner product in {0, 1} n , and some measurements.

This circuits has five steps: 2. With the oracle, we get the quantum superposition of all input-outputs through f :

|0⟩ |0⟩ H ⊗n O f (x, y) = (x, y ⊕ f (x)) H ⊗n ∢ → f (x0) ∢ → x
∑ x∈{0,1} n |x⟩ |f (x)⟩
3. We measure the second register. This gives us an f (x 0 ) for an unknown x 0 , and collapses the first register to the compatible preimages, that are, thanks to the promise

|x 0 ⟩ + |x 0 ⊕ s⟩ 4.
We then reapply the Hadamard transform to the first register, which becomes

∑ x∈{0,1} n (-1) x0•x (1 + (-1) x•s ) |x⟩ 5.
We measure that register. Any x such that x • s = 1 has a null amplitude, and we can't measure it. Therefore, we'll measure a random value statisfying x • s = 0.

One application of this circuit gives us a random vector orthogonal to s. We can retrieve the hyperplane orthogonal to s with n -1 independent equations in O(n) queries, and then retrieve s.

Extending Simon's algorithm

In this section, we'll study what happens in the circuit in various interesting situations that occur in the applications we have considered. s is 0 [START_REF] Simon | On the power of quantum computation[END_REF]. The behaviour is slightly different if s = 0 (f is injective): we have only one element at step 3, and we measure a random value at step five, wich means we'll get n independent values in O(n) queries. This case was already treated by Simon in his original paper.

More preimages [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF]. If f fulfils f (x) = f (x ⊕ s) for all x, but can also verify f (x) = f (y) for different values, that is, f can have more than 2 preimages by image, the routine still works and gives us a vector orthogonal to the secret, but we won't get a uniform distribution. This problem has been addressed in [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF], Theorem 1, where they bound the error probability of the algorithm, depending on the probability of occurence of a given parasite period, that is, with

p 0 = max t / ∈{0,s} Pr[f (x) = f (x ⊕ t)],
we get an error probability with cn queries of at most ( 2

( 1 + p 0 2 ) c ) n .
Taking the log in base 2, with p e the error bound, we get

n(1 + c(log(p 0 + 1) -1)) = log(p e ).
We can rewrite it as

cn = 1 log ( 2 p0+1 ) (n -log(p e )).
This allows us to compute directly the needed number of queries for a given success probability. We see that p e diminishes exponentially with the number of queries. For our numerical applications, we can be very conservative for p 0 and take 1/8. As this shows an unwanted differential property, this bound is unlikely to be tight for our applications, which are xors of 4 AES rounds. With such a p 0 , we get cn = 1.2(n -log(p e )). For our numerical applications, we'll consider a p e such that the total success probability of the attack is greater than one half.

Multiple periods [START_REF] Yang | Investigating the linear structure of Boolean functions based on Simon's period-finding quantum algorithm[END_REF]. If f satisfies f (x) = f (x ⊕ s) for multiple values of s, the routine will spawn some vectors orthogonal to all the periods. We will then be able to recover the vector space generated by these periods [START_REF] Yang | Investigating the linear structure of Boolean functions based on Simon's period-finding quantum algorithm[END_REF]. If we have n bits and s independent periods, it is equivalent to Simon's problem with n-s+1 bits (the post-processing is a bit different, as we get a vector space instead of a value). In the most degenerate case, if f is constant, we can only measure 0 (this can also be detected in a few classical queries).

Different functions [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF]. The original problem requires an oracle identical for each query. However, as one query gives one equation, we don't need to have the same oracle call for each query, as long as the hidden periods are the same in all the functions. This will allow us to apply our cryptanalysis with a different nonce at each oracle call. This was used in some of the applications in [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF].

Previous classical attack

Chaigneau and Gilbert presented at FSE'17 a key-recovery attack on AEZv4 [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF]. The attacker can query the functions of AEZ with a fixed unknown key, and chosen authenticated data and plaintexts. The attack is done in two parts: first, they apply 3 independent birthday sub-attacks that retrieve one of the 3 subkeys, and next they perform a diffential attack that retrieves the 2 remaining subkeys once one is known. The first part needs a quantity of data at the birthday bound (2 64 blocks), wich is beyond the security claimed by AEZs designers, who limited the data to 2 44 blocks for a given key. We'll describe here only that part, as it is sufficient to perform efficient quantum attacks. Moreover, the second part doesn't gain much in a quantum setting, and would lead to less efficient attacks.

For each of the 3 attacks, they seek for a collision in a specific function we construct with some functions of AEZ, and such a collision, with a high probability, will give them a subkey if they xor the colliding inputs. The functions are described in table 3. The functions f I and f J need a fixed nonce N for each input, but not f L , as for this function the queried nonce depends on the input value.

subkey function property 3. Collision functions in [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF] For example, for f L , the value of AEZ-hash(K, (τ, x, x)) is

I fI (x) = lastblock(AEZ-core(K, (τ, N ), (0, x, 0, x, 0))) fI (x) = fI (x ⊕ I) J fJ (x) = AEZ-prf(K, (τ, N, (x, x)), τ ) fJ (x) = fJ (x ⊕ J) L fL(x) = AEZ-prf(K, (τ, x, x), τ ) fL(x) = fL(x ⊕ 6L) Table
∆ = E 3,1 K (τ ) ⊕ E 4,1 K (x) ⊕ E 5,1 K (x)
, which gives us, when we expand:

∆ = E 3,1 K (τ ) ⊕ AES4(x ⊕ 2L ⊕ 8J) ⊕ AES4(x ⊕ 4L ⊕ 8J).
For x ′ = x ⊕ 6L, we get

∆ = E 3,1 K (τ ) ⊕ AES4(x ⊕ 6L ⊕ 2L ⊕ 8J) ⊕ AES4(x ⊕ 6L ⊕ 4L ⊕ 8J).
As we are in F 2 128 , it reduces to

∆ = E 3,1 K (τ ) ⊕ AES4(x ⊕ 4L ⊕ 8J) ⊕ AES4(x ⊕ 2L ⊕ 8J).
Hence, we get the same ∆ (which implies the same value of

f L (x)) if x ⊕ x ′ = 6L, that is, f L (x) = f L (x ⊕ 6L).
We have similar properties for f J and f I :

f J (x) = f J (x ⊕ J) and f I (x) = f I (x ⊕ I).
Then, for f L (and similarly for f I and f J ), the attack is:

-Query f L (x) for 2 64 different values of x. -Search for a collision f L (x) = f L (x ′ )
We'll see how to use these properties to dramatically accelerate this attack in a quantum setting in the next section.

Quantum cryptanalysis of AEZ

In this section, we'll show how to use Simon's algorithm to efficiently recover the subkeys in AEZv4, AEZv5 and AEZ10. We've chosen to restrain ourselves to a classical known nonce for each quantum query.

All these attacks make use of a function f , of the form

f (x) = a ⊕ g(x ⊕ b) ⊕ g(x ⊕ b ⊕ s),
with g a xor of AES4 with various inputs. Simon's algorithm will retrieve efficiently s, except if s = 0. In this case, f is a constant function, and the corresponding key is weak, as such a property can easily be detected classically. However, the proportion of such weak keys, which corresponds to the subkeys I, J, L (or some multiples of the subkeys) being linearly dependent, is too small to be exploited (this occurs with a probability of around 2 -125 for one f ).

AEZv4

We can directly use the functions of [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF], described in table 3, in Simon's algorithm. There is however a slight difference for f I , as the period is not on the full AEZ-core but only on the last block. We can construct an oracle of f I from an oracle of AEZ-core by uncomputing and taking only the last block. With this method, one query to f I costs two queries to AEZ-core. For each case, we query functions of n = 128 bits. In order to get a success probability of 0.5, we need 80% of success for each subkey, which is attained in 157 queries. The total query complexity of the attack is 628 = 2 9.3 . We use respectively 2, 3 and 2 × 6 block of data for each query. We need 2669 = 2 11.4 ≪ 2 44 blocks of data.

The complete attack is:

-For k ∈ {I, J, L}:

• Query 157 times Simon's routine with f k .

• Solve classically the boolean equation system to get the period of f k .

• If this period was a multiple of k, invert to retrieve k.

In the original attack, f I and f J needed a nonce reuse. This is not the case with the quantum attack, as the different functions have the same hidden period. The only constraint for the nonce is to be non-entangled with the input value. For f L , we need to perform a quantum query with a nonce superposition. If we want to disallow this, we can still use

f ′ L = AEZ-prf(K, (τ, N, x, x), τ ), which satisfies f ′ L (x) = f ′ L (x⊕12L
). This has the same query complexity, but a slightly larger data complexity (2 11.5 ).

But we can go even further, if we look at f JL (x) = AEZ-prf(K, (τ, N, (x, x), (x, x)), τ ).

The associated ∆ is

A⊕AES4(x⊕4L⊕8J)⊕AES4(x⊕4L⊕9J)⊕AES4(x⊕8L⊕8J)⊕AES4(x⊕8L⊕9J).
This function has a hidden period of J and 12L (and also J ⊕ 12L). As seen in section 3, this means we can retrieve the vector space ⟨J, 12L⟩ with this function. J and 12L need to be independent for the function to be non-constant. In that case, we can retrieve the value of J and L with an exhaustive (classical) research, as it has only 6 possibilities (for example by checking for collisions in f J and f L ). This diminishes even more the query complexity to 471 = 2 8.9 , using the same number of block of quantum data. We then need to identify J and L. We can do an exhaustive search, in one classical query and 6 tests (we only need to test pairs of linearly independent vectors of the subspace we retrieved), or check for collisions, in 6 classical queries (one for a reference, 3 to try to collide with the reference on the first subkey, 2 to try to collide on the second).

We can also use these multiple periods in the classical attack: we use f JL for our collisions, but as one query of this function has the same data complexity as the queries of f J and f L , it won't change much on the overall complexity. 4. Collision functions for AEZv5

AEZv5

The functions in table 4 allow to perform the same attack on AEZv5, with a quantum query complexity of 2 8.9 , and a data complexity of 2464 = 2 11.3 blocks.

We can even be more efficient in queries and recover the vector space ⟨6I, 3J, 3L⟩ in one go, with the function

f IJL (x) = AEZ-prf(K, (τ, N, (x, x, A, B, C, D, E, F, x, x), (x, x, A ′ , B ′ , C ′ , D ′ , E ′ , F ′ , x, x) ), τ ).
Here, any non-x value in argument can be anything as long as it is not entangled with x. This f has the 3 periods of f I , f J and f L , and allows us to recover the vector space in 155 = 2 7.3 queries, and a data complexity of 3255 = 2 11.7 blocks. Once we know the vector space, we can use one classical query and check the 7 × 6 × 4 = 168 possible triplets, or check for collisions in the classical version of f I , f J and f K , which can be done in 1 + 7 + 6 + 4 = 18 classical queries.

Using the same principle, we can also define and use f IJ , f JL or f IL , which all have comparable complexities, (τ,N,(x,x,B,C,D,E,F,G,x,x),τ ) and f J (x) giving the best data complexity of 2 11.1 blocks.

f IL (x) = AEZ-prf(K,

AEZ10

The core function is even simpler in this variant: E i,j K (X) = AES(X ⊕ iJ ⊕ jI). Hence, we can do the attack with the functions in table 5. With two functions, subkey function period

I fI (x) = AEZ-prf(K, (τ, N, (x, x)), τ ) 3I J fJ (x) = AEZ-prf(K, (τ, N, x, x), τ ) 3J I, J fIJ (x) = AEZ-prf(K, (τ, N, (x, x), (x, x)), τ ) 3I, 3J, 3I ⊕ 3J
Table 5. Collision functions for AEZ10

we can recover I and J in 312 quantum queries and 936 quantum blocks of data.

If we choose to get the vector space spawned by I and J, we only need 155 queries and 775 blocks of data. In this case, we don't get a full key recovery, but the knowledge of the tweaks I and J allows to make forgeries for any non-empty authenticated data.

Variants of the attack

We can gain one block per query if we allow the nonce to be in quantum superposition and if the nonce can be more than 128 bits (which is not recommended, but isn't forbidden by the specification). Indeed, this would allow to suppress the nonce line in the associated data in each of the queried functions. The new functions would have a hidden period for some other multiples of the subkeys. The attack from Chaigneau and Gilbert [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF] can also be applied to all the versions we have considered here classically, and the cost will be at the birthday bound (2 64 queries, for around 2 66 blocks of data, depending on the amount of associated data in the functions). If we want to gain in data complexity, we can reuse the second part of the attack in [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF]. Once the subkey I is known, we can get J and L by attacking 3 rounds of AES (we can probably also make use of the knowledge of J or L, but this would need another dedicated analysis).

Thwarting the attack

There are different ways to counter this specific attack. As Simon's algorithm uses a specific structure, the simplest solution would be to change the way offsets are used, from a xor with the data to another operation (see [START_REF] Alagic | Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts[END_REF]). However, if this is still a commutative group operation, the algorithm would be vulnerable to some other quantum algorithms like Kuperberg's algorithm [START_REF] Kuperberg | A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF], and it may not lead to a satisfactory level of security.

A more conservative approach would be to change a bit the way the associated data is processed. We can currently see it as 4 rounds of an AES with a custom key schedule, with the first round key that depends on the position of the block, the other ones being fixed. If the variable key is one of the inner AES keys (or if there are variable keys on multiple rounds), this quantum attack would not work. This could however lead to some kind of related-key attacks on this 4round AES, and it would require a dedicated analysis to ensure it does not lead to some other classical attacks.

Moreover, these changes would prevent the quantum exponential gain of Simon's algorithm, but the collision analysis from Chaigneau and Gilbert [START_REF] Chaigneau | Is AEZ v4.1 Sufficiently Resilient Against Key-Recovery Attacks?[END_REF] would remain.

Conclusion

We've shown that all the versions of AEZ are deeply broken in the quantum superposition model. This is an example of an exponential speedup of a classical attack on a real primitive, that went from costly to almost-free. We've also presented a way to exploit multiple hidden periods in order to reduce the number of quantum oracle calls, and provide more flexibility in the attack, and discussed how to avoid these kinds of attacks.

Fig. 3 .

 3 Fig. 3. Simon's algorithm quantum circuit

  ) = AEZ-prf(K, (τ, N, (x, A, B, C, D, E, F, G, x), τ ) 6I J fJ (x) = AEZ-prf(K, (τ, N, x, x), τ ) 3J L fL(x) = AEZ-prf(K, (τ, N, (x, x)), τ ) 3L Table

Table 1 .

 1 Summary of the attacks on AEZ since version 3

	Version	Data, time, memory complexity (blocks)	model	Type	Ref
	AEZv3	2 66.6	Classical	Key Recovery	[8]
	AEZv4	2 66.5	Classical	Key recovery	[6]
	AEZv4	2 10	Classical	Existential forgery	[4]
	All	≃ 2 9	Quantum query Existential forgery	[11]
	AEZv4	2 11.4	Quantum query	Key recovery	Section 5.1
	AEZv5	2 11.1	Quantum query	Key recovery	Section 5.2
	AEZ10	2 9.6	Quantum query Universal forgery Section 5.3
			2

This AES doesn't uses the same keys as the others.

Acknowledgements

The author would like to thank Colin Chaigneau and Henri Gilbert for helpful discussions on AEZ, and María Naya-Plasencia and André Schrottenloher for their detailed comments on the early versions of this paper.