Xavier Bonnetain

Gaëtan Leurent

María Naya-Plasencia

André Schrottenloher

Quantum Linearization Attacks

Keywords: Quantum cryptanalysis, MACs, superposition query model, Deutsch's algorithm, Bernstein-Vazirani algorithm, Simon's algorithm, Shor's algorithm

Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs. . . ) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. Recovering the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes. In this paper, we introduce the quantum linearization attack, a new way of using Simon's algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. Recovering this structure allows to perform forgeries. We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric cryptanalysis: Deutsch's, Bernstein-Vazirani's, and Shor's. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks. Our attack breaks many parallelizable MACs such as LightMac, PMAC, and numerous variants with (classical) beyond-birthday-bound security (LightMAC+, PMAC+) or using tweakable block ciphers (ZMAC). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.

Introduction

The possible emergence of large-scale quantum computing devices in a near future has prompted a wide move towards post-quantum security, which takes into account the new security threats that they pose. In particular, the most popular asymmetric cryptosystems currently in use, such as RSA, can be broken by an adversary capable of successfully implementing Shor's algorithm [START_REF] Shor | Algorithms for quantum computation: Discrete logarithms and factoring[END_REF]. An ongoing standardization project led by the NIST [56] has structured the efforts of the (asymmetric) cryptographic community on this question.

As symmetric primitives do not rely on a trapdoor, they seemed for a long time to avoid the cases where quantum computers bring an exponential speedup over the best classical algorithms. In fact, most problems in symmetric cryptography, such as the search for the secret key of a black-box cipher, seem to admit a quadratic speedup at best, given by Grover's quantum search algorithm [START_REF] Grover | A fast quantum mechanical algorithm for database search[END_REF]. Although this speedup is significant, it could be countered by increasing the parameters of symmetric cryptosystems, e.g., doubling the size of secret keys.

However, in the past few years, a series of works have shown the insecurity of some symmetric cryptosystems against quantum adversaries entitled to superposition queries. That is, some primitives become broken if they can be queried inside a quantum algorithm. This started with the 3-round Feistel distinguisher proposed by Kuwakado and Morii [START_REF] Kuwakado | Quantum distinguisher between the 3-round feistel cipher and the random permutation[END_REF]. Later, they found a polynomial-time keyrecovery attack on the Even-Mansour cipher [START_REF] Kuwakado | Security on the quantum-type even-mansour cipher[END_REF], which was the first quantum key-recovery on a classically secure symmetric construction. These results rely crucially on the fact that many popular designs in symmetric cryptography have a strong algebraic structure, as they are built by combining smaller primitives (such as permutations or block ciphers) using cheap operations such as XORs. Kaplan et al. [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF] showed that many other constructions exhibited a structure exploitable by a quantum adversary, and designed the first forgery attacks on MACs (notably CBC-MAC [START_REF] Black | CBC MACs for arbitrary-length messages: The three-key constructions[END_REF], OMAC [START_REF] Iwata | OMAC: one-key CBC MAC[END_REF], PMAC [START_REF] Black | A block-cipher mode of operation for parallelizable message authentication[END_REF]) and authenticated encryption schemes (e.g., OCB3 [START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF], GCM [START_REF] Mcgrew | The security and performance of the Galois/Counter Mode (GCM) of operation[END_REF]).

In this paper, we will focus on idealized MAC constructions that authenticate messages of arbitrary size using smaller primitives such as permutations, block ciphers or tweakable block ciphers (TBCs) of block size n. These constructions have classical proofs of security showing either that the MAC behaves as a pseudo-random function, or that it is unforgeable, up to some exponential bound in n. We will exhibit polynomial-time quantum attacks on constructions that were not vulnerable to previous Simon's attacks (like those of [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF][START_REF] Santoli | Using Simon's algorithm to attack symmetric-key cryptographic primitives[END_REF]). Previous Attacks. Although there have been many of them, all the quantum forgery attacks known so far follow the same paradigm. They query the MAC with a constant number of blocks, using usually a single block of message x in superposition. Inside the MAC, this block of message x is XORed to some unknown value α depending on other blocks: thus, the result is MAC(x ⊕ α).

Having two different values α 0 , α 1 , we then have access to two functions f (x) = MAC(x ⊕ α 0 ) and g(x) = MAC(x ⊕ α 1 ), such that f (x) = g(x ⊕ α 0 ⊕ α 1 ). From there, we can use Simon's Boolean hidden shift algorithm [START_REF] Simon | On the power of quantum computation[END_REF] as a black box. It recovers α 0 ⊕ α 1 in quantum polynomial time, whereas any classical algorithm would require exponentially many queries to f and g (thus to the MAC). The recovery of the internal shift α 0 ⊕ α 1 then enables the adversary to forge new messages, and in some cases to recover secret-key material.

Let us point out the following important remark:

If the message blocks are not directly XORed to internal values (keys, offsets, encryption of other blocks. . . ), then the previous attacks based on Simon's algorithm do not apply.

Contributions. In this paper, we present the quantum linearization attack, which is a new family of quantum attacks on classically unforgeable MACs when superposition queries are allowed. Thanks to the novelty of our approach, we are able to attack many MACs that resisted previous cryptanalysis, as they do not not exhibit the property recalled above (a message block XORed to an internal state value). In particular, our attack usually circumvents the use of TBCs instead of block ciphers. It is also the first case of a quantum polynomialtime attack on MACs with beyond-birthday security, where the internal state has a bigger size. As an example, we break LightMAC with a linear number of queries, and we can attack LightMAC+ with only twice as much. Overview. Our attack starts with the following remark. Consider a function of blocks x 1 , . . . , x of the form: G(x 1 , . . . , x ) = g 1 (x 1 ) ⊕ . . . ⊕ g (x ) ⊕ C , where C is an independent constant, and the g i are independent random functions to which the adversary does not have access. Then classically, this function cannot be distinguished from random with a single query, though as little as four would be enough: we make x 3 , . . . , x constant, we query for every x 1 ∈ {0, 1} and x 2 ∈ {0, 1}: the XOR of the four results is zero.

Our key idea is to linearize the function G by restricting the block inputs so that the output is an affine function. Similarly to the simple classical distinguisher, we make the blocks x 1 , . . . , x take only one-bit values and emulate a function of an -bit input:

F (x) = F (b 1 . . . b ) = G(0 n-1 b 1 , . . . , 0 n-1 b
). Now, we will remark that F is an affine function of b 1 , . . . , b . As the g i are XORed; flipping a bit b i in the input XORs g i (0) ⊕ g i (1) to the output.

It is well known that the Bernstein-Vazirani algorithm allows to distinguish an affine function from a random one with a single quantum query. This shows that, thanks to a multi-block input, we can access new vulnerabilities of cryptographic constructions. But the power of our attack is clearly demonstrated when we make G go through a new random function:

G (x 1 , . . . , x ) = g(G(x)) = g (g 1 (x 1 ) ⊕ . . . ⊕ g (x ) ⊕ C) . (1)
All the functions g 1 , . . . , g , g are unknown to the adversary, so she cannot find the affine structure of the internal G. In fact, this function would be classically secure as a MAC. However, when linearizing, we obtain:

G (x) = g(F (x))
where F is an affine function of x = b 1 . . . b . Thus, G embeds a hidden Boolean period, and Simon's algorithm can recover it in polynomial time.

Applications. In Section 4 and Section 5, we detail the applications of our algorithm. We obtain the first polynomial-time attacks against the following MACs:

