Xavier Bonnetain

María Naya-Plasencia

Hidden Shift Quantum Cryptanalysis and Implications

Keywords: quantum cryptanalysis, hidden shift problem, Simon-meets-Kuperberg, Poly1305, symmetric cryptography, modular additions

At Eurocrypt 2017 a tweak to counter Simon's quantum attack was proposed: replace the common bitwise addition, with other operations, as a modular addition. The starting point of our paper is a follow up of these previous results: First, we have developed new algorithms that improve and generalize Kuperberg's algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005, largely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.

We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes. We also propose a generic algorithm to solve the hidden shift problem in non-abelian groups.

In order to verify the theoretical analysis we performed, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.

Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak, concluding that it does not seem to be efficient.

Introduction

As years go by, the existence of quantum computers becomes more tangible and the scientific community is already anticipating the consequences of the induced breakthrough in computational power. Cryptology is one of the affected disciplines. Indeed, the current state-of-the-art asymmetric primitives would become insecure, and the NIST has launched a competition for finding new primitives.

Symmetric cryptography, essential for enabling secure communications, seemed much less affected at first sight: for a long time, the greatest known threat was Grover's algorithm, which allows exhaustive key searches in the square root of The attack model. These last mentioned attacks apply in a scenario of superposition quantum queries. It means that the adversary is not only allowed to perform local computations on a quantum computer 3 , but is also allowed to perform superposition queries to a remote quantum cryptographic oracle, to obtain the superposition of the outputs. These attacks have been described as superposition attacks [START_REF] Damgård | Superposition Attacks on Cryptographic Protocols[END_REF], quantum chosen message attacks [START_REF] Boneh | Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World[END_REF] or quantum security [START_REF] Zhandry | How to Construct Quantum Random Functions[END_REF].

This is a strong model for the attacker, but there are very good arguments for defending the interest of studying the security of symmetric primitives in this setting (see for instance [START_REF] Gagliardoni | Semantic Security and Indistinguishability in the Quantum World[END_REF] or [START_REF] Gagliardoni | Quantum Security of Cryptographic Primitives[END_REF] for more detailed justifications of the model):

1. This model is simple. Using another model would imply artificial and hard to respect measures with respect to cryptographic oracles in a world with quantum resources, with complex manipulations of yet uncertain outcome 4 . 2. Safety in this model implies safety in any other scenario, even advanced ones (e.g. obfuscated algorithms).

applications in symmetric cryptography. 5 We focus on the groups Z/(2 n ), which are vastly used in symmetric cryptography. The original algorithm retrieves one bit of the secret shift at a time and uses a reducibility property to get the next bit. We propose a variant that performs better by getting all the bits in one step, allowing a drastic cost reduction of the attack on Poly1305. We also propose a way of solving the hidden shift problem in non-abelian groups.

2. Simon Meets Kuperberg. We propose a new quantum algorithm that considers a generalization for products of cyclic groups (Z/(2 p ) w and its subgroups), commonly used in symmetric primitives. The problem is more easily solvable in these groups than in Z/(2 wp ). Our complexity analysis shows how it meets Simon (w = 1) and Kuperberg (p = 1) in each extreme.

3. Simulation of the algorithms. We have implemented the classical part of these algorithms (Kuperberg, improved Kuperberg and Simon-meets-Kuperberg) and simulated it in order to estimate the asymptotic query complexity, and to get values for parameters of interest, verifying the expected complexities. Our code is available as additional material A and will be made publicly available.

4. Attack on Poly1305 in the superposition model. We propose a quantum attack on Poly1305 [START_REF] Bernstein | The Poly1305-AES Message-Authentication Code[END_REF], a MAC that has been standardized for TLS 1.2 [START_REF] Langley | chacha20-poly1305 cipher suites for transport layer security (tls)[END_REF] and 1. 3 [1], and is notably used by OpenSSH, Firefox and Chrome. In [START_REF] Daniel | Post-quantum cryptography[END_REF] a classical and quantum security of 128 bits is claimed for Poly1305: "'Informationtheoretic' MACs such as GMAC and Poly1305 already protect against quantum computers without any modifications: their security analysis already assumes an attacker with unlimited computing power." Our attack, that works in the superposition model, has a complexity of 2 38 and uses our improved Kuperberg's algorithm. It recovers half of the 234-bit key, allowing some forgeries. The attack is not a direct application of the algorithm and requires some additional techniques.

Attack on the FX variants.

We answer an open question asked in [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FXconstruction[END_REF], assessing the quantum security of the FX construction with any group law. If the inner key addition is done with a commutative group law, the security gain of the construct is marginal, and the best we can hope to achieve with a non-abelian group is a gain of around n/3 bits of security for an n-bit inner key.

6. Evaluate the proposed countermeasures from [2]. The final aim was to determine how to size the symmetric primitives in order to offer a certain desired security, and to decide whether the proposed countermeasure was sufficient, and efficient enough in practice. Using modular additions in vulnerable constructions instead of xors for key addition increases the complexity of the corresponding quantum key-recovery attack, but we show that the proposal from [2]does not seem practical, and would require an internal state size of a few thousand bits, to be compared with the size of the internal state of AES-256, which is 128 bits.

Organization of the paper. Section 2 introduces some preliminary material. Section 3 presents our study on Kuperberg's algorithm and our improvement, several generalizations, our simulations and the inferred complexities. Section 4 describes our new quantum algorithm for parallel additions. Section 5 presents the first quantum attack on Poly1305 in the superposition model, using Kuperberg's algorithm. Section 6 estimates the strength of the FX construct with new group laws. Section 7 applies our previous results to actual symmetric primitives, deducing the key or internal state size that must be used in those constructs to offer a desired quantum security. The paper ends with a conclusion in Section 8.

Preliminaries

In this section, we present the quantum symmetric attacks from [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF] and [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FXconstruction[END_REF], the proposed solution from [2] and our cost model.

2.1 Quantum attacks using Simon's algorithm from [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF] In [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF] Simon's quantum algorithm was applied to cryptanalyse several widely used modes of operation and CAESAR candidates. This was possible due to the exponential speedup of Simon's algorithm, that solves the following problem:

Let f : {0, 1} n → {0, 1} n . Given the promise that there exists s ∈ {0, 1} n such that for any

(x, y) ∈ {0, 1} n , [f (x) = f (y)] ⇔ [x ⊕ y ∈ {0 n , s}], find s.
The authors applied Simon's algorithm to find a secret information in time linear in the block size (O(n) instead of O(2 n/2 ) classically). One implication of the problem was not verified in the attacks: with a small probability, we might have f (x) = f (y) and x ⊕ y / ∈ {0 n , s}. However, they showed that the algorithm is still efficient with a random function in place of a random permutation.

Solution proposed in [2]

In [2], the authors propose to change, in the primitives broken by [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF], the group law, to prevent the use of Simon's algorithm. They also propose a security reduction from the primitives to the corresponding hidden shift problem, and claim that they are safe, as no polynomial algorithm for these problems is known. They notably propose (Z/(2 n ), +) (for which Kuperberg's algorithm is, in a sense, not a threat, as it is superpolynomial), or the symmetric group S n .

Cryptanalysis of the FX construct [35]

The FX construct [START_REF] Kilian | How to Protect DES Against Exhaustive Key Search[END_REF] uses a block cipher E k and two additional keys k 1 , k 2 , and is defined as FX k0,k1,k2 (x) = E k0 (x ⊕ k 1 ) ⊕ k 2 . It can be broken by combining Simon's and Grover's algorithms : one can perform an exhaustive search on k 0 and then see the FX construct as an Even-Mansour with the public permutation E k0 , which can be broken with Simon's algorithm. The authors left as an open problem the case where the whitening keys were added with modular addition.

Cost Model

We're interested in the explicit costs of the algorithms we study. These algorithm have all a similar shape: they use a generation circuit that produces some relevant qubits, a combination circuit that uses the produced qubits, and a control circuit have chooses which qubits are to be combined. The generation circuit is a Quantum Fourier Transform applied to an oracle, whose total cost in time and memory is the number of queries. The combination circuit has a fixed cost, and can only be used once per query. The control circuit can be more complex, but only have to reason about classical values, and hence can be implemented purely classically, and its cost in time and memory will be the cost in query, with a polynomial overhead. As we expect that a classical computer will be far more efficient than a quantum computer to apply the same number of gates, we estimated that the bottleneck of our algorithm will be the quantum part of it, and that the relevant cost unit here is the number of queries.

New Results on Kuperberg's Algorithm

In this section, we study Kuperberg's quantum algorithm for solving the hidden shift problem. While the final aim is to be able to accurately estimate the complexities of the cryptanalysis on primitives whose security rely on the hidden shift problem, we have also performed a more profound work that verifies and helps better understanding Kuperberg's algorithm and its performance. We propose a new variant of the algorithm that reduces its cost, and that will allow to build the performant attack from section 5. We've implemented the classical part of these algorithms and made some simulations in order to get concrete estimates of the asymptotic complexity and values for parameters of interest, that match and refine the theoretical expectations. We finally propose a generalization of the algorithm for the case of non-abelian groups.

Hidden Shift Problem and Quantum Algorithms

The hidden shift problem (HSP) is defined as follows:

Let f , g two injective functions, (G, •) a group. Given the promise that there exists s ∈ G such that, for all x, f (x) = g(x • s), retrieve s.

We say that f is a shifted version of g, the shift being s. To estimate the complexity, we consider n = log 2 |G|. The hardness of the problem depends vastly on the group law. If it is a bitwise xor, Simon's algorithm [START_REF] Simon | On the Power of Quantum Cryptography[END_REF] solves it in polynomial time. If the group law is a modular addition, it can be solved with a linear number of queries [START_REF] Ettinger | On Quantum Algorithms for Noncommutative Hidden Subgroups[END_REF], but this method requires an exponentialtime classical post-processing, and as such, won't be interesting for us. The firsts sub-exponential (in quantum query and quantum and classical time) algorithms are presented in [START_REF] Kuperberg | A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF]. They have a time and space complexity in 2 O( √ n) for a group of size 2 n . Other variants were developed later, with an algorithm with quantum polynomial space, but slightly worse time complexity, in 2 O( √ n log(n)) [START_REF] Regev | A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space[END_REF], and some algorithms in [START_REF] Kuperberg | Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF], that generalize the previous one, allowing some trade-offs between classical and quantum memory and time.