ΘCB3 [START_REF] Rogaway | Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC[END_REF][START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF], LightMAC [START_REF] Luykx | A MAC mode for lightweight block ciphers[END_REF], LightMAC+ [START_REF] Naito | Blockcipher-based MACs: beyond the birthday bound without message length[END_REF], Deoxys [38], ZMAC [START_REF] Iwata | ZMAC: A fast tweakable block cipher mode for highly secure message authentication[END_REF], PMAC TBC3k [START_REF] Naito | Full PRF-secure message authentication code based on tweakable block cipher[END_REF], PolyMAC [START_REF] Iwata | Stronger security variants of GCM-SIV[END_REF], GCM-SIV2 [START_REF] Iwata | Stronger security variants of GCM-SIV[END_REF] In addition, we provide attacks on the XOR-MACs of [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF], on MACs based on universal hashing (e.g., NMH * [START_REF] Halevi | MMH: software message authentication in the gbit/second rates[END_REF] and BRW Hashing [START_REF] Bernstein | Polynomial evaluation and message authentication[END_REF]) and, in Section 5.5, a new superposition forgery attack against Poly1305 [START_REF] Bernstein | The Poly1305-AES message-authentication code[END_REF]. A previous quantum attack was given in [START_REF] Bonnetain | Hidden shift quantum cryptanalysis and implications[END_REF], using a hidden shift structure. Using Shor's algorithm instead, we reduce the number of superposition queries from 2 38 to about 32. On Parallelizable MACs. The quantum linearization attack leaves only little space for quantum-secure parallelizable PRFs. Indeed, we are able to break any PRF with extendable domain, where at least ≥ n independent input blocks of ≤ n bits are processed independently, then XORed. This works as well for any operation that is linear on (F 2 ) n . It is still possible to obtain an unforgeable IVor nonce-based MAC of this form, as shown in [START_REF] Bhaumik | QCB: efficient quantum-secure authenticated encryption[END_REF], but the security then relies on the non-repetition of IVs. We do not know if an attack applies when we use a modular addition instead of a XOR in [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF]. If this was the case, then it would clearly mean that one has to rely on sequentiality or on nonlinear operations. Organization. We start in Section 2 by reviewing some quantum computing notions, the quantum algorithms used in this paper (Deutsch's algorithm, Bernstein-Vazirani, Simon's algorithm, Shor's algorithm), the Q1 / Q2 attack scenarios and notions of quantum unforgeability. In Section 3, we detail our new algorithmic ideas. In Section 4, we apply our attack to many parallelizable MAC constructions. We dedicate Section 5 to MACs based on universal hashing. We discuss the implications of our attacks in Section 6 and conclude the paper in Section 7.

Preliminaries

In this section, we give some preliminaries about quantum computing, quantum attacker models and the well-known quantum algorithms that will be used throughout this paper. We elaborate about the Q2 attacker model and the notion of quantum unforgeability for MACs, with or without IVs. Note that some details of quantum computing will appear in this section. They are intended for the interested reader. In the rest of this paper (with the exception of Section 5.5), we will use the algorithms of this section as black boxes.

Notation

We consider n-bit string values, sometimes as elements of F 2 n , sometimes as elements of F n 2 . This shall be clear from context. We let ⊕ denote the XOR (addition in F n 2 ), denote multiplication in F 2 n , and + modular addition. We let • denote the scalar product of bit-strings seen as n-bit vectors.

On Quantum Computing

Although we choose to present in detail the quantum algorithms that we will use for our attacks, most of our results can be obtained by applying them as black boxes. Thus we stress that our results, similarly as other structural attacks on symmetric cryptosystems [START_REF] Kuwakado | Security on the quantum-type even-mansour cipher[END_REF][START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF], can be understood from a high-level perspective, and our attacks do not require specific knowledge of quantum computing. Further details are only required to prove the correctness of the algorithms.

A general presentation of the quantum circuit model can be found in [START_REF] Nielsen | Quantum computation and quantum information[END_REF]. The basic computation units are qubits, two-level quantum systems whose state is represented by a superposition α |0 + β |1 , with amplitudes α and β, which is a normalized vector in C 2 (of norm |α 2 | + |β 2 | = 1). The state of an n-qubit system belongs to C 2 n , its 2 n basis vectors (in the computational basis) are the 2 n n-bit strings.

A quantum algorithm is a sequence of unitary operators of C 2 n , partial measurements, and oracle calls. We say that a function f is queried in superposition if the following unitary operator O f is made available: |x |y → |x |y ⊕ f (x) . Indeed, this operator allows to query f on any quantum state, thus on any superposition of inputs x. This is the standard oracle, equivalent to the phase oracle

O f,± which computes |x → (-1) f (x) |x .
One of the basic unitary operations of the quantum circuit model (quantum gates), and actually the most important one in the algorithms of Section 2.3, is the Hadamard gate H which maps a single qubit |b to 1 √ 2 |0 + (-1) b |1 . By applying Hadamard gates to each individual qubit of an n-bit input, we compute the Hadamard transform, a particular example of Quantum Fourier Transform:

H ⊗n : |x → 1 2 n/2 y∈{0,1} n (-1) x•y |y .
An important property is that the Hadamard transform is involutive. For better readability, we often omit global amplitude factors such as the 1 2 n/2 above, as quantum states are always normalized.

Given a quantum state of the form x α x |x , the measurement operation destroys the state and yields an element x with probability |α x | 2 . Partially measuring the state projects it on a smaller superposition of elements. For a quantum state of the form:

Quantum Algorithms

Our new attacks are based on well-known quantum algorithms: Deutsch's algorithm [START_REF] Deutsch | Quantum theory, the church-turing principle and the universal quantum computer[END_REF], which is a single-bit version of the Deutsch-Jozsa algorithm [START_REF] Deutsch | Rapid solution of problems by quantum computation[END_REF], the Bernstein-Vazirani algorithm [START_REF] Bernstein | Quantum complexity theory[END_REF], Simon's algorithm [START_REF] Simon | On the power of quantum computation[END_REF] and Shor's algorithm [START_REF] Shor | Algorithms for quantum computation: Discrete logarithms and factoring[END_REF]. These algorithms have in common to be based on Fourier sampling, a process in which a quantum Fourier transform is applied before and after a single query to a superposition oracle. They are also amongst the earliest quantum algorithms proven to beat any classical algorithm, and as such are often presented in textbooks (see e.g. [START_REF] Nielsen | Quantum computation and quantum information[END_REF]). However, except for Shor's algorithm, their practical interest remained unclear for a long time. Deutsch's Algorithm. Deutsch's algorithm [START_REF] Deutsch | Quantum theory, the church-turing principle and the universal quantum computer[END_REF] solves Problem 1 with probability 1 using a single query to O f , whereas classically, two queries to f are needed for the same success probability. This constant speedup might seem anecdotal, but is crucial when the same function cannot be queried more than once.

Algorithm 1 Deutsch's algorithm