From this point, we focus on additions modulo a power of 2, as they are very common in symmetric cryptography, due to implementation reasons. Single modular addition. All these algorithms are in two parts: an oracle that calls f and g to produce some qubits and a combination circuit that transforms them into more interesting ones. The combination part uses the quantum oracle

O : |b |x |y → |0 |x |y ⊕ f (x) if b = 0 |1 |x |y ⊕ g(x) if b = 1 .
Generation. The oracle circuit (Figure 1a) produces the uniform superposition in the registers b and x with Hadamard gates (H), feeds them to the oracle (O), and then measures register y. This measurement gives a result y 0 and collapses the b and x registers in the state f (x)=y0 |0 |x + g(x)=y0 |1 |x , which is, thanks to the promise, the state |0 |x 0 + |1 |x 0 + s for a given (unknown) x 0 . We then apply a quantum Fourier transform (QFT) on the x register and measure the result. This gives us an with a uniform probability, and collapses the remaining qubit in the state |ψ = |0 + exp 2ιπ s 2 n |1 . This qubit depends on s, but is not directly exploitable. The qubit |ψ 2 n-1 = |0 + exp (ιπs) |1 is very interesting, as it is |+ if the lowest bit of s is 0, and else is |-. Hence, if me measure it in the {|-, |+ } basis, we get one bit of s. Combination. We have then a combination part, that uses the produced qubits to generate some more interesting ones. The combination is done with the circuit in Figure 1b, that consists of one controlled-not and a measurement of the second register. By doing so, we destroy two elements in order to produce one. Before the measurement, the system is in the state CNOT |ψ

1 |ψ 2 = |00 + exp 2ιπ s( 1 + 2) 2 n |10 + exp 2ιπ s 2 2 n |01 + exp 2ιπ s( 1 -2) 2 n |11
If we measure a 0 we'll get the qubit |ψ 1 + 2 , and if we measure a 1 we'll get |ψ 1-2 . Both outcomes are equiprobable. If we only see the s and not the qubits, we can produce random numbers and combine them 2 by 2 using an operation, + or -, that we discover afterwards. All the numbers can be used once, and we want to obtain 2 n-1 . This abstract problem would be a problem of subset-sum modulo 2 n if the operation at each step was fixed, and not picked randomly in {+, -}, as we would want to find a tuple satisfying

i∈I i = 2 n-1 mod 2 n .
However, in our situation, the problem is closer to finding a tuple satisfying

i∈I δi i = 2 n-1 mod 2 n ,
with δ i ∈ {-1, 1} unknown before the actual destructive computation.

With these quantum tools, we can produce random elements and combine them, but we need an algorithm to choose which elements to combine.

Choosing the elements to combine. As a combination produces either a + b or a -b, we need to find a property preserved in both cases, to not lose everything if the wrong outcome occurs. It turns out divisibility by 2 is such a property: if both a and b are multiples of 2 k , a + b and a -b will also be multiples of 2 k . Hence comes naturally the idea of the combination algorithm: from the elements we have, generate elements with a higher divisibility by 2, until we get 2 n-1 . To achieve this, we can combine elements such that a + b or a -b has a high divisibility by 2 (e.g. have a long trail of 0 in their binary representation).

Hence, an algorithm to find 2 n-1 is then, beginning with the odd numbers, to combine the two elements that can produce a number with the highest possible divisibility by 2. As this property corresponds to the longest partial collision in the binary representation of the elements, they can be efficiently found with a radix tree. There is however one caveat: we don't want the useless 0 element, so we try to not combine two identical elements, or one element and its opposite.

As the interesting a and b collide on their lowest bits, they have the same divisibility by 2, that is, a = 2 k (2a + 1) and b = 2 k (2b + 1). Then, a + b = 2 k+1 (a + b + 1) and a -b = 2 k+1 (a -b). This means that even in the bad case (with a small divisibility by 2), we still get a slightly better divisibility by 2. Then, the algorithm consists in using this heuristic until we get 2 n-1 . This is Algorithm 1, from [START_REF] Kuperberg | A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF]. The paper also presents a sketch of proof that its complexity is in O 2 √ Algorithm 1 Kuperberg's original algorithm [START_REF] Kuperberg | A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF] If this succeeds, we get the value of the lowest significant bit of the hidden shift, s 0 . We have then to retrieve the other bits of s. This can be done using a recursive procedure: with the knowledge of s mod 2 = s 0 , we can construct the functions f (x) = f (2x) and g (x) = g(2x + s 0 ), that have the hidden shift s = (s -s 0 )/2 in Z/(2 n-1 ). The 2nd bit of s is the lowest bit of s , and we can reapply the routine, and so on until we get all the bits.

New variant with improved the time complexity

In this section we propose an optimization of the previous algorithm that allows to perform the attack in Section 5. Previously each bit of the shift were retrieved independently. We have noticed that the remaining qubits of each step can be reused. The phase of the element is 2π s

2 n = 2π (s0+2s ) 2 n = 2π s 2 n-1 + 2π s0 2 n .
If s 0 = 0, we can reuse them directly as elements of Z/(2 n-1 ) for the next step (we just have to see the them modulo 2 n-1 , that is, drop the most significant bit).

If it is 1, we have an additional phase of 2π 2 n that prevents us to do so. We can get rid of it by applying a phase shift gate of angle -2π 2 n before reusing it. We can use that to reuse all our remaining qubits. Moreover, in the 2nd phase, the interesting elements are 010...0 and 110...0, that is, any element of the penultimate pool. Likewise, we can use an element in a pool to retrieve one bit of the shift if we know all the preceding bits. We may get one less combination by pool, but as it will be the last one, it would have been the least interesting one. This strategy leads to the improved Algorithm 2, where we ensure that each pool stays non-empty. If we miss one qubit, won't have the value of the corresponding bit of s, and, as we won't know which rotations to do, on the following bits of s.

This variant is still subexponential, but due to the fact that we do only one pass instead of n, we have a polynomial gain, and we can estimate its complexity, using the same arguments as for Algorithm 1, as O n2

Approximated promise

In concrete attacks, we may want to use this algorithm on functions that respect partially the promise. We study in this section various cases.

Lemma 1 (Unwanted collisions). Let f : Z/(2 n ) → Z/(2 n ) a random func- tion , s ∈ Z/(2 n ).
We can retrieve s in Q quantum queries if we can solve the hidden shift problem in Z/(2 n ) with a permutation using Q/e quantum queries Proof. This case was studied in section 2.2 of [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF] in the context of Simon's algorithm. It corresponds to the hidden subgroup problem with a non-injective function. It then still respect for all x, f (x) = g(x + s) for a secret s.

Let's decompose each step. The measurement after the oracle produces

|0 c i=1 |xi + |1 c i=1
|xi + s and measured f (x i ) with probability c/2 n . After the QFT, the measurement will give us a label and a qubit

c i=1 exp 2ιπ xi 2 n |0 + exp 2ιπ s 2 n |1
As a qubit is invariant by a global phase shift, we still get a valid element. However, it is not uniformly sampled, and the probability of getting a given is

p = 1 c2 n c i=1 exp 2ιπ xi 2 n 2 .
Notably, the case = 0, which is useless for us, is the most probable. It is known [START_REF] Flajolet | Random Mapping Statistics[END_REF] that for a random function, the expected number of images with r preimages is 2 n / (er!). The first measurement samples on the images, uniformly if it is a bijection, and proportionally to the number of preimages in the general case. That means we'll have a probability of r/(er!) = 1/(e(r -1)!) of getting an image with r preimages. We'll get a unique preimage with probability 1/e, so that means with e times the number of samples, we'll get enough elements with only one preimage. This is a very rough approximation, as the multiple preimages induces only a bias on the generated elements.

Remark 1. Alternatively, we can consider the function F (x) = (f (x), f (x + 1), . . . ), that has the same shifts as f , but has a smaller probability of unwanted collisions, at the cost of having to query f multiple time for one query of F .

Lemma 2 (Multiple shifts). Let (s i ) i≤t ∈ Z/(2 n ) t , let f, g two permutations of Z/(2 n ) such that, for all x, i, f (x) = g(x + s i ).
The first bits of the s i can be retrieved if and only if they are all equal. They can be retrieved by solving the HSP in Z/(2 k ) with the same functions, with

2 k = gcd i =j (2 n , s i -s j ).
Proof. We can study what happens with two shifts:

x, f (x) = g(x+s) = g(x+t).
From these equalities, we can deduce that for all x and λ, f

(x) = f (x + λ(s - t)) = g(x + s + λ(s -t))
. The functions have in fact plenty of shifts: s + λ(s -t), the exact number depending on the divisibility by 2 of s -t. The bits of x that are above this level have in fact no impact on the value of f , so this problem is degenerate: if s -t = 2 k µ, we have an instance of the problem in Z/(2 k ), with a hidden shift s = s mod 2 k = t mod 2 k , and we have 2 k = gcd(2 n , s -t). We cannot get the other bits of s or t, as all the s + λ(s -t) are also valid shifts.

For more shifts, we need to consider the difference that have the smallest divisibility by two, that is, the gcd of all the differences with 2 n .

As the divisibility by two of the difference corresponds to an equality in the first bits, the lemma holds.

Remark 2. If we don't know that the functions have multiple shifts, or if the gcd is not known in advance, this is still detectable, as the labels we measure will always divide 2 n-k .

Proof. The formula of the probability of measuring is p(

) = 1 c2 n c i=1 exp 2ιπ xi 2 n
2 with c shifts. This reduces to

1 c2 n exp 2ιπ x 2 n λ exp 2ιπ λ2 k 2 n 2 . This is 0 if exp 2ιπ 2 k 2 n = 1, that is, if 2 n-k
. This means we'll only get some s with at least n -k trailing zeros.

Lemma 3 (Partial shift). Let f , g two permutations of Z/(N ), s ∈ Z/(N ), X ⊂ Z/(N ) such that, for all x ∈ X, f (x) = g(x + s).
Then if the hidden subgroup problem in Z/(N ) costs Q queries, we can retrieve s given quantum oracle access to f and g in Q queries, with probability (|X|/N ) Q .

Proof. If we measure an f (x) whose x is in X, then we have a valid element. This happens with probability |X|/N . If this is not the case, we get a malformed qubit. We can expect the algorithm to succeed only if all the Q queried elements are valid, which happens with probability (|X|/N ) Q . Remark 3. It would also be possible for the algorithm to succeed if we have a way to identify the bad x from the value f (x)/g(x), which is measured, as it would allow us to drop the corrupted qubit when we create it. The problem would then only concern the unidentified bad x.

Lemma 4 (Input restriction). Let f, g be two permutations of Z/(N ), s ∈ Z/(N ) such that, for all x, f (x) = g(x + s). Given a quantum oracle access to f and g restricted to the inputs 0 ≤ x < 2 n , if 0 ≤ s < 2 n-1 and the hidden subgroup problem in Z/(2 n-1 ) can be solved in Q queries, s can be retrieved in eQ 2 queries.

Proof. We are only given access to the interval [0; 2 n ). We cannot see the hidden shift in Z/(N ) as a hidden shift in Z/(2 n ). However, if s is small enough, we have an instance of a partial hidden shift, the valid elements being the ones such that 0 ≤ x < 2 n and 0 ≤ x + s < 2 n . The probability to get a bad element is less than s/2 n in this case. If we need Q queries, and s/2 n 1/Q, then the success probability will be greater than (1 -1/Q) Q 1/e. This fails for greater s.

However, we can query a subinterval of [0; 2 n ) for f and g. For A ∈ [0; 2 n-1 ), if we query [0; 2 n-1 ) to f (x + A) and g(x), we will retrieve s with probability

1/e if 0 ≤ s -A < 2 n-1 /Q , if we need Q queries to solve the hidden subgroup problem in Z/(2 n-1 ).
To retrieve s, we can sequentially test for all A multiples of 2 n-1 /Q , until we reach 2 n-1 . We then have Q intervals to test, and each test costs Q queries. Moreover, the algorithm will succeed if the test with the right guess of A succeeds, and can be verified with a few classical queries. As the right guess has a success probability greater than 1/e, we expect to find the shift in eQ 2 queries. Remark 4. Here, we do a sequential test of the intervals. We could do a Grover search on it instead, but we would need to choose a slightly higher number of queries, in order to have a success probability very close to one. Moreover, it would force us to implement all the control system that chooses which qubit to collide quantumly and not classically.

Remark 5. We can see this method as trying to solve the HSP in Z. It also shows that considering only the cyclic groups Z/(2 n ) allows to solve the problem in any cyclic group in subexponential time, despite a different group structure.

Simulations

We have simulated the classical part of the algorithm by replacing the quantum measurements by random outcomes. We used this to get an estimate of the query complexity: We generate a certain amount of random numbers, and then combine them in order to get the values we want. We hence get an estimate of the success probability for a given amount of samples (Figure 2), and deduce from it an asymptotic complexity for a constant success probability. Table 1 shows some results of these simulations for different values of n, for 90% success probability. The code of this implementation is available as additional material. Figure 2 shows the estimated probability of retrieving the whole secret in function of the number of initial queries for a 64-bit secret. We've considered this parameter instead of some finer ones, such as the numbers of bits we retrieved because of the dependency between the bits we can retrieve: we have to retrieve them in order, and the first ones are the hardest to get. We can try to guess the missing bits, but as we destroy our qubits when we measure them, we can't recover from a wrong guess. It shows a transition from a negligible probability of success to a negligible probability of failure in less than a factor 2. As the algorithm is collision-based, it performs significantly better if it is run once with a bigger initial pool than many times with smaller pools. It also shows that the gap to get an arbitrarily small failure probability is small, which is useful if we want to combine it with another quantum algorithm, like a Grover search. We can then deduce an approximate complexity in query of 0.7 × 2 1.8

√ n for a 90% success probability for Algorithm 2, which matches the exponent complexity of O 2 √ 2 log 2 (3)n of the less efficient Algorithm 1, as 2 log 2 (3) 1.8. We see that the polynomial part is in fact a constant next to 1 for Algorithm 2, which hints that the bound in [START_REF] Kuperberg | A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF] for Algorithm 1, O n2 √ 2 log 2 (3)n to retrieve the last bit, is probably tight for the exponent part, but not for the polynomial part.

Hidden Shift in Non-Abelian Groups

In this section, we study the hardness of the HSP in other groups that can replace the xor (if we ignore the cardinality problem, as their size is not a power of 2), that is, GL 2 (q) (the group of invertible matrix of size 2 × 2 in F q and S n , the symmetric group on n elements (which was proposed as an alternative to

Z/(2 n ) in [2]
), and propose a generic algorithm that can be used to assess the security provided by any group. Kuperberg's Algorithm solves the Hidden Shift Problem for cyclic groups, and a natural extension can be applied to products of cyclic groups (We've only considered powers of 2 here, but variants exists for all moduli). With the fundamental theorem of finite abelian groups, this means that variants of Kuperberg's algorithm can be used for all abelian groups. Moreover, as the exponent of the complexity for Z/(N ) seems to be in all cases at most 2 log 2 (3) log 2 (N ), and as a product of cyclic groups tends to reduce the complexity (see Section 4), we can estimate that the algorithm would cost at most 2 √ 2 log 2 (3)n for an abelian group of size around 2 n (this would need a deeper investigation, but it gives a comparison point for a first estimate).