1: Start from |0 |0 2: Apply a Hadamard gate |0 + |1 3: Apply O f,± (-1) f (0) |0 + (-1) f (1) |1 = (-1) f (0) |0 + (-1) f (0)⊕f (
f is constant (f (0) = f (1)) or balanced (f (0) = f (1)).
Deutsch's algorithm (Algorithm 1) is best presented with a phase oracle O f,± |b = (-1) f (b) |b . It can be seen that upon measurement, the algorithm actually yields the value f (0) ⊕ f (1) (although a single query has been made to f ) whose knowledge solves Problem 1.

Bernstein-Vazirani Algorithm. The Bernstein-Vazirani algorithm [START_REF] Bernstein | Quantum complexity theory[END_REF] offers a polynomial speedup for finding the slope of an affine function over F n 2 .

Problem 2 (Bernstein-Vazirani). Given access to an oracle O f for an affine function f : {0, 1} n → {0, 1}, that is, f (x) = a • x ⊕ b for a, b unknown, find a.

Upon measurement in Algorithm 2, we obtain the unknown a with certainty, using a single query to O f,± , while n queries would be needed classically.

Remark 1. This algorithm can be seen as a generalization of Deutsch's algorithm. Indeed, in the case n = 1, there are only two types of affine functions: f (x) = x ⊕ b (a = 1) and f (x) = b (a = 0), and Bernstein-Vazirani allows to distinguish them in one query.

Simon's Algorithm. Simon's algorithm [START_REF] Simon | On the power of quantum computation[END_REF] solves the problem of distinguishing an injective function from a periodic one. Note that it was the first example of an exponential quantum speedup relatively to an oracle. Problem 3 (Simon). Given access to a function f : {0, 1} n → {0, 1} n for which there exists s such that: ∀x, y, f (x) = f (y) ⇐⇒ y ∈ {x, x ⊕ s}, find s.

In Algorithm 3, at Step 9 in the injective case, the value a obtained before has a single preimage x a . Thus, the current state is y ((-1) return "injective case" 13: else if Y is of rank n -1 then 14:

return "periodic case" and the s orthogonal to Y 15: else 16:

return "failure" 17: end if will grow to a full-rank family. In the periodic case, the value a has exactly two preimages x a and x a ⊕ s which interfere with each other. The current state is

y ((-1) xa•y + (-1) (xa⊕s)•y ) |y = y (-1) xa•y (1 + (-1) s•y ) |y
and only the vectors y orthogonal to s have a non-zero amplitude. Thus, the family Y grows to span the euclidean subspace orthogonal to s. Computing the rank of Y allows to detect the period and solving the linear system Y s = 0 n allows to recover it. Generalizations. Although the original Simon's problem concerns functions without random collisions (that is, we cannot have f (x) = f (y) if x ⊕ y / ∈ {0, s}), it can be shown that the algorithm works as well for random functions having a period, which models the cryptographic problems that we are interested in.

The following simple condition was given in [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF]. For Simon's algorithm to run as expected (i.e., with O (n) queries), it is sufficient for the periodic function f , of period s, to satisfy the following condition:

max t / ∈{0,s} Pr x [f (x ⊕ t) = f (x)] ≤ 1 2 . ( 2
)
That is, f should not admit another "unwanted partial period" t.

In the examples studied in this paper, the condition (2) will be easy to check.

Note that if we had f (x ⊕ t) = f (x) for all x, then t would simply turn the set of periods of f into a vector space of dimension 2. In general, the space of periods could be a vector space of any dimension. An extended version of Simon's algorithm by Brassard and Høyer [START_REF] Brassard | An exact quantum polynomial-time algorithm for Simon's problem[END_REF] allows to recover this whole space in polynomial time.

Finally, another important case is when the output set is smaller than the input set. This was studied in [START_REF] Bonnetain | Tight bounds for Simon's algorithm[END_REF] for Simon's algorithm and [START_REF] May | Quantum period finding is compression robust[END_REF] for periodfinding in general. The results in [START_REF] Bonnetain | Tight bounds for Simon's algorithm[END_REF] show that as long as the functions behave as random (but with the periodicity constraint), then for n input bits, the number of output bits required to run correctly without any cost increase is of order log 2 n. The results in [START_REF] May | Quantum period finding is compression robust[END_REF] show that the output can be hashed down to a single bit, and the algorithms still work up to a constant increase in queries.

Shor's Algorithm. We will use Shor's algorithm [START_REF] Shor | Algorithms for quantum computation: Discrete logarithms and factoring[END_REF] to solve the abelian hidden period problem. It will appear in a "black-box" manner in Section 5.4, and in Section 5.5. We will analyse in detail the behavior of the algorithm on Poly1305.

Problem 4 (Abelian hidden period). Let (G, +) be an abelian group, X a set. Given access to a function f : G → X which is either injective, or periodic (∃s ∈ G, f (s + •) = f (•)), then determine the case and / or find the period.

In particular, we consider G = Z M1 ×. . .×Z M k the product of multiple cyclic groups of known order. For simplicity, and to prepare for Section 5.5, we present the algorithm in the case of Z 2 p for some prime p. Note that f is also periodic over Z p in each of its parameters. This is the typical situation when Shor's algorithm is used to solve the Discrete Logarithm Problem. The periods of f form a twodimensional integer lattice, which is generated by (p, 0) and (-1, s) for some s. In other words, the value of f (x, y) depends only on the value of xs + y mod p. We may assume for simplicity that the function xs + y mod p → f (x, y) is injective.

The algorithm only relies on an efficient implementation of the Quantum Fourier Transform over Z p :

|x → p-1 y=0 exp 2iπ xy p |y ,
which we assume exact. We represent the elements of X on m bits. In Algorithm 4, at Step 4, we can only measure a vector |z, t having a nonzero amplitude. This means that we need:

p-1 x=0 exp 2iπ (z -st)x p = 0 ,
which happens only when (z -st) = 0. In that case, the sum simply gives p.

After renormalization, all vectors |z, t with (z -st) = 0 have the same amplitude 1 √ p , and we will measure one of them taken uniformly at random. If t = 0, we compute s by s = zt -1 mod p. This occurs with probability 1 -1 p .

Attack Scenarios

We consider different attack scenarios throughout this paper.

Algorithm 4 Shor's algorithm 5: Apply a Quantum Fourier Transform again. The state becomes:

1: Start from |0, 0, 0m |0
p-1 z,t=0 p-1 x=0 exp 2iπ zx + (a -xs)t p |z, t = p-1 z,t=0 exp(2iπat/p) p-1 x=0 exp 2iπ (z -st)x p |z, t .
6: Measure a |z, t and return s = zt -1 mod p.

Q1 and Q2 setting. Following [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF][START_REF] Hosoyamada | Quantum demiric-selçuk meet-in-the-middle attacks: Applications to 6-round generic feistel constructions[END_REF][START_REF] Bonnetain | Quantum attacks without superposition queries: The offline Simon's algorithm[END_REF], we will adopt the Q1 / Q2 terminology to classify quantum attacks on symmetric schemes. Note that these models have alternative names, for example "quantum chosen-plaintext attack" (qCPA) is used for "Q2" in [START_REF] Ito | Quantum chosenciphertext attacks against feistel ciphers[END_REF][START_REF] Cid | Quantum cryptanalysis on contracting feistel structures and observation on related-key settings[END_REF]. In the Q1 setting, the adversary is given only classical encryption or decryption query access to black-boxes. In the Q2 setting, the adversary is given quantum or superposition access, in the sense that a blackbox E K becomes a quantum oracle O E K . This is the case for all the attacks of this paper.

The study of quantum attacks on symmetric schemes in the Q2 setting was sparkled by seminal work of Kuwakado and Morii [START_REF] Kuwakado | Quantum distinguisher between the 3-round feistel cipher and the random permutation[END_REF][START_REF] Kuwakado | Security on the quantum-type even-mansour cipher[END_REF], who showed that the 3-round Luby-Rackoff construction and the Even-Mansour cipher became insecure if exposed to superposition queries. More precisely, they can use Simon's algorithm to respectively distinguish the construction and recover the key of the cipher in polynomial time, while classical proofs of security exist.

Attacks based on period-finding. Since these earlier results, many works have extended the reach of Q2 attacks [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF][START_REF] Bonnetain | Quantum key-recovery on full AEZ[END_REF][START_REF] Leander | Grover meets Simon -quantumly attacking the FXconstruction[END_REF][START_REF] Bonnetain | On quantum slide attacks[END_REF][START_REF] Dong | Quantum attacks on some feistel block ciphers[END_REF][START_REF] Guo | Attacks on beyond-birthday-bound macs in the quantum setting[END_REF]. However, the attack strategy has remained the same. A hidden structure is embedded in the construction to be attacked, so that f (E K (x), x) for some choice of combination f , is a periodic function of x; or that a shift exists between f (E K (x), x) and g(E K (x), x). The recovery of this hidden period or shift, which is secret material, then leads to a break. We can cite some examples:

Against the Even-Mansour construction [START_REF] Kuwakado | Security on the quantum-type even-mansour cipher[END_REF]:

E K (x) = K 2 ⊕ Π(x ⊕ K 1 )
for a random public permutation Π and two keys K 1 , K 2 . One has:

E K (x) ⊕ Π(x) = E K (x ⊕ K 1 ) ⊕ Π(x ⊕ K 1 )
which leads to a recovery of K 1 in O (n) queries and O n 3 computations. Against CBC-MAC with two blocks [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF]: It can be defined as:

CBC-MAC(y, x) = E K • E K x ⊕ E K (y) ,
where K and K are two keys that will remain unknown to the adversary. Due to the structure of CBC-MAC, one can take two arbitrary values α 0 , α 1 , and define the function:

F : {0, 1} × {0, 1} n → {0, 1} n (b, x) → CBC-MAC(α b , x) (3)
We have then that

F (b, x) = F (b ⊕ 1, x ⊕ E K (α 0 ) ⊕ E K (α 1 )). Thus F has a hidden boolean period 1 E K (α 0 ) ⊕ E K (α 1 ). Having obtained the internal value E K (α 0 ) ⊕ E K (α 1 )
, we can query the tag of any message starting with block α 0 , and then forge a message starting with α 1 with the same tag.

Constructions based on IVs. We consider two types of constructions with quantum access: some make use of an initialization value (IV, sometimes also named a nonce) and some do not. In the IV case, we consider that the IV is a classical value, chosen randomly before each oracle query, and not repeated. This model follows from the idea that the IV is not controlled by the adversary, and it can serve as an intermediate between the classical setting and a (much) stronger model in which the adversary would completely (and quantumly) control the IVs.

In fact, the latter case does not seem to have been studied so far in quantum security. Well-known notions such as IND-qCPA [START_REF] Boneh | Secure signatures and chosen ciphertext security in a quantum computing world[END_REF] rely on classical randomness, and many modes of operation have been proven secure in this model [START_REF] Anand | Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation[END_REF][START_REF] Bhaumik | QCB: efficient quantum-secure authenticated encryption[END_REF].

In the classical setting, many MAC constructions have a security that relies on the non-repetition of IVs, for example the MAC of OCB [START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF]. The same happens in the quantum setting, since the MAC of QCB [START_REF] Bhaumik | QCB: efficient quantum-secure authenticated encryption[END_REF] has been proven secure under quantum queries with classical non-repeated IVs. Unforgeability. The first notion of quantum unforgeability for MACs was defined by Boneh and Zhandry [START_REF] Boneh | Quantum-secure message authentication codes[END_REF]. We will name it plus-one unforgeability (PO), following [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF]. The idea is that an adversary making q quantum queries to the construction, where q is polynomial, should not be able to produce q + 1 valid {message, tag} pairs. A more recent definition is blind-unforgeability (BU), proposed in [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF]. It is strictly stronger than PO-unforgeability. In this paper, we will give several quantum forgery attacks that break the PO notion, thereby also breaking BU. Quantum PRFs. A quantum pseudorandom function (qPRF) is a family of functions F K , indexed by a key space K, such that no quantum adversary making queries to an oracle O f can distinguish efficiently between a function F K , with K drawn uniformly at random, and a truly random function. It is shown respectively in [START_REF] Boneh | Quantum-secure message authentication codes[END_REF] and [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF] that a qPRF is also a quantum-secure deterministic MAC by the PO and BU definitions. Therefore, any function that is not POunforgeable is also not a secure qPRF. To the best of our knowledge, the only classical symmetric construction that has been proven quantum-secure as a deterministic MAC, the Cascade / NMAC / HMAC construction [START_REF] Song | Quantum security of NMAC and related constructions -PRF domain extension against quantum attacks[END_REF], is also a qPRF.

A Quantum Attack on OCB3

We detail the Q2 attack on the MAC of OCB3 from [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF]. As the other previous works recalled above, this attack relies on a Boolean period-finding problem. Specification. OCB3 is an IV-based mode of authenticated encryption with associated data (AEAD), based on a block cipher [START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF]. As OCB stands for offset codebook, the scheme relies on the definition of offsets that are dependent on the key and change between each block. We will focus on the authentication tag of OCB3 (see Figure 1). Our considerations are independent on the exact value of the offsets, and apply to all versions of OCB, but we use OCB3 as a concrete example. Forgery Attack with Simon's Algorithm. Kaplan et al. showed in [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF] how to forge authentication tags using Simon's algorithm. The idea is to query the tag of an empty message with two AD blocks A 0 , A 1 = x:

x

→ E K (∆ IV ) ⊕ E K (∆ 0 ⊕ x) ⊕ E K (∆ 1 ⊕ x) .
One can then remark that this function of x is periodic, of period ∆ 0 ⊕ ∆ 1 , independent of the IV, and only on the secret key K. Although the function changes at each query (since the IV changes), the period is always the same and Simon's algorithm allows to recover it with O (n) superposition queries. (For the same reason, we could use a non-empty message, and even different messages between the queries.) Once ∆ 0 ⊕ ∆ 1 has been obtained, one can then query the tag of any pair of AD blocks A 0 , A 1 and forge the tag of A 1 , A 0 .

Remark 2. It is easy to check that Equation ( 2) is satisfied in practice. If it wasn't, then the existence of an unwanted partial period t:

Pr x [f (x ⊕ t) = f (x)] ≥ 1 2 ,
would imply a higher-order differential of probability greater than 1 2 for E K , which is impossible if E K is a pseudorandom permutation (in other words, E K would suffer from a classical break).

The Quantum Linearization Attack: Algorithmic Ideas

In this section, we present the algorithmic ideas underlying our new quantum linearization attack. To that end, we keep the example of OCB3 [START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF] introduced in Section 2.5. We explain a new way to forge with Q2 queries. The extensions and applications of this new idea will be explored in the next sections.

Note that to the best of our knowledge, this is the first application of the Deutsch and Bernstein-Vazirani algorithms for forgery attacks.

Attack on ΘCB with Deutsch's Algorithm

The attack of Section 2.5 works only because of the offsets. In fact, the existence of a controlled value (here x) XORed to a secret (here the offsets) has been so far a prerequisite of all Q2 attacks.

Here we present a forgery attack against the mode ΘCB3 [START_REF] Rogaway | Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC[END_REF][START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF], which is a more abstract version of OCB3 in which the block cipher E K is replaced by a tweakable block cipher (a family of independent block ciphers E K,t indexed by a tweak t). This is shown in Figure 2.

Here, the tweaks t 0 , . . . , t j , t * form an arbitrary sequence of distinct values, that depend only on the block index; the tweak t is the only one dependent on the IV. Again, we consider an empty message, but this time a single AD block that is either 0 or 1. We define i functions which truncate the output of such a call to the ith bit:

F i : {0, 1} → {0, 1} b → Trunc i ( E K,t0 (b) ⊕ E K,t (0))
.

The functions F i change at each new superposition query (because the IV intervenes in E K,t (0)). Thus we need the ability to compute a query to F i using a single query to the untruncated mode itself. This is fortunately easy to do so using the truncation technique of [START_REF] Hosoyamada | Quantum demiric-selçuk meet-in-the-middle attacks: Applications to 6-round generic feistel constructions[END_REF].

With this single query, Deutsch's algorithm allows to recover the value:

Trunc i ( E K,t0 (0) ⊕ E K,t (0)) ⊕ Trunc i ( E K,t0 (1) ⊕ E K,t (0)) = Trunc i ( E K,t0 (0) ⊕ E K,t0 (1)
) , and within n queries and uses of the algorithm, we can obtain the full value

E K,t0 (0) ⊕ E K,t0 (1)
.

We can now forge valid messages as follows: we query a message with 0 as the first block, we XOR E K,t0 (0) ⊕ E K,t0 (1) to the tag, and we have obtained the tag of the same message with 1 replacing the first block. This works for any block and for any pair of messages.

This attack shows that XORing with an IV-dependent value, although it provides sufficient protection against forgeries in the classical setting (since ΘCB has a security proof), does not in the quantum setting.

Interestingly, it is possible to protect against this attack by using the IV in the TBC calls, as done by Bhaumik et al. in [START_REF] Bhaumik | QCB: efficient quantum-secure authenticated encryption[END_REF]. While this simple modification has practically no incidence on the classical security of the mode, it is crucial to obtain unforgeability in the quantum setting.

Another Example: XOR-MACs. In [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF], two XOR-MAC constructions are defined, which can be attacked with Deutsch's algorithm. They are both based on a pseudorandom function F K and an IV. The first one, XMACR (randomized XOR scheme), considers that the IV is drawn uniformly at random, and the second one, XMACC (counter-based XOR scheme) that it is maintained as a counter. Both compute:

MAC(m 1 , . . . , m ; IV ) = F K (0 IV ) ⊕ 1≤i≤ F K (1 i m i ) .
Then, since the contribution of the IV is only XORed, forgeries can be made.

Using the Bernstein-Vazirani algorithm

We propose here a generalization of the previous attack, with longer queries. We now consider functions of the form

g 1 (x 1 ) ⊕ g 2 (x 2 ) ⊕ • • • ⊕ g (x ) ⊕ C
with, as before, a C that is independent from all x i . Now, we can choose some arbitrary α 0 i and α 1 i , and consider the function

F j : {0, 1} → {0, 1} (b 1 , . . . , b ) → Trunc j i=1 g i (α bi i ) ⊕ C ,
It is easy to see that this function is affine: indeed, if we change the value of b i , then we add Trunc j g i (α 0 i ) ⊕ g i (α 1 i ) to the output. Hence, if we apply the Berstein-Vazirani algorithm, in one query, we recover the values of the Trunc j g i (α 0 i ) ⊕ g i (α 1 i ) , for all i. Next, it suffices to repeat the algorithm for each bit of the output to obtain the value of all the g i (α 0 i ) ⊕ g i (α 1 i ). This technique can be applied to OCB3 / ΘCB3, as the tag is a function of the form

i g k i (AD i ) ⊕ f k (IV, M )
Hence, we can attack multiple blocks of associated data at once.

Attacking any XOR of permutations

The main limitation of the previous attacks is that they need a direct access to the linear combination of independent blocks. In this section, we overcome this limitation with an attack that leverages linear combinations of permutations in a more intrinsic way, using Simon's algorithm in a novel fashion. We consider a MAC construction that processes m > n message blocks x 1 , . . . , x m by pushing the x i through independent TBC calls E K,i , XORing the result and applying an IV-dependent function afterwards.

IV, (x 1 , . . . , x m ) → f K IV, 1≤i≤m E K,i (x i ) .
Remark 3. We write the attack with a TBC, i.e., a family of independent block ciphers E K,T indexed by a secret key K and a public tweak T . This is to emphasize the application of our attack to parallelizable MACs; however, the attack works in the same way if we replace the independent block ciphers by independent functions.

In the case of ΘCB, the definition of f K is simple, since it only XORs the IV-and the AD-dependent parts. But the attack of Section 3.2 does not apply anymore if f K is a pseudorandom function. This will be the case of our new attack, which is why it will apply to many MAC constructions. Quantum Attack. First of all, it is easy to see that if the E K,i are independent block ciphers, and if f K is a pseudorandom function family, then this construction is a classically unforgeable MAC: this is the security of ΘCB3.

Our attack in the quantum setting starts from the same idea as above (Section 3.2): we query the MAC with arbitrary blocks taking two values:

x 1 = b 1 ||0 n-1 , . . . , x m = b m ||0 n-1
, where x = b 1 . . . b m forms an m-bit input (in the remaining of this paper, we will write the n -1 zeroes used for completion as a single 0). We will put x in superposition, and so, there will be only "one superposed bit" in each individual block input.

One then observes that E K,1 (x 1 ) ⊕ . . . ⊕ E K,m (x m ) is an affine function of x:

F (x) := E K,1 (x 1 ) ⊕ . . . ⊕ E K,m (x m ) = i b i E K,i (0) ⊕ E K,i (1) ⊕ E K,i (0) .
More precisely, if we identify bit-strings with boolean column vectors, F (b 1 . . . b m ) is equal to:

( E K,1 (0) ⊕ E K,1 (1)) • • • ( E K,m (0) ⊕ E K,m (1)
)

Mm ×    b 1 . . . b m    ⊕ i E K,i (0)
.

The matrix M m has n rows and m columns, so when m ≥ n + 1, its kernel is nontrivial. This means there will exist a non-zero m-bit boolean vector α such that:

( E K,1 (0) ⊕ E K,1 (1)) • • • ( E K,m (0) ⊕ E K,m (1)) × α =    0 . . . 0    ,
and for all such vectors α, seen as m-bit strings, we have:

F (x ⊕ α) = M m × (x ⊕ α) ⊕ i E K,i (0) = F (x) .
In other words, this function F hides a subgroup of (F 2 ) m generated by all the vectors α satisfying the condition above (it is easy to see that they indeed form a group). Thus, F satisfies the promise of Simon's algorithm: by making a single superposition query, we can find y such that y • α = 0 for such an α, and furthermore, as Brassard and Høyer showed [START_REF] Brassard | An exact quantum polynomial-time algorithm for Simon's problem[END_REF], we can even recover the full subspace of periods with a polynomial number of quantum queries to F . However, in our model, we cannot query F directly and we have instead access to: f K (IV, F (x)), where IV changes at each query. The key remark is that the hidden subgroup is unchanged, since F is independent of the IV . This assumption is enough to allow Simon's algorithm and its extensions to work.

Remark 4 (Smaller m). Some period might still arise if m ≤ n. Indeed, if m = n, there will be a non-trivial period with probability around 1 -1/e. This quickly decays for smaller m.

Remark 5 (Unwanted collisions). Since the "inner" function F is affine, it does not contain any unwanted collisions. If F (x ⊕ α) = F (x) for some α and x, then this holds as well for all x. However, unwanted collisions might occur in f K (IV, •).

Assuming that M m is full rank, we can express the probability of unwanted partial periods for f K (IV, F (•)) as the probability of such unwanted collisions for f K (IV, •):

p = max t,Mm×t =0 Pr x∈{0,1} [f K (IV, F (x ⊕ t)) = f K (IV, F (x))] = max t,Mm×t =0 Pr x∈{0,1} [f K (IV, F (x) ⊕ M m × t) = f K (IV, F (x))] = max u =0 Pr x∈{0,1} [f K (IV, F (x) ⊕ u) = f K (IV, F (x))] = max u =0 Pr y∈{0,1} n [f K (IV, y ⊕ u) = f K (IV, y)] .
Even if the output is truncated to less than n bits, p ≤ 1 2 follows trivially from the fact that f K (IV, •) should not admit a differential of such high probability. To conclude, it is precisely the fact that the termination function f K (IV, •) is a good PRF, and does not admit an interfering period, that allows to apply easily Simon's algorithm in our case. Thus, by making a polynomial number of Q2 queries to the MAC construction, we can obtain such an α. This allows to create forgeries as follows. Forgeries without IVs. We first make n queries to find a valid α with Simon's algorithm (with constant probability of success). Then, the knowledge of this α allows us, for each tag x queried, to output a forged tag x ⊕ α. Thus we can double the number of tags that we produce compared to the number of queries we make. This breaks the PO notion as soon as, making r + n queries, we have 2r ≥ r + 1 + n tags, thus with 2n + 2 queries in total. Note that by breaking PO, we are actually showing that the MAC construction is not a qPRF (if it were, it would be PO-secure). Forgeries with IVs. As long as the IV (or nonce) is used only in the keyed post-processing, we can recover a value α and run the attack as above. We will indeed output more triples {IV, message, tag} than the number of queries made, although some IVs are repeated in the outputs. Universal Forgeries. Instead of taking the arbitrary values b i ||0 in message blocks, we can take any pair of values for each of them. That way, we can even start from any m-block message y 1 , . . . , y m , and then define a function of x = b 1 . . . b m that inputs y i in block i if b i = 1 and an arbitrary value 0 otherwise. Using Simon's algorithm, we will find a subset of the y i such that the E K,i (y i ) have the same XOR as the E K,i (0). Hence, we can produce a new message having the same tag as y 1 , . . . , y m . This works as soon as m ≥ n (there just needs to be enough message blocks for our attack). parallelizable beyond birthday-bound (BBB) MACs, although they have a larger internal state. Here is a summary of MACs attacked in this section (usually in time quadratic in the internal state size n), whose previous best quantum attack was exponential:

LightMAC [START_REF] Luykx | A MAC mode for lightweight block ciphers[END_REF], LightMAC+ [START_REF] Naito | Blockcipher-based MACs: beyond the birthday bound without message length[END_REF], Deoxys [38], ZMAC [START_REF] Iwata | ZMAC: A fast tweakable block cipher mode for highly secure message authentication[END_REF],

PMAC TBC3k [START_REF] Naito | Full PRF-secure message authentication code based on tweakable block cipher[END_REF] On the contrary, here are some MACs on which, to the best of our knowledge, our attack does not apply: SUM-ECBC [START_REF] Yasuda | The sum of CBC MACs is a secure PRF[END_REF], 2K-ECBC-Plus [START_REF] Datta | Double-block hash-then-sum: A paradigm for constructing BBB secure PRF[END_REF], 3kf9 [START_REF] Zhang | 3kf9: Enhancing 3GPP-MAC beyond the birthday bound[END_REF]. The best Q2 attacks on these remain exponential-time (usually

O 2 n/2 or O 2 k/2
where n is the internal block size, and k the key size).

First Examples

We will consider MAC designs with or without IVs or nonces. When there is no IV, then the attack of Section 3.3 breaks them in the PO notion. This also shows that even though they usually yield classical PRFs, these constructions are not quantum-secure PRFs. When there is an IV, the MAC may be insecure as a PRF but still secure as a MAC (since the IV is changed at each query, and not repeated). Despite that, our attack may still yield a break, as we showed in the example of ΘCB above. In that case, the period that is recovered with Simon's algorithm is independent of the IV, and can be reused to forge a new valid (message, tag) pair under any previously queried IV. LightMAC. LightMAC [START_REF] Luykx | A MAC mode for lightweight block ciphers[END_REF] is based on an n-bit block cipher and separates the message in blocks of n -s bits, where s ≤ n/2 is some parameter that limits the maximal message size. The function is the following:

LightMAC(m 1 , . . . , m ) = Trunc t E K2 (m 10 * ) ⊕ -1 i=1 E K1 (i s m i )
,

where the i s are s-bit constants. Calling LightMAC with single-bit blocks and using Simon's algorithm, we immediately obtain a sequence of indices j 1 , . . . , j v such that E K1 (i j1 1) ⊕ . . . ⊕ E K1 (i jv 1) = E K1 (i j1 0) ⊕ . . . ⊕ E K1 (i jv 0) and thus, we can produce existential forgeries, and universal forgeries of messages with a linear number of blocks.

Deoxys. Due to the similarity of its MAC with ΘCB, our attack applies to all versions of Deoxys-II [38], one of the finalists of the CAESAR competition (it also applies to Deoxys-I).

Protected Counter Sums. In [START_REF] Bernstein | How to stretch random functions: The security of protected counter sums[END_REF], Bernstein defined the protected counter sum construction, which uses a pseudorandom function f : {0, 1} d+c → {0, 1} c to build a pseudorandom function with message space of at most 2 c -1 blocks of length d:

f (m 1 , . . . , m ) = f (0 f (1 m 1 ) ⊕ . . . ⊕ f ( m )) .
The quantum linearization attack essentially shows that this construction, while classically sound, does not yield a quantum-secure pseudorandom function (even if f itself is a qPRF).

Attacks on BBB MACs

We consider here a variant of the previous construction typically used to design Beyond Birthday MACs. We focus on deterministic MACs, but as before, the same forgery attacks apply if IVs are used in the final processing of the tag.

In the most generic setting, the input x 1 , . . . , x m is processed with a TBC E K,i , then combined in two different ways:

(x 1 , . . . , x m ) → f K i E K,i (x i ), i 2 i E K,i (x i ) .
Here f K is a function whose details are insignificant for our attack.

A similar observation as above applies. By calling the MAC in superposition with messages of the form x = b 1 ||0, . . . , b m ||0, we will obtain a periodic function. Indeed, there are now two matrices M m and M m with n rows and m columns, and two column vectors C, C such that:

F (x) = F (b 1 , . . . , b m ) := f K   Mm ×    b 1 . . . b m    ⊕ C, M m ×    b 1 . . . b m    ⊕ C    ,
where the columns of M m correspond to E K,i (0) ⊕ E K,i (1) and the columns of

M m correspond to 2 i ( E K,i (0)⊕ E K,i (1)
). Then, as soon as m ≥ 2n+1, the matrix: M m M m has 2n rows and at least 2n + 1 columns, and so, it has a non-trivial kernel. There exists a non-zero vector α such that

M m α = M m α =    0 . . . 0    .
This α is a boolean period of F , for which M AC(x ⊕ α) = M AC(x). Again, the further we increase m, the bigger the subspace of periods will become. This whole space can be recovered using Brassard and Høyer's extension of Simon's algorithm [START_REF] Brassard | An exact quantum polynomial-time algorithm for Simon's problem[END_REF] in polynomial time. Related works. In [START_REF] Guo | Attacks on beyond-birthday-bound macs in the quantum setting[END_REF], Guo, Wang, Hu and Ye used combinations of Simon's algorithm and Grover's algorithm to design forgery attacks on many BBB MACs, in the Q2 setting. With this technique, they found two things. First, staterecovery attacks of complexity O 2 n/2 where n is the block size of the underlying block cipher, and the internal state is 2n bits in total. This comes from the fact that the same input blocks are processed in two branches separately. The standard use of Simon's algorithm, where a controlled message block x is XORed to an uncontrolled value, allows only to recover this value in one of the branches.

The n bits on the other branch have to be guessed with a Grover search, and so, the attack is a Grover-meets-Simon [START_REF] Leander | Grover meets Simon -quantumly attacking the FXconstruction[END_REF] instance. And next, partial key-recovery attacks for parallelizable MACs, of complexity O 2 k/2 , where k is the partial key size (the total key size ranges from 3k to 5k). They consist in guessing part of the key and breaking the MAC by using a symmetry of the branches. To these attacks correspond classical partial key-recoveries of complexity O 2 k . Our attack has completely different requirements and offers different results. We need longer messages (of roughly 2n blocks in this setting), but when it applies, the complexity is always polynomial. Note that there are constructions targeted by Guo et al., such as SUM-ECBC, that we cannot attack since the blocks are processed sequentially and not linearly in parallel as we require. LightMAC+. LightMAC+ [START_REF] Naito | Blockcipher-based MACs: beyond the birthday bound without message length[END_REF], as its name suggests, is a BBB extension of LightMAC.

As shown in Figure 3, it processes message blocks m 1 , . . . , m as follows:

LightMAC+(m 1 , . . . , m ) = E K1 (E K (1 s m 1 ) ⊕ . . . ⊕ E K ( s m )) ⊕ E K2 (2 -1 E K (1 s m 1 ) ⊕ . . . ⊕ 2 0 E K ( s m ) ,
where the multiplications are done in the finite field F 2 n . This falls into our framework and is thus forgeable in quadratic time (about 2n blocks are required to embed a vector space in both branches, and this can then be recovered in a linear number of queries). PMAC+. It is a double-block hash-then-sum construction similar to LightMAC+, which also falls into our framework. In full generality, there are three keys K 1 , K 2 , K 3 . The message blocks m 1 , . . . , m are processed as follows:

y i = m i ⊕ 2 i E K1 (0) ⊕ 2 2i E K1 (1
) and then:

PMAC+(m 1 , . . . , m ) = E K2 (E K1 (y 1 ) ⊕ . . . E K1 (y )) ⊕ E K3 2 E K1 (y 1 ) ⊕ . . . 2 E K1 (y ) .
The masking by 2 i E K1 (0) ⊕ 2 2i E K1 (1) simply makes the processing of each block different, but this is insignificant for our attack. By recovering a period, we can create forgeries and break PMAC+ as a qPRF. Note that both LightMAC+ and PMAC+ were classically proven secure up to 2 3n/4 queries [START_REF] Kim | Tight security bounds for double-block hash-then-sum MACs[END_REF]. Besides, increasing the number of parallel branches may have consequences on the bound, but only increases the complexity of our attack by a constant factor. We considered here three-key versions, but of course, the twoand one-key versions [START_REF] Datta | Double-block hash-then-sum: A paradigm for constructing BBB secure PRF[END_REF][START_REF] Datta | Single key variant of PMAC Plus[END_REF] are similarly broken.

Other MACs

LAPMAC. LAPMAC was defined in [START_REF] Minematsu | A lightweight alternative to PMAC[END_REF]. The definition depends on some parallelization parameter µ. Successive chunks of µ message blocks will be processed in parallel through the block cipher E K (except the last one), then some tweak function depending on their index in the chunk. The results are XORed and encrypted again, before being XORed to the next chunk of µ message blocks, etc. When µ ≥ n, LAPMAC applied to n message blocks becomes similar to LightMAC or PMAC, and there is sufficient parallelization to perform our attack. Whether a variant of the attack applies for smaller values of µ is an interesting question. ZMAC. ZMAC [START_REF] Iwata | ZMAC: A fast tweakable block cipher mode for highly secure message authentication[END_REF] is a MAC that uses a TBC. It is based on the ZHASH doubleblock hash construction followed by a finalization function. We can simply focus on the abstraction ZHASH (see Fig. 5 in [START_REF] Iwata | ZMAC: A fast tweakable block cipher mode for highly secure message authentication[END_REF]):

ZHASH(X 1 , X 1 r , . . . , X l , X l r ) = i 2 l+1-i E i,X i r K (X i ), i X i r ⊕ i E i,X i r K (X i ) ,
where E t K is E K called with a tweak t. If we make the tweak inputs constant, then the construction is similar to PMAC+ with a TBC, and different random keyed permutations for each block. Our attack applies as well. PMAC with a TBC. Naito [START_REF] Naito | Full PRF-secure message authentication code based on tweakable block cipher[END_REF] showed that PMAC+ used with a TBC could achieve full PRF security (up to O (2 n ) queries). In this variant, the message blocks are processed independently with different tweaks. This has no consequence on our attack, which requires only O (n) queries of about 2n blocks each.

Attacks on MACs based on Universal Hashing

In this section, we focus on some attacks on MACs based on universal hashing. In particular, we give polynomial-time attacks on PolyMAC [START_REF] Iwata | Stronger security variants of GCM-SIV[END_REF], GCM-SIV2, and we give a superposition attack on Poly1305 requiring about 32 queries.

Overview

Universal hash functions were introduced by Carter and Wegman in 1977 [START_REF] Carter | Universal classes of hash functions[END_REF] in order to build secure MACs, and are now used in many MAC constructions and security proofs. The first proposal by Wegman and Carter was to hash the message and to encrypt the result with a one-time-pad. This defines a MAC with information-theoretic security, but the use of a one-time-pad is impractical, and it was soon suggested to replace it with the output of a PRF, i.e., to replace the one-time-pad by counter-mode encryption. This results in the Wegman-Carter construction used in GCM and Poly1305-AES: M → H K1 (M ) ⊕ F K2 (N ) where F is a secure pseudorandom function family, and H an almost-XOR-universal hash function family.

Universal hash functions and MAC constructions

An almost-XOR-universal hash function family is a family of function H from {0, 1} * to {0, 1} n indexed by a key K ∈ K such that:

∀m = m , ∀d ∈ {0, 1} n , #{K ∈ K : H K (m) ⊕ H K (m ) = d} ≤ ε#K
The most widely used universal hash function construction is polynomial hashing. The input message is interpreted as the coefficients of a polynomial in a field F, and the polynomial is evaluated on the hash key:

PolyHash K : F F m 1 , m 2 , . . . m → i=1 K i m i
Block cipher-based constructions such as the OCB3 MAC can also be analysed as universal hashing-based, using i E K (A i ⊕ ∆ i ) as a universal hash function.

There are many different ways to turn a universal hash function into a MAC:

One-time-MAC: H K (M ). If the universal hash function satisfies extra properties (it must be strongly universal), it can be used directly as a MAC, if a new key is used for each message. This construction is used in ChaCha20-Poly1305, Grain128A and Grain128AEAD [START_REF] Hell | Grain-128 AEAD a lightweight AEAD streamcipher[END_REF]. Wegman-Carter: H K1 (M ) ⊕ F K2 (N ). The Wegman-Carter construction is a nonce-based MAC using a universal hash function H and a PRF F . It authenticates several messages using the same key, as long as the nonce N is not repeated (the security is lost as soon as two different messages are authenticated with the same key). This construction is used in GMAC. More generally, the construction H(M ) F (N ) with a group operation and F almost--universal is a secure MAC. This construction is used in Poly1305-AES. Hash-then-PRF: F K2 (H K1 (M )). The hash-then-PRF construction builds a deterministic MAC from a universal hash function H and a PRF F . The PolyMAC construction discussed below follows this design. More generally, security proofs for several block cipher-based MACs consider the MAC as following the hash-then-PRF construction; in particular this is the case of double-block hash-then-sum constructions [START_REF] Datta | Double-block hash-then-sum: A paradigm for constructing BBB secure PRF[END_REF]. WMAC: F K2 (H K1 (M ) N ). WMAC [START_REF] Black | MAC reforgeability[END_REF] is a generalization of the hashthen-PRF construction using an additional nonce input N to the PRF. This requires a PRF with a larger input, but provides higher security when nonces are unique, without breaking down when they are repeated. EWCDM: E K3 (E K2 (N ) ⊕ N ⊕ H K1 (M )). The Encrypted Wegman-Carter with Davies-Meyer construction [START_REF] Cogliati | EWCDM: an efficient, beyond-birthday secure, noncemisuse resistant MAC[END_REF] is an alternative construction offering high security with a nonce with graceful degradation when nonces are repeated. Instead of using a 2n-bit PRF as in WMAC, it uses two calls to an n-bit block cipher.

Attacking Wegman-Carter MACs

All MACs following the Wegman-Carter construction are exposed to the attack using Deutsch's algorithm that we presented in Section 3.1. More precisely, an IV-respecting quantum adversary can retrieve the value of H K1 (M 1 ) ⊕ H K1 (M 2 ) for an arbitrary pair of messages M 1 , M 2 . He can then repeatedly query the tag of M 1 under new nonces, and produce corresponding valid tags for M 2 . When using the generalization with a group operation instead of ⊕, this simple attack does not apply. In particular, Poly1305-AES uses a modular addition and cannot be broken with Deutsch's algorithm, but we will show a dedicated attack in Section 5.5, using the fact that it is based on polynomial hashing.

Attacking Algebraic Universal Hash Functions

We can apply our linearization attack to MACs that reuse the same hash key for several messages, whether deterministic (like hash-then-PRF), or nonce-based (like Wegman-Carter, WMAC, and EWCDM). Indeed, it is enough for us to linearize the function H, and the attack applies regardless of the security of the operations that are computed afterwards, even if they involve a nonce.

Many Universal Hash Functions based on algebraic operations have a strong linear structure. In particular, polynomial hashing is a linear function of the message, making it a natural target for Simon's algorithm (in characteristic 2) or Shor's algorithm (in general). We describe concrete attacks against a few constructions.

PolyMAC. PolyMAC [START_REF] Datta | Double-block hash-then-sum: A paradigm for constructing BBB secure PRF[END_REF] is a double block hash-then-sum construction based on polynomial hashing. The generic construction uses two hashing keys K 1 , K 2 and two encryption keys K 3 , K 4 . For an -block message m 1 , . . . , m , this gives:

PolyMAC(m 1 , . . . , m ) = E K3 K 1 m ⊕ K 2 1 m -1 ⊕ . . . ⊕ K 1 m 1 ⊕ E K4 K 2 m ⊕ K 2 2 m -1 ⊕ . . . ⊕ K 2 m 1 .
If a single branch is used, then this looks like the GMAC construction [START_REF] Mcgrew | The security and performance of the galois/counter mode (GCM) of operation[END_REF] (but without a nonce), using polynomial hashing. GMAC was already attacked in [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF] due to its similarities with CBC-MAC, and the fact that the nonce did not influence the embedded hidden shift. However, we can use our attack here. By taking -block message inputs with blocks 0 or 1, we will recover with Simon's algorithm a period b 1 • • • b such that:

i b i K i 1 = 0 and i b i K i 2 = 0 .
This immediately allows a forgery attack, but also, we can recover multiple such periods and solve the corresponding equations to recover K 1 and K 2 .

PolyMAC with Modular Additions. Interestingly, our attack applies as well when the polynomial hashing does not use XORs, but modular additions (modulo some value M ). However, Simon's algorithm has to be replaced by Shor's algorithm. Note that this is specific to polynomial hashing, and does not apply to LightMAC or PMAC-style constructions in general.

We can define:

PolyMAC+(m 1 , . . . , m ) = E K3 K 1 m + K 2 1 m -1 + . . . + K 1 m 1 mod M ⊕ E K4 K 2 m + K 2 2 m -1 + . . . + K 2 m 1 mod M .
In that case, we can remark that there exists periods a 1 , . . . , a such that:

K 1 a 1 + . . . + K 1 a mod M = 0 and K 2 a 1 + . . . + K 2 a mod M = 0 .
More precisely, these periods form a lattice in Z M , and for all of them, we have:

∀m 1 , . . . , m , PolyMAC+(m 1 + a 1 , . . . , m + a ) = PolyMAC+(m 1 , . . . , m ) .
Thus, the generalization by Mosca and Ekert [START_REF] Mosca | The hidden subgroup problem and eigenvalue estimation on a quantum computer[END_REF] of Shor's algorithm allows to retrieve the full lattice of these periods: we can not only forge, but also recover the internal hashing keys. GCM-SIV2. This is a double-block variant of GCM-SIV defined in [START_REF] Iwata | Stronger security variants of GCM-SIV[END_REF]. The tag generation combines two independent polynomial hashes (with two keys K 1 , K 2 ) with a keyed-dependent combination function F K , of which we shall not study the details. This mode is nonce-based. With an empty associated data, the tag is computed as follows:

GCM-SIV2 -MAC(N, m 1 , . . . , m ) = F K (N ⊕ H K1 (m 1 , . . . , m ), N ⊕ H K2 (m 1 , . . . , m )) ,
where H K1 and H K2 are polynomial hashes (this would be similar for the tag of an empty message, replacing M by the associated data). Thus, although the MAC is nonce-dependent, it falls into our framework since the periods of the polynomial hashes remain independent of N . Other algebraic hashing constructions. There are many alternatives to polynomial hashing based on field operations. Several constructions are linear, such as the dot product construction, and Toeplitz hashing [START_REF] Krawczyk | New hash functions for message authentication[END_REF]. 5Some other constructions can be linearized using specially crafted messages. NMH * [START_REF] Halevi | MMH: software message authentication in the gbit/second rates[END_REF]. The NMH * universal hash function is defined as:

NMH * (M ) = (m 2i + K 2i )(m 2i+1 + K 2i+1 ) mod p
If we consider messages with blocks with an even index set to arbitrary constants, we obtain a linear function of the odd message blocks. Therefore, Shor's algorithm can break MACs based on this hash function that reuse the hash key.

BRW Hashing [START_REF] Bernstein | Polynomial evaluation and message authentication[END_REF]. The BRW universal hash function is based on a class of polynomials that can be evaluated with /2 multiplications with inputs, using a single key. The construction is defined recursively, depending on the input length:

• BRW K () = 0 • BRW K (m 1 ) = m 1 • BRW K (m 1 , m 2 ) = m 1 K + m 2 • BRW K (m 1 , m 2 , m 3 ) = (K + m 1 ) (K 2 + m 2 ) + m 3 • BRW K (m 1 , m 2 , . . . m ) = BRW K (m 1 , m 2 , . . . m t-1 ) (K t + m t )+ BRW K (m t+1 , m t+2 , .
. . m ) with t a power of 2, and 4 ≤ t ≤ n < 2t.

For instance, with 8 inputs, we obtain

(K+m 1 ) (K 2 +m 2 )+m 3 (K 4 +m 4 )+(K+m 5 ) (K 2 +m 6 )+m 7 (K 8 +m 8 )
This construction can also be linearized by setting message blocks with an even index set to arbitrary constants.

Period-Finding against Poly1305

Poly1305 [START_REF] Bernstein | The Poly1305-AES message-authentication code[END_REF] is a polynomial MAC with some specific constraints that force a dedicated analysis. It has already been cryptanalysed in [START_REF] Bonnetain | Hidden shift quantum cryptanalysis and implications[END_REF], where the authors proposed an attack in 2 38 time and queries. The authors managed to overcome the specific constraints by leveraging a hidden shift structure. The attack we propose here is drastically more efficient, and uses a hidden period instead.

Poly1305 uses a hashing key r of 124 bits with at most 106 non-zero bits and a 128-bit cipher key K. The MAC of a message m 1 , . . . , m with the nonce N is computed as:

Poly1305(m 1 , . . . , m ) = (c 1 r + c 2 r -1 + . . . + c r 1 ) mod 2 130 -5 + AES K (N ) mod 2 128 ,
where c 1 , . . . , c are the padded message blocks obtained from the message blocks m 1 , . . . , m . When message blocks are full 128-bit blocks, the c i are simply obtained from the m i by adding 2 128 .

Let us assume that we query with two message blocks. We have:

Poly1305(m 1 , m 2 ) = m 1 + 2 128 • r 2 + m 2 + 2 128 • r mod 2 130 -5 + AES K (N ) mod 2 128 = ((m 1 • r + m 2 ) • r + C 1 ) mod 2 130 -5 + C 2 mod 2 128 ,
where C 1 , C 2 are constants of our query that depend on r, K, N . Since the computation ends with a reduction modulo 2 128 , which is smaller than 2 130 -5, we must actually use a compressed instance of Shor's algorithm [START_REF] May | Quantum period finding is compression robust[END_REF]. This increases mildly the number of queries, by less than a factor 2.

Two inputs (m 1 , m 2 ) and (m 1 , m 2 ) lead to the same tag if

m 1 r + m 2 = m 1 r + m 2 mod 2 130 -5 ⇔ (m 1 -m 1 )r + (m 2 -m 2 ) = 0 mod 2 130 -5 .
Hence, the periods of the function Poly1305(m 1 , m 2 ) are solutions of m 1 r +m 2 = 0 mod 2 130 -5.

As the period is modulo 2 130 -5 but the input is 128-bit long, we cannot do the query expected by Shor's algorithm. Still, the fraction of inputs we can actually query is large enough so that we can still apply Shor's algorithm with a partial query, and recover efficiently the period.

The initial query is:

1 2 128 2 128 -1 m1,m2=0 |m 1 |m 2 |Poly1305(m 1 , m 2 ) = 1 2 128 2 128 -1 m1,m2=0 |m 1 |m 2 |f (m 1 r + m 2 ) .
Here, is a function that depends on r, K, N . The only relevant point is that it does not depend on m 1 , m 2 directly, but only on m 1 r + m 2 . For simplicity, in the following we assume f is a permutation. We will now apply the QFT over Z/(2 130 -5) on the input registers. We note p = 2 130 -5. We obtain Thus, we measure a tuple (x, y) = (0, 0) with x = yr with probability at least 1/16. As 2 130 -5 is prime, one such tuple is enough to recover r. Hence, we need at most 16 queries on average to recover r, assuming f is a permutation. Here, as f is a function, we rely on [START_REF] May | Quantum period finding is compression robust[END_REF] to bound the increase by a factor 2. Note that as we are only a few bits of output short of having a permutation, this is a very loose bound. Overall, the attack will require no more than 32 queries.

On Parallelizable Quantum PRFs

Let us take a broader point of view. The deterministic MACs that we attacked in this paper all have common points. Besides allowing inputs of any length (as should be expected of any MAC construction), they • process their input blocks independently; • compute one or more linear functions, with XORs, of these processed input blocks; • process the authentication tag from the outputs of these linear functions.

These characteristics are to be expected from any MAC that is: • of average rate one, meaning that there are as many primitive calls as there are blocks; • parallelizable; • having an internal state of size O (n), independent of the query length. Our attack is easily defeated if the blocks are processed sequentially by calling a compression function, as in the NMAC construction. However, the construction becomes unparallelizable.

It may be possible to obtain a quantum-secure parallelizable qPRF using a tree hashing, where the blocks are placed at the leaves of a binary tree, and each node is computed by calling a (keyed) compression function on its two children. However, such a construction requires an internal state greater than O (n), and that increases with the amount of data. Typically to traverse the binary tree, we will need to remember O (log m) nodes, where m is the number of leaves. Open Question. If we stand by the characteristics listed above (efficient, parallelizable, constant internal state size), then it seems that the only solution is to use modular additions in place of XORs in the constructions that we attacked. In that case, our attack does not seem to work anymore, due to the fact that modular additions, contrary to XORs, are not involutive. Thus changing one of the blocks in our n-block queries does not modify involutively the result, which breaks the periodicity property that we used with Simon's algorithm.

This makes this option worth investigating, both from a provable security and a cryptanalysis perspective. Note that the situation is different from most attacks with Simon's algorithm, where the replacement of XORs by + changes the attack complexity from polynomial to subexponential (see [START_REF] Alagic | Quantum-secure symmetric-key cryptography based on hidden shifts[END_REF][START_REF] Bonnetain | Hidden shift quantum cryptanalysis and implications[END_REF]). In our case, it is possible that using + allows an exponential security level.

Conclusion

In this paper, we introduced a novel way of using quantum period-finding to break parallelizable MAC constructions in the superposition query model, breaking most of them in this setting. In full generality, our attack makes use of multiple blocks to embed a hidden period, a surprisingly simple idea that might have other applications. We gave new polynomial-time forgery or partial keyrecovery attacks on LightMAC, LightMAC+, PolyMAC, Poly1305, GCM-SIV2, Deoxys, ZMAC, PMAC TBC3k. Our attack is not mitigated by the use of multiple parallel branches (as in double-block hash-then-sum MACs). It can be prevented for IV-based MACs if the non-reused IV intervenes in the processing of all message blocks (as done in [START_REF] Bhaumik | QCB: efficient quantum-secure authenticated encryption[END_REF]).

These results show that we cannot obtain a parallelizable quantum-secure PRF by processing independently the message blocks, XORing the results, and then hashing the output. If modular additions are used instead of XORs, our attack does not apply anymore (except on polynomial hashing, which has a simpler structure). Overcoming this limitation, or on the contrary, proving the security of such a PRF, is an interesting open question.

1 √ y |αx 0 y | 2 y

 12 x,y α xy |x |y , measuring the register |x yields a value x 0 with probability y |α x0y | 2 , and projects on the state α x0y |y .

, 0, 0m 2 :

 2 Apply a Quantum Fourier Transform on both input registers p-1 x,y=0 |x, y |0m 3: Apply O f p-1 x,y=0 |x, y |f (x, y) 4: Measure the second register. The state collapses on a uniform superposition of all (x, y) such that xs + y = a mod p for some unknown a, meaning y = a -xs mod p:

Fig. 1 .

 1 Fig. 1. Computation of the tag in OCB3. Only the offset ∆ IV depends on the IV .

Fig. 2 .

 2 Fig. 2. Computation of the tag in ΘCB3. Only the final tweak t depends on the IV.

1 EK 2 TFig. 3 .

 123 Fig. 3. LightMAC+ with three keys K, K1, K2.

xm 1 m 1 #{0 ≤ m 1 , m 2 < 2 128 : m 1 r + m 2 = c} 2 Now, as x → x 2 2 . 2 = p -1 p2 256 1 p #{0 ≤ m 1 , m 2 < 2 128 } 2 =

 1112222221122 + ym 2 p |x |y |f (m 1 r + m 2 ) . We can rewrite the state by regrouping components with identical m 1 r + m 2 : (x -yr) p |x |y |f (c) Now, we can compute the probability to measure a nonzero tuple (x, y) with x = yr. As there are p -1 such tuples, the overall probability is is a convex function, we can use Jensen's inequality: This allows us to lower bound the previous probability by ≤ m 1 , m 2 < 2 128 : m 1 r + m 2 = c}

  xa•y ) |y and we sample a uniformly random y ∈ {0, 1} n . After n + r such samples, the family Y

	Algorithm 3 Simon's algorithm
	1: Y = ∅
	2: Choose a number r depending on the required probability of error
	3: Repeat n + r times
	4:	Start from |0n0n
	5:	Apply a Hadamard transform to the first register	x |x |0
	6:	Apply O f (standard)	x |x |f (x)
	7:	Measure the second register, obtain a	x|f (x)=a |x
	8:	Apply a Hadamard transform	y ( x|f (x)=a (-1) x•y ) |y
	9:	Measure a y, Y ← Y ∪ {y}
	10: EndRepeat
	11: if Y is of full rank then
	12:

Applications to Parallelizable MACsIn this section, we apply the quantum linearization attack to many parallelizable MACs of the literature. In particular, we show that the attack can be extended to

Grain128A and Grain128AEAD[START_REF] Hell | Grain-128 AEAD a lightweight AEAD streamcipher[END_REF] use Toeplitz hashing, but we can only attack them in the nonce-misuse setting because they use the one-time-MAC construction.

Acknowledgments 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). A.S. is supported by ERC-ADG-ALGSTRONGCRYPTO (project 740972).