Generic non-abelian hidden shift. The hidden shift problem is a special case of a collision-finding problem. As such, it can be solved classically in 2 n/2 queries. This classical cost matches the cost of an exhaustive shift search with Grover's algorithm. This is however not optimal, as collisions can be found more efficiently with a quantum computer, in 2 n/3 queries [START_REF] Brassard | Quantum Algorithm for the Collision Problem[END_REF]. If we also consider time, the gain is smaller, but the 2 n/2 cost of Grover's algorithm can still be beaten [START_REF] Chailloux | An efficient quantum collision search algorithm and implications on symmetric cryptography[END_REF]. This has two important implications for non-abelian groups. First, it suggests that for a fixed size, a cipher based on a hidden shift problem cannot match the best we can expect from a symmetric cipher. Second, it means we need to beat the cost of 2 n/3 in order to have an interesting hidden shift algorithm.

Non-abelian hidden shift algorithm This algorithm can't be used with nonabelian groups. However, these groups contains some abelian subgroups (as the iterated powers of an element). We can apply the algorithm on such a subgroup, and it will succeed if the hidden shift lies in this subgroup. The idea is then to look for this situation. It can be done by considering the right cosets of the abelian subgroup A. Indeed, all group elements can be uniquely written as ar, with a ∈ A and r a fixed representative of a right coset. The hidden shift can be decomposed as s = s a s r , and with f (xs) = g(x), the relation f (xs a s r ) = g(x) can be seen as f (xs a ) = g(x), which is an instance of the hidden subgroup problem in A. The complete algorithm is then to do a Grover search on the right coset, and then try to solve the problem in A, as presented in Algorithm 3.

As the hidden shift is a joint property of the two functions, we cannot do a collision search as in the generic case, and need an exhaustive search. This procedure can also be used to solve the hidden period problem, as this is the case f = g. Hence, we can upper bound the hardness of the generic hidden shift problem, in function of the size of the group (around 2 n ) and the size of its maximal abelian subgroup (around 2 a ), which would be around 2 (n-a)/2+ √ 2 log 2 (3)a . GL 2 (q) contains (q 2 -q)(q 2 -1) elements, some of which of order q 2 -1. If we consider the group generated by such an element, we'll have A of size around q 2 2 n/2 . This means the complexity of the HSP in GL 2 (q) is at most around q2 2.6

√ log 2 (q) = 2 n/4+1.3 √ n .
For S n , we can consider the subgroup generated by Algorithm 3 Generic resolution of a hidden shift problem in a non-abelian group

A ← A commutative subgroup of G C ← {A representative of each right coset} procedure GroverSearch(c ∈ C) c is assigned in quantum superposition s ← Kuperberg's algorithm result in A for f (xc) and g(x) if f (xsc) = g(x) for a few random x then Mark c end if end procedure
c is now the representative of the coset of the shift s ← Kuperberg's algorithm result in A for f (xc) and g(x) return sc the 2-cycles {(2i -1, 2i)|1 ≤ i ≤ n/2}. As all the cycles are disjoint, this is an abelian group, of size 2 n/2 , isomorphic to (Z/(2)) n/2 . This allows the use of Simon's algorithm to find the hidden shift, with a total cost of around n2 -n/4 √ n!, for a group of size n!. This is however asymptotically worse than 3 √ n!. This suggests that even for non-abelian groups, the structure can lower the security of a scheme based on the hidden shift problem. To illustrate this we present in Table 2 the security of different group laws and their respective size.

Group (Z/(2)) 128 Z/(2 128 ) GL2(2 32 ) S34 (Z/(2))

New algorithm: Simon Meets Kuperberg

We describe in this section a new quantum algorithm, that, for the first time, solves efficiently the HSP problem when considering a product of cyclic groups, which often appears in symmetric constructions [START_REF] Berger | Extended generalized feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput[END_REF][START_REF] Suzaki | \textnor-mal{\textsc{TWINE}}$ : A lightweight block cipher for multiple platforms[END_REF][START_REF] Ferguson | The skein hask function family[END_REF][START_REF] Bernstein | The salsa20 family of stream ciphers[END_REF]. We also provide a simulation of the algorithm in section 4.3, showing that our complexity estimations are correct.

Solving the Problem for Parallel Modular Additions

An interesting generalization for, inter alia, symmetric cryptography is to consider p termwise additions modulo 2 w , that is, a modular addition in Z/(2 w ) p . The hidden shift in this case is a vector s = (s 1 , . . . , s p ) of p words of w bits each. The aim of this section is to propose a new algorithm that deals efficiently with that group. The first logic approach was to apply an adapted variant of Kuperberg, but its complexity significantly differs from optimal. We propose a new algorithm which complexity is close to optimal. It exploits three facts in particular that allow us to consequently improve the complexity. In order to describe our algorithm, we need to previously adapt the first part of Kuperberg's algorithm by considering a quantum Fourier transform compatible with the group law, so the original one is changed to into a termwise variant. The oracle circuit produces the qubits ψ 1 ,..., p = |0 + exp 2ιπ si i 2 w |1 , the product is replaced by an inner product. The combination circuit also works the same way, and produces a termwise sum or difference.

Better worst-case gain. The first fact that allows to improve the complexity over a basic algorithm is realizing that, though the combination strategy can be quite similar with a research of partial collisions on the lowest significant bits of each term, there is however a difference in the behavior in the disadvantageous case: while we gained only one 0 in the former situation, here, we'll get a 0 in each term in which we have a collision in the lowest 1 (p zeros) while the size of the corresponding list is big enough. We also have more choices in the combinations, and we can have various equivalent and incompatible possibilities, with collisions on different parts of the vector.

With p + 1 equations we can always gain p zeros. As before, we can separate the elements in pools, depending on the divisibility by 2 of each term. Instead of looking at the position of the first one, we look at the position of the first one in any component of the vector to separate in pools. In each w pool, we can restrict ourselves to the bit slice corresponding to the corresponding level. This slice corresponds to a vector in (Z/(2)) p . Hence, we can produce a vector that will fit in the next pool if we manage to find some linearly dependent vectors, that is, whose sum (or difference, as it is the same in Z/(2)) is 0.

Recovering the shift. We realized that the elements with i ∈ 0, 2 w-1 are of the form ψ 1,..., p = |0 +exp (ιπ s i i ) |1 , so measuring them in the {|-, |+ } basis will give us the parity of s i i , that is, a linear equation in the parity bits of the s i . In the case w = 1, we get a variant of Simon's algorithm for hidden shifts.

We describe next how to apply each approach separately, and then describe how our algorithm combines them to obtain an optimized complexity, that will be discussed and analyzed in section 4.2.

First Idea: Kuperberg's variant with a better worst-case gain. A simple strategy represented in Algorithm 4 is to mimic the former one: we apply directly the strategy with the first term to zero all its bits except the most significant one, and then process the second term, and so on. We can also apply it the other way around: we can see the vector (s w-1

1 • • • s 0 1 , . . . , s w-1 p • • • s 0 p ) as the number s w-1 p s w-1 p-1 • • • s w-1 1 s w-2 p • • • s 0 p • • • s 0 1
, and apply directly the former strategy, until we get enough elements of the form s w-1

p s w-1 p-1 • • • s w-1 1 0 • • • 0 that
we can measure. Another approach is to weight all the possible combinations with the expected gain in the total number of trailing zeros, and choose the most favorable one. The first two have the advantage of being classically easy to implement, with a radix tree. Second Idea: p + 1 dependent equations always gain p zeros. There is however another way to use the parallel structure of the hidden subgroup: given p + 1 random elements, we can find a subset whose sum (or difference) will always be even on all the components: if we look at the parity vector of the elements, this corresponds to a linearly dependent subset of the vectors. This approach can be useful if p is big with respect to the size of the pools: with on average p/2 + 1 vectors, we can zero p bits. We can then iterate the technique to set to zero the next row of bits, and so on. This is described in Algorithm 5.

Moreover, seeing the elements in a pool as equations allows us to perform the same optimisation we have proposed for the case p = 1, to get all the secret in one pass. Instead of storing one element per pool, we have to store p elements that are linearly independent, that is, a full system of equations. As this optimisation does not depend on what we do to each pool, we can also apply it to improve Algorithm 4.

As, on average, we combine (p/2 + 1) elements, we divide at each w step the pool by (p/2 + 1). This algorithm has a complexity in O((p/2 + 1) w ). If w = 1, it matches Simon's complexity (and is, indeed, Simon's algorithm). It is interesting for big p, as it is polynomial in p, but it quickly becomes costly if w rises, as it is exponential in it.

Our new algorithm: combining both ideas. As the two variants merge the elements to progressively create new elements with a greater number of zeros, we can, to be more efficient, combine both methods. The algorithm uses a threshold to choose between the two approaches. It determines when we have to change the method of sieving. The value of this threshold is calculated and studied in the next section. Our new algorithm is described in Algorithm 6, where all the bits are also recovered in one pass thanks to our adapted improvement.

Complexity analysis

In this section we provide a complexity analysis of the previously described algorithm, that will depend on the relation between the parameters w and p. A summary can be found in Table 5.

We first estimate the complexity of Algorithms 4 and 5, and then combine these costs to compute the best thresholds, and derive the final complexity.

Complexity using partial collisions. To estimate the complexity of partial collisions in (Z/(2)) p , we had the same approach as for the original algorithm: we performed simulations. As we do not have bad outcomes in this case, we expected a more efficient algorithm. An optimistic approach could estimate that the complexity is 2 √ 2p , which would mean that a pool of 2 a elements produces a pool of 2 a-1 elements that all have a more zeroes. In practice, this is not what we observed, and we found a complexity of around 2 √ 2.3p , as presented in Table 3. This algorithm is far from the best method to solve this problem, but it can become relevant if we need a huge number of elements that are zeroed on p bits. Collision cost. We have two heuristics for collision cost. When we don't have enough elements to have some collisions, we estimate from our simulations the cost to produce N elements to be around 2 ) 2 in this situation. The minimal cost is around 2N , as we need to combine every element with another one. Doing simulations, we found that it is (2N + 2 p-2 )/(1 + 1/2 p ), asymptotically in N . The 2N comes from the fact that we do for almost all non-zero elements one combination, the 2 p-2 corresponds to the small number of elements that don't have a total collision with another element, and the (1+1/2 p ) corresponds to the zero element that can naturally occur, with probability 1/2 p . Alternative approach. Instead of considering only one row of bits and try to zero it, we can consider a bigger chunk. That is, we want to produce N elements that have a certain amount (greater than p) of zeroes in their firsts bits. In order to estimate this cost, we refer to Kuperberg's original algorithm. In practice, the algorithm will be more efficient, but we can approximate it with the original Table 3: Some results of the simulations, for 90% success.

√ 2.3p+log 2 (N
complexity. We can then estimate the cost of the algorithm to zero q bits to be 2

√ 2 log 2 (3)q+log 2 (N ) 2 .
As before, this will not hold if we have to many elements to produce, as the minimal cost is 3N , but we should never be in this regime.

Complexity using equations.

Lemma 5 (Equation cost). A step of Algorithm 5 produces N elements with p zeroed bits using N (p/2 + 1) elements on average, and needs p qubits.

Proof. A step of Algorithm 5 uses random equations to produce a zeroed element. If we have p elements that form a basis of Z/(2) p , any other element is a linear combination of p/2 elements, on average, in this basis. If we have a basis, we can hence get an equation that has, on average p/2 + 1 elements, and that sums to zero on the p bits. We can then construct such a basis by choosing p random elements : if they form a free family, we have a basis, if not, we then have some elements that sums to zero. This allows to perform the algorithm on-the-fly : each time a new element arrives, we can try to form a basis with the previous one. If we new element is linearly independent, we add it in our memory. If it is not, we combine all the elements that sums to zero.

Theorem 1. Algorithm 5 has a complexity in quantum queries and time of around 2(p/2 + 1) w . It needs 2p(w -1) quantum memory, plus the oracle cost.

Proof. At each step, we store p independent elements that will allow us to retrieve p bits, and divide the remaining number of elements by p/2 + 1. At the end, we want p elements (with only p elements, as they would be random, the success probability is only of 1/e, but we can get arbitrarily close to 1 with a fixed overhead). The total cost is then of

p(p/2 + 1) w-1 + p(p/2 + 1) w-2 + • • • + p,
which reduces to 2(p/2+1) w . The total cost in quantum memory is then p(w-1) qubits for the w -1 steps, and p(w -1) qubits that will yield an equation in the bits of the shift, but that we cannot measure immediately. This cost in memory is optional, as we could do the algorithm w times, but we would then have to pay the constant overhead at each step, not only at the last one. Remark 6. We found that the marginal cost of (p/2 + 1) elements to produce one can be beaten if the total number of elements is huge by sorting them before searching for a zero-sum set. As extracting values from a radix tree naturally produces a sorted list, this was observed in our simulations.

Determining the total complexity. To determine the complexity, we will run the algorithm backwards : we estimate how many elements we need at a point of the algorithm, and then deduce how many elements we need before to obtain this number of elements. More precisely, we consider a fixed p, and estimate what we have to do to get the elements we want as w grows.

The final steps. The final steps uses Algorithm 5. The complexity to process w rows is then C 0 (p, w) = 2(p/2 + 1) w .

Changing to collision finding. With collision finding, we can erase one row and produce N elements at a cost of 2 √ 2.3p+log 2 (N ) 2 . We will prefer to use this algorithm instead of the previous one if

C 0 (p, w) > 2 √ 2.3p+log 2 (C0(p,w-1)) 2 . This means that 2(p/2 + 1) w ≥ 2 √ 2.3p+(1+(w-1) log 2 (p/2+1)) 2 , which implies w ≥ w 0 = 1.15p/ log 2 (p/2 + 1) 2 + 1/ log 2 (p/2 + 1) -1/2 .
This threshold is the number of steps in which we should use Algorithm 5, and the previous steps are solved using 4. The total cost is then around

C 1 (p, w) = 2 √ (1+w0 log 2 (p/2+1
)) 2 +2.3p(w-w0) . However, this approximation regime is only valid while the total number of elements is small enough. Saturated regime of collisions. We saw before that the cost of zeroing one row is asymptotically around 2N , and cannot outperform this bound. We can now estimate when our previous estimate violates this bound. This occurs when 2

√ 2.3p+log 2 (N ) 2 ≤ 2N , which implies N ≥ 2 2.3p-1 2 2 1.15p
. Using this constraint to the previous complexity, we get that w must be lower than

w 1 = 2.3p/4 + w 0 -(1 + w 0 log 2 (p/2 + 1)) 2 /2.3p .
We can still use the algorithm in this saturated regime, and estimate that one row can be erased if we divide by 2 the number of elements. Then, the complexity is C 2 (p, w) = 2 w-w1+ √ (1+w0 log 2 (p/2+1)) 2 +2.3p(w1-w0) .

Multiple steps at once. The complexity we got at the previous step does not have any constraint. It can however become irrelevant, as we have a better approximation if w is big enough, as it is exponential in w. Indeed, we can estimate that we can erase pw zeros and get N elements at a cost of 2

√ 2 log 2 (3)pw +log 2 (N ) 2 .
This approximation will become relevant when 2 Simon Meets Kuperberg. From Table 5 we can see how Simon's complexity is met in the extreme case where w = 1 and Kuperberg's complexity is obtained when p = 1, as expected. It also shows that even if asymptotically in w, the complexity becomes closer to the complexity of Kuperberg's algorithm in Z/(2 pw ), the last w 2 rows of bits of the state do not provide as much security.

√ 2 log 2 (3)p+log 2 (C2(p,w-1)) 2 ≤ C 2 (p, w), which implies w ≥ w 2 = log 2 (3)p -1/2 + w 1 -(1 + w 0 log 2 (p/2 + 1)) 2 + 2.3p(w 1 -w 0 ) . The total complexity is then C 3 (p, w) = 2 √ 2 log 2 (

Simulations of the algorithm

We have performed various simulations of the algorithm, in order to confirm our models and theoretical complexities. For w = 1, the obtained complexity corresponds to solving an equation system, hence it needs around p queries, and our model holds. For p = 1, the complexity is reduced to 2 √ 2 log 2 (3)p , which corresponds to our previous simulations. We've considered two types of simulations in order to confirm our algorithm. First, as before, we simulated the success probability of the algorithm for a given input size. Second, we simulated the number of elements at each step of the algorithm, in order to see more precisely the accuracy of each model. Table 6: Simulations compared with our model, with a success probability of 90%, 1000 tests per estimation, in log scale, for pw = 100 and 128.

From Table 6, we see that our estimates correspond to the simulations in the ranges we were able to simulate, with a slightly pessimistic estimation when p is not too small and w is bigger than p. In order to estimate the accuracy of our different models, we also simulated the number of elements in each pool at the beginning of each step, as for example in Figure 3.

The computed thresholds for Figure 3 are (2,3,7). As they are in reverse, they correspond to [START_REF] Brassard | Merkle puzzles in a quantum world[END_REF]12,[START_REF] Daniel | Post-quantum cryptography[END_REF] on the graph. The two curves are converging at around step 9, which suggests that our models 3 and 4 are slightly pessimistic. This is explained by the fact that model 3 neglects the gains of good combinations and model 4 the gains of bad combinations.

Cryptanalysis of Poly130in the Superposition Model

We propose in this section the first quantum superposition attack on the Poly1305 primitive, with a complexity of about 2 38 in time and queries, that shows that it is not secure in the superposition model.

Poly1305 description

Poly1305 is a MAC designed by Bernstein [START_REF] Bernstein | The Poly1305-AES Message-Authentication Code[END_REF]. It has been standardized for TLS 1.2 [START_REF] Langley | chacha20-poly1305 cipher suites for transport layer security (tls)[END_REF], is currently a part of a recommended cipher suite in the TLS 1.3 draft [1], and is notably supported by OpenSSH, Firefox and Chrome. The designer announced in [START_REF] Daniel | Post-quantum cryptography[END_REF] a classical and quantum security of Poly1305 of 128 bits. We'll describe Poly1305-AES, but our analysis works with any internal block cipher used.

Poly1305-AES uses two 128-bit keys (r, k) and a 128-bit nonce n, takes as input a variable-length message m considered as an array of 128-bit blocks, and outputs a 128-bit tag. For efficiency purposes, some bits of r are fixed to 0, which means it can only take 2 106 different values. The function is

Poly1305-AES (r,k,n) ((m i ) i≤q ) = q i=1
(m q-i+1 + 2 128 )r i mod 2 130 -5 +AES k (n).

Quantum attack in the superposition setting

For our quantum attack, we consider having access to the oracle

P oly n : |m 1 |m 2 |0 → |m 1 |m 2 |Poly1305-AES (r,k,n) (m 1 , m 2 ) .
The nonce is classical, and changes at each query. As we consider the superposition scenario, we consider that the function can be called in superposition. We aim at retrieving r (and not k), as r is sufficient to retrieve AES k (n) for any tag, which allows some forgeries. If one also wants k, one can perform a Grover search on it, with an additional cost of 2 64 . In the additional material B we describe a distinguisher on Poly1305 and a simple key-recovery attack, but in this section we propose a more evolved attack that uses Kuperberg's algorithm.

Poly1305 uses a polynomial structure for hashing, and the commutative algebra Z/(2 130 -5)[X] contains many possible shift structures, both in Z/(2 130 -5) (with addition) and in Z/(2 130 -6) (with multiplication). For example, one can consider the two functions f (x) = xr + r 2 + 2 128 (r + r 2 ) and g(x) = xr + 2 128 (r + r 2 ), which satisfies f (x) = g(x+r). We cannot call them directly, but we can call F (x) = Poly1305-AES (r,k,n) (1, x) and G(x) = Poly1305-AES (r,k,n) (0, x), which, if the nonce is the same, also satisfy F (x) = G(x + r).

There are two issues that do not allow the direct application of Kuperberg's algorithm: first, the nonce changes at each query, which means that in order to have F (x) = G(x+r), we must compute F and G in only one query to Poly1305. This is feasible, as both are of the form Poly1305(a(x)), with a(x) a function of x: one can compute a F (x) = (1, x) and a G (x) = (0, x) in superposition in an auxiliary register, and then call P oly n on it. Second, and more annoyingly, the inputs of Poly1305 are restrained to be between 0 and 2 128 -1, which means we cannot sample all group elements. This can still be solved by using Lemma 4, as we can query [0; 2 128 ). Solving the hidden shift in Z/(2 127 ) costs around 2 20 . We can thus set the interval size at 2 106 . r can be retrieved if it is below 2 127 . This is the case, as the bit constraints on r implies r < 2 124 , which means we need only to test 2 18 intervals. The total cost is then 2 20 × 2 18 = 2 38 , for a success probability better than one half. We can check if the found r is the right one by trying to forge some valid messages, or we can use the distinguisher presented in Appendix B.

Grover acceleration. As the previous attack involves an exhaustive search on the correct interval among the 2 18 , one might want to use Grover's algorithm, in order to gain up to 2 9 on the attack. We automatically lose a factor 2 because of the uncomputation of the algorithm. Moreover, we would need to compute all the qubit choices quantumly, and we must have a success probability of the inner function very close to one. All these factors make the attack more efficient in query (around 2 31 ), with a small time gain.

Impact of our improvements

The total cost of the attack depends vastly on the precise cost of Kuperberg's algorithm. The original algorithm, with an estimated complexity of around n 2 2 √ 2 log 3 (2 n ) , has here a cost of around 2 34 queries. The total attack is then vastly more costly, around 2 65 , which is very close to the cost of a simple exhaustive search on the key if AES-128 is used, and exceeds the cost of the simple quantum attack described in Appendix B. We could also use a Grover search, which would lead to a cost estimate of around 2 50 , which is far higher than both the non-Grover variant of our attack (at 2 38 ) and the Grover variant (at 2 31 ).

Attack on the FX Construction

The FX construction, proposed by Killian and Rogaway [START_REF] Kilian | How to Protect DES Against Exhaustive Key Search[END_REF], is a simple way to extend the key-length of a block cipher. It uses a block cipher E k0 and two additional keys k 1 , k 2 whose length is the block size of the block cipher, and the new cipher is FX k0,k1,k2 (

x) = E k0 (x ⊕ k 1 ) ⊕ k 2 .
We can see it as an Even-Mansour construction, with a block cipher taking the role of the random permutation. The quantum security of this scheme has been studied by Leander and May in [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FXconstruction[END_REF] in the superposition model. Their conclusion is that this construction is essentially as secure as the inner cipher E k0 . Their approach is close to the quantum attack against the Even-Mansour construction, with the addition that the key of the inner cipher has to be seeked. They consider the function f (k, x) = FX k0,k1,k2 (x) ⊕ E k (x), which fulfils the promise f (k 0 , x) = f (k 0 , x ⊕ k 1 ). They then recover k 0 and k 1 by performing a Grover search on k 0 , with a test function that is the application of Simon's algorithm to the partial function x → f (k 0 , x). If this function is periodic, then k 0 has a very high probability of being correct, and the period of the function is k 1 . It can moreover be efficiently checked, by testing the periodicity for a few values. Once k 0 and k 1 are known, k 2 can be retrieved with one known plaintext/ciphertext pair. The total cost is around 2|k 1 |2 |k0|/2 . This leads to some efficient attacks against the FX-based primitives DESX, PRINCE [12] and PRIDE [START_REF] Albrecht | Block ciphers -focus on the linear layer (feat. PRIDE)[END_REF]. For PRINCE and PRIDE, |k 0 | = |k 1 | = 64, the attack costs around 2 39 queries and time, whereas for DESX, |k 0 | = 56 and |k 1 | = 64, the attack costs around 2 35 queries and time 6 .

The authors only considered the original construction, that uses some xors, and left as an open problem the evaluation of the security using another group law. We can here give an answer for the most natural variant, which is to use modular additions instead of xors, with the cipher

FX+ k0,k1,k2 (x) = E k0 (x + k 1 ) + k 2 .
The function is no longer periodic in this situation, but we can find a hidden shift problem with the two functions f (k, x) = FX+ k0,k1,k2 (x)+E k (-x) and g(k, x) = FX+ k0,k1,k2 (-x)+E k (x), which fulfils the promise f (k 0 , x) = g(k 0 , x+k 1 ). These two function can efficiently be computed in superposition, for a total cost of one query and one encryption. The attack consists then in a Grover search that uses Kuperberg's algorithm as a test function. The Grover search needs the same number of iterations (2 |k0|/2 ), but Kuperberg's algorithm needs around 2 1.8 √ |k1| samples. The total cost is around 2 |k0|/2+1.8

√

|k1| × 2 queries (we can factor the query to f and g to only one query to FX+, and we double to uncompute Kuperberg's algorithm).

Other group laws. If the group is abelian, the attack can be straightforwardly applied. If the group law is not abelian, we need a slightly different approach. With F X • k0,k1,k2 (x) = E k0 (x • k 1 ) • k 2 and a a fixed non-zero value, we can consider f (x) = F X • k0,k1,k2 (x) • (F X • k0,k1,k2 (ax)) -1 and g(k, x) = E k (x) • E k (ax), which satisfies f (x) = g(k 0 , x•k 1 ). We can then have the same approach, using the corresponding non-abelian hidden shift algorithm in a Grover search. The concrete cost of the attack depends of the group structure, and can be estimated from the values of Table 2.

Quantum attack on PRINCE+ and PRIDE+. We can directly attack a variant of PRINCE and PRIDE where the key whitening is done through a modular addition. Concretely, we can attack them in around 2 47.4 queries and time, which is smaller than the ideal 64-bits of quantum security. We also attack DESX+ in 2 43.4 queries and time.

Concrete Proposals

The most interesting idea from [2] for preventing Simon-based attacks is using modular additions, which is already common in symmetric primitives (see for instance [START_REF] Rivest | RC6 as the AES[END_REF]47,[START_REF]Federal Information Processing Standard-Cryptographic Protection -Cryptographic Algorithm[END_REF]). Based on the complexities of the new algorithms and attacks from the previous sections, we can now correctly size some of the primitives that were broken using Simon-based algorithms, now patched to use modular additions, in order to provide a certain desired post-quantum security.

Let us point out that we used a slightly unconventional definition of the security: we consider a cipher to provide a security of Q bits when no attack of complexity lower than 2 Q exists (the more conventional definition being when no attack better than the generic exhaustive search is known, whose complexity usually is 2 Q = 2 k/2 ).

Concrete Parameters and Security of Some Generic Constructions

If we consider the generic Even-Mansour constructions, with a xor, it will provide a security of 8 or 9 bits for an state size of 128 or 256 bits respectively. When using one or several modular additions, this security is augmented, becoming 20 or 28.5 bits for states of 128 or 256 bits respectively, but all the constructions are far from the ideal 2 64 security offered by an ideal cipher with a 128-bit key, and even more from the 2 128 offered quantumly by a classical primitive with a 256-bit key. To the best of our knowledge, the quantum security offered by the Advanced Encryption Standard (AES) [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF] meets these ideal claims. In Table 7 we show the needed security parameters of some popular constructions in order to resist their corresponding attacks when using Kuperberg's algorithm. As expected, p modular additions of words of size w provide less security than one modular addition of the state size. We can see that, in all the cases, the size of the state needed to achieve a certain security becomes much bigger than for common symmetric primitives (128 bits for instance), needing to be bigger than 5200 bits in some cases. The problem of a bigger state is not limited to implementation issues: designing a secure permutation for such a big state would be a very challenging task. From table 2 we can also estimate the needed size for some constructions that uses non-abelian groups. Table 7: Examples of parameters for 128-bit security when using modular additions instead of ⊕. E-M stands for Even-Mansour and O-M for operation modes.

Conclusion

Modular additions are not enough. We have shown that the proposal from [2] does not seem practical. Using modular additions instead of xors would increase the security, but it would need a large internal state to provide reasonable security, far beyond the size of classical symmetric constructions. For instance, the key-alternating cipher with modular addition would need a few thousand bits of internal state and key size, to be compared with the 128 bits of internal state and 256 key-bits of AES-256. Beyond the obvious efficiency drawback, the design of a correspondingly large secure permutation would be a very challenging task.

Kuperberg's algorithm simulation and verification. We have been able to study, improve and simulate Kuperberg's algorithm: the concrete complexity of our tweaked version is 2 1.8

√ n , which is small enough for a practical use on typical parameters of n (we have therefore implemented it). We also have presented a way to solve the hidden shift problem in various situations (including non-abelian groups), and provided an estimate of the complexity.

New algorithm representing Simon-meets-Kuperberg. We provided a new efficient algorithm that solves the problem when considering parallel modular additions. We have simulated the algorithm and verified that our estimated complexity is met in practice.

Cryptanalysis of FX variants and Poly1305. This paper proposes some new quantum attacks, mainly using our generalized and improved Kuperberg's algorithm, that provide an important speed-up with respect to Grover's quantum generic exhaustive search attack.

Further applications. Hidden shift algorithms can be applied in other cryptographic fields. They have in particular been successfully applied to ordinary isogenies [START_REF] Childs | Constructing elliptic curve isogenies in quantum subexponential time[END_REF] and are relevant to assess the security of some proposed postquantum asymetric schemes, such as CSIDH [START_REF] Castryck | Csidh: An efficient post-quantum commutative group action[END_REF]. We leave as an open problem the evaluation of the security offered by this construction against quantum hidden shift algorithms, which was not addressed in the CSIDH paper.

Fig. 1 :

 1 Fig. 1: Quantum circuits for Kuperberg's algorithm

√ 2 log 2 Algorithm 2

 22 (3)n . A more precise complexity estimation is done in Section 3.4. Variant to get all the qubits in one pass Generate N random numbers in Z/(2 n ) Separate them in pools Pi of elements divisible by 2 i and not 2 i+1 for i := 0 to n -2 do while |Pi| ≥ 3 do Ensures Pi stays non-empty Pop two elements (a, b) of Pi where a + b or a -b has the highest possible divisibility by 2 (and is not 0) c is chosen randomly in {a + b, a -b} Insert c in the corresponding Pj if ∀i ∈ [0, n -1], Pi = ∅ then return Found end if end while end for return Failure

Fig. 2 :

 2 Fig. 2: Estimated success probability in the number of samples, for 64 bits

Algorithm 4

 4 Variant 1 for termwise additions Generate N random numbers in Z/(2 w ) p Separate them in pools Pi of elements with all p terms divisible by 2 i and at least one term not divisible by 2 i+1 for i := 0 to w -1 do while |Pi| ≥ 2 do Pop two elements (a, b) of Pi where a + b or a -b has the highest possible divisibility by 2 on each term c is chosen randomly in {a + b, a -b} Insert c in the corresponding Pj end while end for if Pn-1 = ∅ then return Found else return Failure end if

Fig. 3 :

 3 Fig. 3: Number of elements in each pool at each step for p, w = 8, 16, in log scale.

  (p/w) E-M(1/n) O-M/LRW(1/n) E-M(2048/13) E-M(1024/14) E-M(4

  , without qubits, in base 2

	Generate N random numbers in Z/(2 n )	Queries
	Separate them in pools Pi of elements divisible by 2 i and not 2 i+1
	for i := 0 to n -2 do
	while |Pi| ≥ 2 do
	Pop two elements (a, b) of Pi where a + b or a -b has the highest possible
	divisibility by 2 (and is not 0)
	c is chosen randomly in {a + b, a -b}	Combination
	Insert c in the corresponding Pj
	if Pn-1 = ∅ then	Found |ψ 2 n-1 ?
	return Found
	end if
	end while
	end for
	return Failure

Table 1 :

 1 Some results of the simulation of Algorithm 2 for 90% success probability

	n queries log 2 (queries) 1.8 *	√	n -0.5 number of tests
	16	118	6.9	6.7	10 6
	32	826	9.7	9.7	10 6
	64 14975	13.9	13.9	5 * 10 5
	80 49200	15.6	15.6	10 5
	128 9.8 * 10 5	19.9	19.9	5 * 10 4

Table 2 :

 2 Estimate of the cost of solving the hidden shift problem for some groups.

	2 30	Z/(2 5000 ) GL2(2 100 ) S78

  Algorithm 5 Variant 2 for termwise additionsGenerate N random numbers in Z/(2 w ) p Separate them in pools Pi of elements with each terms divisible by 2 i and at least one term not divisible by 2 i+1 System = ∅ for i := 0 to w -1 do Pop p elements from Pi linearly independent at the level i, put them in System Basis = ∅ for e ∈ Pi do if x mod 2 i+1 x ∈ {e} ∪ Basis is linearly independent then Add e to Basis else Find a linearly dependent subset J Compute c = ±

	x
	x∈J
	Insert c in the corresponding Pj
	end if
	end for
	end for
	if System is full then return Found
	else return Failure
	end if

  Algorithm 6 Combined algorithm for termwise additions Generate N random numbers in Z/(2 w ) p Separate them in pools Pi of elements with each terms divisible by 2 i and at least one term not divisible by 2 i+1 System = ∅ for i := 0 to threshold do Partial collisions Pop p elements from Pi linearly independent at the level i, put them in System while |Pi| ≥ 2 do Pop two elements (a, b) of Pi where a + b or a -b has the highest possible divisibility by 2 on each term c is chosen randomly in {a + b, a -b} Insert c in the corresponding Pj end while end for for i := threshold + 1 to w -1 do Zero-sum Pop p elements from Pi linearly independent at the level i, put them in System Basis = ∅ for e ∈ Pi do if x mod 2

	end if
	end for
	end for
	if System is full then return Found
	else return Failure
	end if

i+1 x ∈ {e} ∪ Basis is linearly independent then Add e to Basis else Find a linearly dependent subset J Compute c = ± x∈J x Insert c in the corresponding Pj

Table 4 :

 4 Threshold points for Algorithm 6.

	Constraint	Cost
	(w ≤ w0) w0 ≤ w ≤ w1	C0(p, w) = 2(p/2 + 1) w C1(p, w) = 2 √ (log 2 (C 0 (p,w 0 )) 2 +2.3p(w-w 0 )
	w1 ≤ w (≤ w2) w2 ≤ w	C2(p, w) = 2 w-w 1 C1(p, w1) C3(p, w) = 2 √ 2 log 2 (3)p(w-w 2 )+log 2 (C 2 (p,w 2 )) 2

Table 5 :

 5 Complexity of Algorithm 6.

In[START_REF] Boneh | Random Oracles in a Quantum World[END_REF][START_REF] Brassard | Merkle puzzles in a quantum world[END_REF][START_REF] Zhandry | Secure identity-based encryption in the quantum random oracle model[END_REF][START_REF] Unruh | Non-interactive zero-knowledge proofs in the quantum random oracle model[END_REF], it can query a quantum oracle with an arbitrary quantum input.

Implementations of theoretically secure quantum cryptography remain yet not fully understood, as shown by the attacks[START_REF] Zhao | Quantum hacking: Experimental demonstration of time-shift attack against practical quantum-key-distribution systems[END_REF][START_REF] Lydersen | Hacking commercial quantum cryptography systems by tailored bright illumination[END_REF][START_REF] Xu | Experimental demonstration of phase-remapping attack in a practical quantum key distribution system[END_REF]

Even if some later algorithms have been developed and are more efficient, we focus on the original algorithm for two main reasons. We focus on quantum query and time complexity and the gain from[START_REF] Regev | A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space[END_REF] is in memory and[START_REF] Ettinger | On Quantum Algorithms for Noncommutative Hidden Subgroups[END_REF] needs an exponential time classical post-processing. Moreover, we want concrete values and not asymptotic exponents and the algorithm in[START_REF] Kuperberg | Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF] is far harder to estimate precisely.

log 2 (3)n . As the paper only focuses on the asymptotic exponent complexity, the polynomial part is not well known. We can however deduce from the sketch of proof a complexity in O n 2 2

log 2 (3)n to retrieve the whole hidden shift, which, due to the way the sketch of proof works, may not be a tight bound (both for the polynomial and the exponent).

In[START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FXconstruction[END_REF], they considered the time of a parallelized Simon's algorithm, which can be neglected, leaving a complexity of 2 32 .

Acknowledgements

The authors would like to thank André Chailloux, Anthony Leverrier and André Schrottenloher for their helpful comments and discussions.

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714294 -acronym QUASYModo).

Appendix

A Kuperberg and SMK simulation code

Available at https://who.paris.inria.fr/Xavier.Bonnetain/extra/code. tar.gz.

B A distinguisher attack on Poly1305

We can use a simple distinguisher, that allows to discriminate between a x |x |A(s) and x |x |A(x, s) . If one apply a Hadamard gate to the first register, the first state would become |0 |A , while the second become x,y (-1) x•y |y |A(x) . If x → A(x, s) is a permutation, then there will be no interference, and the probability of measuring a 0 in the first register is 1/2 n in the second case, whereas it is 1 in the first case.

We can apply this to Poly1305, with

where Poly1305(x) is the tag of the one-block message x, with an unspecified nonce. If s = r, then A(x, r) = AES k (n) (which is a fixed value for each query), and if not, it will be A(x, s) = (x + 2 128 )r mod 2 130 -5 -(x + 2 128 )s mod 2 130 -5 + AES k (n) mod 2 128 . As the function x → xs in Z/(2 130 -5) is, with an overwhelming probability, a permutation, we will measure a 0 with a wrong guess with a probability of around 2 -126 . This distinguisher can then be used in a Grover search on r that calls Poly1305 : at each step, we compute

x |x A(x, r), apply a Hadamard gate on the first register, and mark r if the first register is 0. As the test function is not perfect, the success probability of the algorithm will be smaller than 1, but the error of the test function is small enough to have a negligible final error.

There is still one problem : to perform a Grover search, we need to uncompute our computations. And as Poly1305 generates a fresh nonce at each query, we cannot uncompute the function. This is however not a problem, as a nonce difference in the uncomputation will produce a fixed difference in the output (AES k (n) -AES k (n )). This means that the uncomputation would leave the register in a non-zero but non-entangled state, which allows to safely erase and reset it.

We can hence apply a Grover search on r. As it has 106 variable bits, it would cost around 2 53 queries and time to retrieve r.


Preface to Volume 2018, Issue 1

Florian Mendel 1 and María Naya-Plasencia 2 1 Infineon Technologies, Germany 2 Inria, France IACR Transactions on Symmetric Cryptology (ToSC) is a forum for original results in all areas of symmetric cryptography, including the design and analysis of block ciphers, stream ciphers, encryption schemes, hash functions, message authentication codes, (cryptographic) permutations, authenticated encryption schemes, cryptanalysis and evaluation tools, and security issues and solutions regarding their implementation.

ToSC implements an open-access journal/conference hybrid model following some other communities in computer science. All articles undergo a journal-style reviewing process and accepted papers are published in gold open access (in our case the Creative Commons License CC-BY 4.0). The review procedures that we have followed strictly adhere to the traditions of the journal world. Full papers are assigned to the members of the Editorial Board. These members write detailed and careful reviews (usually without relying on subreviewers). Moreover, we have had a rebuttal phase, allowing authors to respond to the review comments before the final decisions. If necessary, the review process enables further interactions between the authors and the reviewers, mediated by the Co-Editors-in-Chief. Detailed discussions among the reviewers lead to one of the following four decisions for each paper: accept, in which case the authors submit their final camera-ready manuscript after editorial corrections; accept with minor revision, which means that the authors revise their manuscript and go through one or more iterations and reviews of the manuscript until the comments have been addressed in a satisfactory way; major revision, which means that the authors are requested to make major changes to their manuscript before submitting again in one of the next rounds; and reject, which means that the manuscript is deemed to be not suitable for publication in ToSC. The last four issues we have tried to refine the method (new for a community used to only accept or reject decisions) and decide in a more fair way when to assign major revisions.

The review process shares with the high quality conferences that it is double-blind and adheres to a strict timing; but unlike a traditional conference, there are multiple submission deadlines per year. Each paper received at least three reviews; for submissions by Editorial Board members this was increased to at least four.

Overall, we are very pleased with the quality and quantity of submissions, the detailed review reports written by the reviewers and the substantial efforts by the authors to further improve the quality of their work. We think that the review process leads to an increased quality of the papers that are published.

The papers selected by the Editorial Board for publication in the last four issues were presented at the conference Fast Software Encryption (FSE). This gave the authors the opportunity to advertise their results and engage in discussions on further work. In 2018, FSE was held during March 5-7, 2018 in Bruges, Belgium. The papers presented at FSE 2018 appeared in ToSC Volume 2017, Issues 2-4 and Volume 2018, Issue 1. For Volume 2017, Issue 2, we received 33 submissions, out of which 10 were accepted, 4 of these after minor revisions; the number of papers that received a major revision decision was 4. For Volume 2017, Issue 3, we received 32 submissions, out of which 13 were accepted, 9 of these after minor revisions; the number of papers that received a major revision decision was 7. For Volume 2017, Issue 4, we received 48 submissions, out of which 12 were accepted, 3 of these after minor revisions; the number of papers that received a major revision decision was 11. For Volume 2018, Issue 1, we received 61 submissions, out of which 13 were accepted, 7 of these after minor revisions; the number of papers that received a major revision decision was 10.

Besides the 48 selected talks, the program included one invited talk by Marc Stevens on breaking SHA-1. The conference also featured a rump session, chaired by Joan Daemen and Pierre Karpman, with several short informal presentations. As it is tradition for FSE, the Editorial Board also selected a best paper, based on the scientific quality and contribution. The Editorial Board has decided to give the award to the paper by Colin Chaigneau, Thomas Fuhr, Henri Gilbert, Jian Guo, Jérémy Jean, Jean-René Reinhard and Ling Song entitled "Key-Recovery Attacks on Full Kravatte".

We would like to thank the authors of all submissions for contributing high quality submissions and giving us the opportunity to compile a good and diverse program. In particular, we would like to thank the Editorial Board members; we value their hard work and dedication to write constructive and detailed reviews and to engage in interesting discussions. Many Editorial Board members spent additional time as shepherds to help the authors improving their works. We would also like to thank the subreviewers for their efforts. We are profoundly indebted to the conference General Chair Elena Andreeva for her hard work to make the conference a success. We also would like to thank Anne Canteaut, Shai Halevi, Gregor Leander, and Friedrich Wiemer for their work and support. Finally, we would like to thank SWIFT, imec and STMicroelectronics for their generous support of the conference.

We hope that the papers in this volume of IACR Transactions on Symmetric Cryptology prove valuable and we are glad to see that ToSC is becoming the leading international venue publishing the top research on symmetric cryptology.

February 2018

Florian Mendel María Naya-Plasencia