Ritam Bhaumik

Xavier Bonnetain

André Chailloux

Gaëtan Leurent

María Naya-Plasencia

André Schrottenloher

Yannick Seurin

QCB: Efficient Quantum-secure Authenticated Encryption

Keywords: authenticated encryption, lightweight cryptography, QCB, postquantum cryptography, provable security, tweakable block ciphers

It was long thought that symmetric cryptography was only mildly affected by quantum attacks, and that doubling the key length was sufficient to restore security. However, recent works have shown that Simon's quantum period finding algorithm breaks a large number of MAC and authenticated encryption algorithms when the adversary can query the MAC/encryption oracle with a quantum superposition of messages. In particular, the OCB authenticated encryption mode is broken in this setting, and no quantum-secure mode is known with the same efficiency (rate-one and parallelizable). In this paper we generalize the previous attacks, show that a large class of OCB-like schemes is unsafe against superposition queries, and discuss the quantum security notions for authenticated encryption modes. We propose a new rate-one parallelizable mode named QCB inspired by TAE and OCB and prove its security against quantum superposition queries.

Introduction

The cryptographic community has launched many competitions and standardization efforts recently. The most recent ones are the CAESAR competition for authenticated encryption (AE) and the NIST standardization processes for post-quantum public-key primitives (PQC) [START_REF]Submission requirements and evaluation criteria for the post-quantum cryptography standardization process[END_REF] and lightweight cryptography (LWC) [START_REF]Submission requirements and evaluation criteria for the lightweight cryptography standardization process[END_REF]. While these competitions have attracted a lot of attention, they have represented rather disjoint efforts: the PQC process focuses on public key cryptography, and post-quantum security has remained out of the scope of most schemes submitted to the LWC process and to the CAESAR competition. A few exceptions exist, like the LWC second-round candidate Saturnin [START_REF] Canteaut | Saturnin: a suite of lightweight symmetric algorithms for post-quantum security[END_REF] for instance, which proposes a block cipher and an AE mode aiming at post-quantum security. This is understandable because the impact of quantum computers on symmetric cryptography is expected to be quite limited, and doubling the key length is usually considered a sufficient measure to resist quantum attacks (such as exhaustive key search with Grover's algorithm).

Security in the superposition model. However, recent works [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] have shown that many MAC and AE modes are broken in the superposition model using Simon's quantum period finding algorithm [START_REF] Simon | On the power of quantum computation[END_REF]. In this model, the adversary is capable of accessing a quantum encryption oracle, and of encrypting quantum states. Though the practical significance of attacks in this model is an unsettled issue in the community and opinions might differ, there is a clear consensus on the importance of having provable security in this scenario. First of all, this model is non-trivial, meaning that there exist secure schemes in this model. f It also offers better composability, even if we are interested only in quantum adversaries making classical queries. Finally, it captures intermediate scenarios with some level of quantum interaction between the attacker and the oracle and covers the scenarios of obfuscation or white-box encryption.

Though lightness and security against quantum adversaries are two very different topics, let us remark that they are not orthogonal. In particular, Saturnin is a submission to the LWC effort claiming security in the superposition model, based on a block cipher. But its authenticated encryption mode is not parallelizable and requires two encryption calls per message block. More precisely, it uses the encrypt-then-MAC construction and combines a quantum-secure mode of encryption (the Counter Mode) with a quantum-secure MAC similar to HMAC/NMAC.

Towards a quantum-safe rate-one AE mode. OCB [START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF] is one of the most influential authenticated encryption modes. OCB3 is parallelizable, and is a rate-one scheme, using just one block cipher call per block of message. It is proven secure in the classical setting provided that its underlying block cipher is a strong PRP [START_REF] Bhaumik | Improved security for OCB3[END_REF]. Nevertheless, several attacks using Simon's algorithm [START_REF] Simon | On the power of quantum computation[END_REF] were proposed in [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF], with a complexity that is linear in the size of the state. These attacks, that we recall in Section 3, can efficiently recover a hidden secret period if the attacker is allowed to query messages in superposition.

Our work started with the idea to make OCB post-quantum secure: we wanted to identify its weaknesses, correct them and obtain a proof of quantum security. The main contribution of this paper is to fill this gap and to propose such a mode together with a proof of security.

Results and Organization of the Paper. In Section 2, we recall some standard definitions and technical material for our quantum security proofs and attacks. Note that contrary to most of the recent works on this topic, we shall not require Zhandry's random oracle recording technique [START_REF] Zhandry | How to record quantum queries, and applications to quantum indifferentiability[END_REF] and we will use instead simpler proof arguments, that we introduce here. We also introduce an extension of Hosoyamada and Sasaki's truncation technique [START_REF] Hosoyamada | Quantum Demiric-Selçuk meet-in-the-middle attacks: Applications to 6-round generic Feistel constructions[END_REF] that allows to compose any linear function with a quantum oracle and compute it with a single query. In Section 3, we define an OCB-like mode with more complex offsets. The previous quantum attack on OCB used the fact that the difference between some offsets was independent of the nonce. We show how to attack this modified OCB with a single quantum query, yielding an attack that can be applied regardless of the nonce dependence. In Section 4, we define quantum-secure tweakable block ciphers. We are interested in adversaries making queries with classical tweaks and a superposition of messages, a setting which corresponds to the attacks on OCB. In this setting, we propose the key-tweak insertion TBC, which requires a relatedkey secure block cipher. In Section 5 we define the new rate-one parallelizable quantum safe mode, QCB, and propose two instances: one using Saturnin with the key-tweak insertion TBC and one using the dedicated TBC TRAX-L-17 [START_REF] Beierle | Alzette: A 64-bit ARX-box -(feat. CRAX and TRAX)[END_REF]. We prove in Section 6 the security of QCB if it is used with a secure TBC. We use two notions: IND-qCPA [START_REF] Boneh | Secure signatures and chosen ciphertext security in a quantum computing world[END_REF] and BZ-unforgeability [START_REF] Boneh | Quantum-secure message authentication codes[END_REF]. We discuss other possible definitions in Section 7.

Preliminaries

We open this section with standard notations for permutations, block ciphers and AEAD schemes. We also define the quantum oracle access that will be given to such a scheme in our proof. We recall some standard results and definitions related to quantum provable security. Finally, we introduce our new linear post-processing lemma (Lemma 2) that we will use in Section 3 and Section 7.

Definitions and Notations

We let P n denote the set of permutations acting on {0, 1} n . By x $ ← -S we mean that x is taken uniformly at random from the set S. We let A f (•) ⇒ b (resp. A f ( ) ⇒ b) denote an algorithm that performs classical queries to oracle f (resp. quantum queries to f ) and outputs b. We write A f ± (• or ) when A has access to the f and the f -1 oracle, which we blend into a single oracle f ± . Block Ciphers. A block cipher with key space {0, 1} k and message space {0, 1} n is a map E : {0, 1} k × {0, 1} n → {0, 1} n such that for every key K ∈ {0, 1} k , M → E(K, M ) is a permutation on {0, 1} n . We let

E K denote the map M → E(K, M ). If E is a block cipher then its inverse is the map E -1 : {0, 1} k × {0, 1} n → {0, 1} n defined by E -1 (K, C) = E -1 K (C).
AEADs. An authenticated encryption scheme with associated data (AEAD) is specified by a tuple of sets (K, IV, A, M, C) where K is the key space, IV is the IV space, A is the associated data space, M is the message space, and C is the ciphertext space, and a pair of deterministic algorithms (Enc, Dec) with signatures

Enc : K × IV × A × M → C Dec : K × IV × A × C → M ∪ {⊥} .
We require an AEAD scheme to be correct, i.e., for all (K, IV, A, M

) ∈ K × IV × A × M, Dec (K, IV, A, Enc (K, IV, A, M )) = M .
We write Enc K (IV, A, M ) for Enc (K, IV, A, M ) and similarly Dec K (IV, A, C). Note that this is the most generic definition of an AEAD, but in our case, we will replace the ciphertext space C by C × T , and the scheme will output a ciphertext C of variable length and an authentication tag T ∈ T of fixed size. As we consider AEADs based on block ciphers, C and M will be parsed into blocks that we index M 0 , . . . , M (resp. C 0 , . . . , C ) where is the block length of M (resp. of C).

Quantum Computing. In this paper, an adversary is a quantum algorithm that accesses one or more oracles. We use the quantum circuit model, whose basics can be found in [START_REF] Nielsen | Quantum information and quantum computation[END_REF]. A quantum algorithm is initiated with a set of m qubits (two-level quantum systems) in a fixed state |0 . The state of the algorithm lies in a Hilbert space of dimension 2 m , with a canonical basis {|i , 0 ≤ i ≤ 2 m -1}. Basic unitary operators, called quantum gates (drawn from a universal gate set), are applied on the qubits. These computations are interleaved with oracle calls and partial measurements, which transform a pure state (an element of the Hilbert space) into a mixed state (a probability distribution of pure states). For ease of notation, we often omit normalization factors from quantum states (e.g.,

1 √ 2 (|0 + |1 ) can be written |0 + |1 ).

Quantum Oracles and Query Model

We model quantum oracle access to any function f : X → Y as a unitary operation: |x |y → |x |y ⊕ f (x) (this is the standard oracle) or as |x |y → (-1) y•f (x) |x |y (this is the phase oracle). Standard and phase oracles are wellknown to be equivalent.

Choice of IVs.

In the classical setting, the security of IV-based AEADs draws on the fact that the IVs of successive queries are distinct and/or randomly chosen. So far, all security notions defined in the quantum setting have followed this setting [START_REF] Boneh | Secure signatures and chosen ciphertext security in a quantum computing world[END_REF][START_REF] Anand | Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation[END_REF][START_REF] Carstens | On quantum indistinguishability under chosen plaintext attack[END_REF], by considering randomness-based modes where the random IV is chosen at each new (quantum) query. Although a non-trivial extension to superposition IVs might be possible, it remains out of scope of our work.

In this paper, we will use classical and distinct IVs, but relax the randomness assumption. In the security games for AEAD defined and used in Section 6, we start the game by an initialization phase in which the adversary declares the IVs that he is going to query. This makes our reasoning easier and (as we will justify in Section 6) it includes the cases where IVs are generated at random, or with a stateful counter.

Quantum Query Model. The input plaintext and AD will be in superposition. Furthermore, the bit-length of the message, AD and ciphertext have to be chosen classically and cannot differ within a query; that is, we encrypt a superposition of messages of a fixed length. We let the adversary choose the bit-length of the message and AD in the queries between 0 and n for a fixed (which determines the maximal number of blocks to be queried). Thus, will intervene as a parameter in our bounds, together with the number of queries q.

Hence, our encryption and decryption oracles are actually families of unitary operators, indexed by these lengths and by the IV choice. As the ciphertext will be longer than the plaintext, we consider that the encryption oracles for messages of m bits output c(m) > m bits. Conversely, messages of distinct lengths may be encrypted to ciphertexts of the same length. Hence, the decryption oracle of a ciphertext of c bits writes a canonical encoding of either the message or ⊥ on c bits. We write these oracles O m,a,IV

Enc K and O c,a,IV Dec K respectively, with 0 ≤ m, a ≤ n. The encryption O m,a,IV
→ |A |M |X ⊕ Enc K (IV, A, M ) c(m) qubits . The decryption O c,a,IV
Dec K is a standard oracle for Dec K with ciphertexts of length c, AD of length a and a fixed IV:

|A a qubits |C c qubits |Y c qubits →    |A |C Y ⊕ M if C = Enc K (IV, A, M ) |A |C Y ⊕ ⊥ otherwise
with M the encoding of M and ⊥ the encoding of ⊥.

Counting Data, Time and Memory. While the oracles authorize messages, AD and ciphertexts to take any number of bits, the modes that we will consider are built on block ciphers with a fixed block size n. Hence, we can count the data complexity in the number of blocks queried: a query to Enc K or to O Enc K with blocks costs data. We count the time complexity either in the number of quantum gates, or in the number of block cipher calls, as a quantum standard oracle. We consider the cost of a single block cipher call to be marginal with respect to the other terms, as it is polynomial in n, making these definitions equivalent. The memory will also be counted in n-bit registers, either classical or quantum.

Distances

Usually, in game-based definitions, the adversary's advantage is a difference in probabilities to output 1 or 0. However, since our adversaries are quantum, their final state is a quantum state. It is well-known that the Euclidean distance between quantum states is related to the distance between the distributions that result from measuring these states. Thus, the probabilistic interpretation of the adversary's result (measuring 0 or 1) can be replaced by a Euclidean distance.

i ||α i | 2 -|β i | 2 | ≤ 4 |φ -|ψ
. The decision of a quantum adversary to output 0 or 1 is conditioned only on its final state. Thus, if two adversaries have similar end states, they can only win with similar probabilities.

Lemma 1.

Let A be a quantum adversary that outputs a bit b. Let B be another adversary that also outputs a bit b, and let |ψ and |φ be their respective states after the last oracle query, before measuring their output in the computational basis. Then:

| Pr [A(•) = 1] -Pr [B(•) = 1] | ≤ 4 |ψ -|φ .
In practice, we will consider a game in which some parameter is selected at random (e.g., the key K), then the game runs and the final state of the adversary depends on K. We are interested in the quantity | Pr

K $ ←K [A(•) = 1] - Pr K $ ←K [B(•) = 1]
| which determines the difference in advantage between the two adversaries. We have: Pr

K $ ←K [A(•) = 1] = k∈K Pr [K = k] Pr [A(•) = 1|K = k].
That is, we can write:

| Pr K $ ←K [A(•) = 1] -Pr K $ ←K [B(•) = 1] | ≤ 1 |K| k∈K | Pr [A(•) = 1|K = k] -Pr [B(•) = 1|K = k] | ≤ 4 |K| k |ψ k -|φ k ,
where |ψ k and |φ k are the final states conditioned on the fact that the selected key is k. So in practice, we will fix all the random parameters, compute the euclidean distance between the end states and take the average.

Query magnitude

We will use a "query magnitude" argument, taken from [START_REF] Bennett | Strengths and weaknesses of quantum computing[END_REF].

|ψ q -ψ q ≤ 2 i |P D (|ψ i )| .

On Random Functions and Permutations

We will use the following results from the literature. First of all, as shown by Zhandry, it is impossible to distinguish a random function with n-bit domain from a random permutation with probability bigger than O q 3 2 n with q queries (where the constant in the O is fixed by the theorem); and conversely. We refer to this statement as PRF-PRP switching.

Theorem 2 ([34], Theorem 3.1).

Let h : {0, 1} n → {0, 1} m be a random function. Any quantum algorithm making q quantum queries to h can only find a collision with probability at most O q 3 2 m . If n ≤ m, then any quantum algorithm making q queries cannot distinguish h from a random injective function except with probability O q 3 2 m .

Second, we use a theorem by Boneh and Zhandry that shows that a quantum algorithm making q queries to a random oracle with a domain of exponential size can only output q + 1 valid {input, output} pairs with negligible probability.

Theorem 3 ([9], Theorem 4.1).

Let A be a quantum algorithm making q queries to a random oracle h : {0, 1} n → {0, 1} m , and producing k > q pairs (x i , y i ) ∈ {0, 1} n × {0, 1} m . The probability that the x i are distinct and

y i = h(x i ) for all 1 ≤ i ≤ k is at most: 1 2 mk q r=0 k r
(2 m -1) r . If k = q + 1 then the adversary succeeds with probability at most q+1 2 m .

We will use the terminology "(q, q + 1) security game" to refer to the game in which A accesses O h q times and must produce q + 1 valid pairs. An alternative proof of Theorem 3 for the q, q + 1 case can be found in the full version of [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF]. By combining this theorem with Theorem 2, we obtain a similar statement for random permutations.

Corollary 1. There exists a constant c such that, if A is a quantum algorithm making q queries to a random permutation Π : {0, 1} n → {0, 1} n and trying to produce q + 1 valid input-output pairs, then A can only succeed with probability at most: c q 3 2 n .

The term in Corollary 1 is simply the sum of the PRP-PRF distinguishing advantage and the (q, q + 1) advantage. The former grows much faster with q, but we will mostly use Corollary 1 with a single query, where both terms are O (2 -n ).

Computing a Linear Function of a Quantum Oracle

In [START_REF] Hosoyamada | Quantum Demiric-Selçuk meet-in-the-middle attacks: Applications to 6-round generic Feistel constructions[END_REF] Hosoyamada and Sasaki show that given access to a standard oracle O f for a function f , it is possible to make a quantum query to Trunc(f (x)), the truncation of the output f (x) to some bits, using only one quantum query to f . We now extend this result, and show that it is possible to compute any linear function of the output using only one quantum query. This is especially important with the oracles we will be using, since they involve IVs that are changed at each new quantum query.

The core observation in [START_REF] Hosoyamada | Quantum Demiric-Selçuk meet-in-the-middle attacks: Applications to 6-round generic Feistel constructions[END_REF] is simple: the state |0 + |1 is invariant whether we XOR a 0 or a 1 on it. Hence, before the query, in the output register, we can set the qubits we want to drop to |0 + |1 and the qubits we want to keep to |0 . We will now extend this result, with the following lemma:

Lemma 2 (Computing a linear function of a quantum oracle). Let

f : {0, 1} n → {0, 1} m be a function, O f : |x |y → |x |y ⊕ f (x) . Let g : {0, 1} m → {0, 1} o be an F 2 -linear function. Then it is possible to construct the oracle O g•f : |x |y → |x |y ⊕ (g • f )(x) using two queries to O g and a single query to O f .
Proof. Let O g be a quantum oracle that implements g, assume we are given the quantum state |x |y . We first add an ancilla register containing the uniform superposition on m bits. We then have the state |x |y 2 m -1 z=0 |z . Then, we apply O g with register z as input and y as output, and we get

|x 2 m -1 z=0 |y ⊕ g(z) |z .
Then, we apply O f with register x as input and z as output. We get

|x 2 m -1 z=0 |y ⊕ g(z) |z ⊕ f (x) .
Finally, we reapply O g with register z as input and y as output. We get

|x 2 m -1 z=0 |y ⊕ g(z) ⊕ g(z ⊕ f (x)) |z ⊕ f (x) .
As g is linear, we have g(z) ⊕ g(z ⊕ f (x)) = g(f (x)). Hence, the state can be rewritten as

|x |y ⊕ g(f (x)) 2 m -1 z=0 |z ⊕ f (x) .
This state can then be simplified, as the z register contains the uniform superposition over m bits, independently of the value of f (x), to

|x |y ⊕ g(f (x)) 2 m -1 z=0 |z .
We can now remove the z register, as it is not entangled with the others, and obtain the quantum state we wanted.

Remark 1. Lemma 2 can also be applied if the quantum oracle to f uses a group law different from ⊕ to update its output register. In that case, g shall be a linear function for the corresponding group law.

Offsets don't work

In this section we start by recalling the superposition attacks on OCB from [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF]. We will next present a first attempt to repair it, that consists of tweaking the value of the offsets, along with a new original superposition attack that shows that any offset-based variant can be broken using Simon's algorithm.

Attack with Simon's Algorithm on OCB

OCB g [START_REF] Krovetz | The software performance of authenticated-encryption modes[END_REF] is one of the most influential authenticated modes. OCB3 is represented in Figure 1, with ∆ i = gray(i) • E K (0 n ) (using a finite field multiplication) and

∆ IV i = ∆ i ⊕ F K (IV )
, with F a simple function of K and IV and gray(i) the gray encoding of i.

OCB3 is classically proven secure if its underlying cipher is a strong PRP.

Simon's algorithm. Simon's algorithm, proposed in [START_REF] Simon | On the power of quantum computation[END_REF] allows to solve efficiently, with a complexity of O(n), the following problem when we are allowed to ask superposition queries to F:

M 0 ∆ IV 0 E K ∆ IV 0 C 0 M 1 ∆ IV 1 E K ∆ IV 1 C 1 . . . M ∆ IV E K ∆ IV C M 0 ⊕ . . . ⊕ M ∆ IV +1 E K i E K (A i ⊕ ∆ i ) Tag Fig. 1. OCB3. (Mi) is the message, (Ai) is the associated data.
Given a Boolean function F on n bits and the promise that there exists s such that, for any x = y, F(x) = F(y) ⇐⇒ x = y ⊕ s, find s.

Simon's algorithm recovers a vector orthogonal to the period with a single quantum query; with O(n) queries, the period is deduced with linear algebra. As shown in [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF], a sufficient condition on F is that there exists no "unwanted period" t = s such that F(x ⊕ t) = F(x) holds with probability ≥ 1 2 . For comparison, classically, the best algorithm requires Ω √ 2 n queries.

Quantum Superposition Attacks on OCB. Two polynomial-time attacks against OCB that require quantum superposition queries to the construction were proposed in [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF]. They both use Simon's algorithm h . The main weakness of OCB is that the nonce only influences the construction through the value ∆, which is XORed to the internal state. The scenario of the attack considers that the attacker has access to a superposition oracle that given a superposition of messages as input, returns the superposition of their encryption. The key is a secret value and the IV is different for each query.

The first attack considers an empty message, and two variable identical blocks x of associated data. The output is then

E K (F K (IV )) ⊕ E K (x ⊕ ∆ 1 ) ⊕ E K (x ⊕ ∆ 2 ) .
This function is periodic, of period ∆ 1 ⊕ ∆ 2 . It is IV-dependent, but the period is not. This allows to use Simon's algorithm to recover the period.

The second attack uses the same idea, but attacks the encryption part and not the authentication. Its core idea is to consider the XOR of two distinct blocks i and j that encrypt the same message block. This is equal to

f i,j (x) = E K (∆ IV i ⊕ x) ⊕ E K (∆ IV j ⊕ x) ⊕ ∆ IV i ⊕ ∆ IV j .
h One attack on OCB presented in [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF] was partial, as it assumed without any mention the use of Lemma 2.

This function is periodic, of period ∆ IV i ⊕∆ IV j = (gray(i)⊕gray(j))•E K (0 n ) . We can then use Simon's algorithm, and this time we need to use Lemma 2 to compute the XOR of two blocks using only one query.

Both attacks recover the difference of two offsets, which is sufficient to make some forgeries. Note that in both cases, the existence of an unwanted period t would imply a high-probability higher-order differential of E K , which would result in a classical break.

A First (Failed) Attempt to Fix OCB

To protect a mode vulnerable to Simon's algorithm, Alagic and Russell [START_REF] Alagic | Quantum-secure symmetric-key cryptography based on hidden shifts[END_REF] proposed to replace the XOR by modular addition. However, this merely increases the attack complexity from polynomial to subexponential [START_REF] Bonnetain | Hidden shift quantum cryptanalysis and implications[END_REF], which does not give acceptable security levels for standard block sizes (e.g., 256 bits).

In order to make OCB quantum-resistant, we will rather try to avoid these attacks entirely. Our first idea is to avoid having an IV-independent period, by making the influence of E K (IV ) different for each block. For instance, ∆ i could be changed to a multiple of E K (IV ):

∆ i = i • E K (IV )
. (The multiplication is still done in the finite field, like in OCB's offsets). This way, the previous attack could only recover one bit of E K (IV ) at a time, which is useless if the IV changes for each query.

New superposition attack for any nonce-based solution.

Actually, the previous proposal is still unsafe, but it requires a new more advanced attack that we present here. This evolved attack is inspired by the multiple-period attacks from [START_REF] Bonnetain | Quantum key-recovery on full AEZ[END_REF]. Its core idea is to leverage the possibility to encrypt a long message to construct multiple copies of the periodic function, in such a way that one query will likely be enough to recover all the bits of the period.

Let g be the function that maps the sequence (x 1 , x 2 , . . . ,

x 2n-1 , x 2n ) to (x 1 ⊕ x 2 , x 3 ⊕ x 4 , . . . , x 2n-1 ⊕ x 2n ).
We consider the function

f (x 1 , . . . , x n ) = g • OCB(x 1 , x 1 , x 2 , x 2 , . . . , x n , x n ) Reusing the notation f i,j (x) = E K (∆ i ⊕ x) ⊕ E K (∆ j ⊕ x) ⊕ ∆ i ⊕ ∆ j , we have f (x 1 , . . . , x n ) = (f 1,2 (x 1 ), f 3,4 (x 2 ), . . . f 2n-1,2n (x n ))
This function is periodic, of period:

s = ∆ 1 ⊕ ∆ 2 , . . . , ∆ 2n-1 ⊕ ∆ 2n = (1 ⊕ 2) • E K (IV ), . . . , ((2n -1) ⊕ (2n)) • E K (IV )
We can also bound the probability of unwanted collisions. If f admits an unwanted period t with probability greater than 1 2 , then one of the f i,j would also admit an unwanted period t i,j with probability greater than 1 2n . As before, this is impossible if E K does not admit a high-probability higher-order differential.

Hence, Simon's algorithm allows us to sample one vector orthogonal to each of the periods of the involved f i,j . As these periods are linearly dependent, this is enough to recover completely the value E K (IV ), assuming n is large enough.

Conclusion.

This attack shows that a solution based on offsets is unlikely to work. After this failed attempt, we decided to move one step backwards. OCB can be seen as an instantiation of the mode TAE or ΘCB, which is defined with a Tweakable Block Cipher (TBC). The TBC used in OCB is the LRW mode [START_REF] Liskov | Tweakable block ciphers[END_REF], which builds upon a block cipher, and is quantumly broken [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF]. The attacks that we gave all seem to stem from the TBC itself, not the mode.

Quantum-secure Tweakable Block Ciphers

In this section, we define quantum-secure tweakable block ciphers (TBCs). We give a TBC construction based on a block cipher in the ideal cipher model, which we will recall below, and explicitly provide its security guarantees.

Definitions Definition 2. Let E be a block cipher. Let A be an oracle algorithm (making either classical or quantum queries depending on the case) which outputs a bit. The advantage of A against the PRP and Strong PRP (SPRP) security of E is defined as:

Adv PRP E( * ) (A) := Pr K $ ← -{0,1} k [A E K ( * ) ⇒ 1] -Pr Π $ ← -Pn [A Π( * ) ⇒ 1] Adv SPRP E( * ) (A) := Pr K $ ← -{0,1} k [A E ± K ( * ) ⇒ 1] -Pr Π $ ← -Pn [A Π ± ( * ) ⇒ 1]
Depending on the access that the adversary has (classical or quantum) to the messages, we replace the * symbol by • (classical) or (quantum).

Tweakable Block Ciphers. A tweakable block cipher (TBC)

with key space {0, 1} k , tweak space {0, 1} t , and message space {0, 1} n is a map E : {0, 1} k × {0, 1} t × {0, 1} n → {0, 1} n such that for every key K ∈ {0, 1} k and every tweak

T ∈ {0, 1} t , M → E(K, T, M ) is a permutation of {0, 1} n . We let E K denote the map (T, M ) → E(K, T, M ). If E is a TBC then its inverse is the map E -1 : {0, 1} k × {0, 1} t × {0, 1} n → {0, 1} n defined by E -1 (K, T, C) being the unique M such that E(K, T, M ) = C. A tweakable permutation with tweak space {0, 1} t and message space {0, 1} n is a map Π : {0, 1} t × {0, 1} n → {0, 1} n such that for every tweak T ∈ {0, 1} t , M → Π(T, M
) is a permutation of {0, 1} n . We let P t,n denote the set of all tweakable permutations with tweak space {0, 1} t and message space {0, 1} n .

Definition 3. Let A be an oracle algorithm making (classical or quantum) queries and which outputs a bit. The advantage of A against the TPRP, resp. strong TPRP (STPRP) security of E is defined as

Adv TPRP E( * , * ) (A) := Pr K $ ← -{0,1} k [A E K ( * , * ) ⇒ 1] -Pr Π $ ← -Pt,n [A Π( * , * ) ⇒ 1] Adv STPRP E( * , * ) (A) := Pr K $ ← -{0,1} k [A E ± K ( * , * ) ⇒ 1] -Pr Π $ ← -Pt,n [A Π ± ( * , * ) ⇒ 1] .
Depending on the access that the adversary has (classical or quantum) to the messages and to the tweaks, we replace the * symbols by • (classical) or (quantum).

The modified (S)TPRP Game. In the proofs of this section, we consider an adversary A playing a modified (S)TPRP game that consists of three phases:

• Pre-Declaration Phase: In the first phase, A declares a set of m tweaks {T 1 , . . . , T m }. • Quantum Phase: In the second phase, A gets access to a standard oracle implementing either E (±)

K or Π (±) , and can make q 1 quantum queries with classical tweaks, subject to the restriction that the tweak is always chosen from the set of pre-declared tweaks {T 1 , . . . , T m }, then measures its final state and outputs s 0 classical bits; • Classical Phase: In the final phase, A makes an additional q 2 classical queries to the oracle, this time with no restriction on the set of tweaks that can be queried, such that the queries are deterministic functions of the s 0 classical bits output at the end of the previous phase.

Thus, the bounds that we will obtain will depend on the number of pre-declared tweaks m, the number of quantum queries q 1 made by A, the number of classical bits s 0 output at the end of the quantum phase, and the number of classical queries q 2 made by A. Note that in the quantum phase some of the pre-declared tweaks may be used multiple times, and some can be ignored entirely. We use the notation Adv (S)TPRP

E(•, )

(A) for this restricted case.

TBCs from Block Ciphers. In this section, we will construct a TBC from a block cipher, and prove security in the ideal cipher model. In the quantum setting, this model was previously considered by Hosoyamada and Yasuda [START_REF] Hosoyamada | Building quantum-one-way functions from block ciphers: Davies-Meyer and Merkle-Damgård constructions[END_REF] to analyze the Davies-Meyer and Merkle-Damgard constructions. This means that the underlying block cipher E is chosen uniformly at random from the set BC k,n of all block ciphers with key space {0, 1} k and message space {0, 1} n at the beginning of the (S)TPRP distinguishing game and the adversary is allowed to make quantum queries to E ± (specifying the key and the plaintext/ciphertext).

The advantage is then defined as

Adv (S)TPRP E (A) := Pr K $ ← -{0,1} k E $ ← -BC k,n [A E (±) K ( * , * ),E ± ( ) ⇒ 1] -Pr Π $ ← -Pt,n E $ ← -BC k,n [A Π (±) ( * , * ),E ± ( ) ⇒ 1] .
(Note that the adversary has access to E ± even in the non-strong TPRP definition.)

Impossibility Results

In order to illustrate the difficulties of building a quantum-secure TBC, even in a weak sense, let us first consider a few examples.

LRW. The LRW mode [START_REF] Liskov | Tweakable block ciphers[END_REF] uses an almost 2-XOR universal hash function family H and adds h ∈ H to the key:

E K,h (T, x) = E K (h(T ) ⊕ x) ⊕ h(T ) .
An -almost 2-XOR universal hash function family H is such that for all x, y, z with x = y, the probability of h(x) ⊕ h(y) = z is small (less than ) when h is chosen at random. Classically, LRW is a strong TBC.

However, the LRW mode is not a quantum-secure TBC even if we allow only classical queries to the tweaks. This was shown in [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF], with an attack that is close to the OCB attacks: by querying only two classical tweaks T 0 , T 1 , one can build a function:

f (x) = E k (h(T 0 ) ⊕ x) ⊕ h(T 0 ) ⊕ E k (h(T 1 ) ⊕ x) ⊕ h(T 1 )
which is periodic, of period h(T 0 ) ⊕ h(T 1 ). Using Simon's algorithm, we can recover the period of this function in O (n) queries. This provides a powerful distinguisher, as this property is extremely unlikely with random permutations. Note that this distinguisher still applies for any function h, even if it is an unknown qPRF.

Key-tweak Insertion. We will consider the key-tweak insertion TBC, built from a block cipher E as: E K (T, M ) = E K⊕T (M ). It admits a simple distinguisher based on Simon's algorithm if the tweaks are queried in superposition: this is the quantum related-key attack of [START_REF] Rötteler | A note on quantum related-key attacks[END_REF]. Indeed, the function f ( ) = E K⊕ (0)⊕E (0) admits K as a period, and so we can use Simon's algorithm again.

Proof of Security for the Key-tweak Insertion TBC

Let E ± K (T, x) = E ± K⊕T (x)
denote the key-tweak insertion TBC. The following proposition shows the STPRP security of this TBC in the ideal cipher model against an adversary playing the modified STPRP game described earlier. We give its proof in Appendix A.

Proposition 1.

Let A be an adversary who makes q 1 quantum queries to an oracle implementing E ± K or Π ± with a pre-declared set of tweaks of size m, and q queries to E ± , followed by outputting s 0 bits and making q 2 classical queries to the same oracle. Then:

Pr K $ ← -K [A E ± K (•, ),E ± ( ) ⇒ 1] - Pr {Π T } $ ← -Pn [A Π ± (•, ),E ± ( ) ⇒ 1] ≤ 8 mq 2 2 k + q 2 s 0 2 • 2 k .
Notice that the above bound depends on m but not on q 1 which is reminiscent of the classical security bound of this TBC (see [START_REF] Bellare | A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications[END_REF], Theorem 6.3 and Corollary 6.5) that depends on the number of different tweaks used and not on the number of queries to E ± . i

We do not explicit how this set of tweaks is determined. It could for example be chosen by the adversary. In that case of course we should not allow him to have a complete control over the size of this set, i.e., the choice of m, or else he could choose m extremely large which would make the above bound useless.

This proposition implies the security when the adversary queries non-adaptive tweaks (so they are predetermined from the start) in which case m = q 1 , but also allows some adaptivity from a predefined set of tweaks for which we can control the size.

When proving the quantum security of QCB in Section 6, we will use the above proposition, but we will be able to control the value of m which will not be significantly larger than q 1 .

Other Directions

Quantum-secure TBCs have been independently considered by Hosoyamada and Iwata in [START_REF] Hosoyamada | Provably quantum-secure tweakable block ciphers[END_REF]. They used a stronger notion of security where tweaks can be queried in superposition, and showed how to construct such a TBC from a block cipher. Their TBC (LRWQ) does not use the ideal cipher model, and only requires the block cipher to be secure as a qPRP. However, they use three block cipher calls for each TBC call, one to process the tweak, and two for the plaintext (before and after XORing the encrypted tweak). Thus, this construction cannot achieve the efficiency that we target. Note that they bound the adversary's advantage, after q queries, by O( q 6 /2 n ), compared to a classical O( q 2 /2 n ) (assuming respectively that the cipher behaves as a qPRP, and a PRP).

Definition of QCB

In this section, we describe the QCB mode, an AEAD based on a Tweakable Block Cipher. It is similar to the TAE mode [START_REF] Liskov | Tweakable block ciphers[END_REF][START_REF] Liskov | Tweakable block ciphers[END_REF] and to ΘCB [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]. Throughout i Theorem 6.3 in [START_REF] Bellare | A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications[END_REF] is about related-key attacks, but this implies a corresponding result for the key-tweak insertion TBC, see Theorem 7.1 of the same paper.

C i ← E K,(0,IV,i) (M i )
Encryption of block i 6: end for

7: C * ← E K,(1,IV, ) (pad(M * ))
Encryption of the final block 8: T ← 0 9: for all i = 0 to j do 10:

T ← T ⊕ E K,(2,IV,i) (A i ) Absorb AD block i 11: end for 12: T ← T ⊕ E K,(3,IV,j) (pad(A * ))
Absorb the final AD block

13: T ← T ⊕ E K,(4,IV, ) (M 0 ⊕ . . . ⊕ M ⊕ pad(M * )) 14: return C = (C 0 C 1 . . . C C * ), T
this section, E K,t will denote a TBC used with key K and tweak t, of block size n. We separate the tweak space in a cartesian product: T = D × IV × L. Thus, tweaks are triples (D, IV, j) where D is a domain separator, IV will be an IV, and j will be a block index. Only 5 values of domain separator need to be used.

The mode is defined in Algorithm 1 and represented in Figure 2 and Figure 3. When the message and AD are cut in blocks, the last block (M * and a * respectively) may be empty. We define the padding scheme pad(M * ) as appending 10 * (a 1 followed by as many zeroes as necessary to fill the block). Note that due to the padding and structure of QCB, the ciphertext C is always longer than the plaintext M (by n bits at most).

M 0 E K,(0,IV,0) C 0 M 1 E K,(0,IV,1) C 1 . . . M E K,(0,IV, ) C pad(M * ) E K,(1,IV, ) C * Fig. 2. QCB, encryption. A 0 E K,(2,IV,0) A 1 E K,(2,IV,1) . . . . . . A j E K,(2,IV,j) pad(A * ) E K,(3,IV,j) i M i ⊕ pad(M * ) E K,(4,IV, )
T Fig. 3. QCB, processing of the associated data and computation of the tag.

Avoiding Quantum Attacks. It is important to include the IV in the tweak when processing the AD. Otherwise, there is a quantum forgery attack based on Deutsch's algorithm [START_REF] Bonnetain | Quantum linearization attacks[END_REF]. In Section 6, we will prove that QCB is secure assuming a weak quantum-secure TBC. We will use the following property, which follows from its definition.

Proposition 2 (Number of tweaks (informal)). For a given IV , there exists a set of tweaks T (IV ) of size |T (IV )| = 5( + 1) such that any QCB query comprised of at most n (included) bits of AD and n bits of message can only reach tweaks in the set T (IV ).

Proof. The tweaks are of the form (d, IV, i) where i is a block number between 0 and (included) and d a domain separator that takes 5 values.

Instantiation with Saturnin: Saturnin-QCB. We propose to instantiate QCB with the block cipher Saturnin [START_REF] Canteaut | Saturnin: a suite of lightweight symmetric algorithms for post-quantum security[END_REF], a second-round candidate of the NIST LWC process [START_REF]Submission requirements and evaluation criteria for the lightweight cryptography standardization process[END_REF]. Saturnin has 256-bit blocks and keys. In addition, the cipher admits a domain separator D of 4 bits. The other modes of operation of the Saturnin submission use values from 0 to 8 included, so we use D = 9, 10, 11, 12 and 13 in Algorithm 1. More precisely, the authors of [START_REF] Canteaut | Saturnin: a suite of lightweight symmetric algorithms for post-quantum security[END_REF] define a variant of Saturnin with 16 Super-rounds aiming at an increased security margin in the related-key scenario, denoted Saturnin 16 . We define: E k,(D,IV,i) (x) = Saturnin D 16 (k ⊕ (IV ||i), x), where we use the key-tweak insertion construction of Section 4 to turn Saturnin D 16 into a TBC with 256-bit tweaks. The IV and the block number are simply concatenated. We use IVs of at most 160 bits and authorize up to 2 95 blocks of data. This construction motivates further inquiry of related-key attacks, as it needs Saturnin 16 to be related-key secure.

Instantiation with a Dedicated TBC: TRAX-QCB. Block ciphers of 256 bits seem more convenient for post-quantum security. However, they are relatively rare (for example, Saturnin is the only such one in the LWC standardization process). Fortunately, it is possible to instantiate QCB with a dedicated TBC with 256-bit blocks, the TRAX-L-17 cipher of [START_REF] Beierle | Alzette: A 64-bit ARX-box -(feat. CRAX and TRAX)[END_REF]. It has smaller tweaks of 128 bits, contrary to the key-tweak-insertion TBC with Saturnin, but it has the advantage of being a dedicated design, with possibly a better security than the tight bound for the key-tweak-insertion. 128 bits allow to fit the 3 bits required for domain separation, 80 bits of IV and 45 bits of block numbering. Thus we can encrypt at most 2 45 -1 blocks of plaintext and AD.

Security of QCB

We show that, if the underlying TBC is secure under classical tweak queries:

• QCB is IND-qCPA secure (Section 6.2): an adversary making quantum encryption queries cannot distinguish between the encryptions of two classical challenge messages; • QCB is BZ-unforgeable (Section 6.3): an adversary making q quantum encryption queries cannot output q + 1 valid IV/AD/ciphertext/tag quadruples.

We discuss other possible (and impossible) security definitions in Section 7.

Definitions

In all our definitions, the adversary makes q superposition queries with distinct pre-declared IVs. The messages and ADs both have a maximal length of complete blocks, but the exact length of queries can be chosen adaptively. We will bound the advantage depending only on q and . We will use superscripts for separate queries, and subscripts for individual blocks within a query.

IND-qCPA.

First of all, we recall the definition of the IND-qCPA security game from [START_REF] Boneh | Secure signatures and chosen ciphertext security in a quantum computing world[END_REF]. In [START_REF] Boneh | Secure signatures and chosen ciphertext security in a quantum computing world[END_REF], each call to the encryption oracle contains randomness. We extend slightly this definition by making the adversary capable of choosing his IVs. However, we request this choice to be non-adaptive. Thus, the adversary specifies at the start of the game the sequence of IVs that she is going to use.

IND-qCPA game

Key generation:

K $ ← K, b $ ← {0, 1}
. Initialization: A sends to the challenger a sequence of distinct IVs:

(IV 1 , . . . , IV q ), one for each subsequent query.

A can perform q -1 encryption queries and one challenge query (at the very end or somewhere in between). For the k th query, the current IV is IV k . For each query, the message and AD length are chosen between 0 and n bits for a fixed (superposed messages must have the same length).

The IND-qCPA advantage of an adversary A against an AEAD E is:

Adv IND-qCPA E (A) = Pr [A succeeds] - 1 2 .
BZ. We define our "Boneh-Zhandry" (BZ) unforgeability game, which is analogous to the definition of unforgeability for MACs of [START_REF] Boneh | Quantum-secure message authentication codes[END_REF].

BZ game

Key generation: K $ ← K. Initialization: A sends to the challenger a sequence of distinct IVs:

(IV 1 , . . . , IV q ), one for each subsequent query.

Encryption queries:

A chooses a message and AD pair (M, A), the encryption oracle encrypts (IV, M, A) with the current IV and returns the output (C, T ) to A. Queries can be in superposition. Forgeries: A produces q + 1 quadruples (A, IV, C, T ) with any IVs of her choice and succeeds if all these quadruples are valid, that is, for each quadruple, there exists an M such that the encryption of (IV, M, A) is (C, T ).

Note that verifying the forgery attempts requires additional queries. Since we assumed a limit on the message and AD lengths of blocks at most, we will also impose this limit on the forgery attempts of the adversary.

In practice, IVs are often either specified by a counter or chosen at random. We argue here that our security definitions are stronger than these 2 scenarios:

• If the challenger chooses at random IV i for each encryption query. Then, he could as well generate all the possible IV 1 , . . . , IV q from the start. In our model, an adversary can generate IV 1 , . . . , IV q at random and send them to the challenger. The security is the same as before except that the adversary knows the different IVs. This can only help the adversary so being secure in our model implies security in the model where the IVs are chosen at random by the challenger. • If the IVs are determined by a counter controlled by the challenger. The adversary can decide when he starts the attack and even assume he has control over the first IV which we call IV 1 , then the set of IVs will be {IV 1 , IV 1 + 1, . . . , IV 1 + (q -1)}. In our model, an adversary can do that by declaring this set so again, our model is stronger j .

In the IND-qCPA and BZ definitions above, the adversary chooses a sequence of distinct IVs: (IV 1 , . . . , IV q ). When proving the security of QCB with oracle access to a tweakable block cipher E, this immediately implies that the set T of possible tweaks to E is T = ∪ q i=1 T (IV i ) hence |T | ≤ 5( + 1)q where is the maximal block length of encryption queries. This control on the size of T allows us to use Proposition 1 in a meaningful way.

IND-qCPA Security

Theorem 4. Let QCB[ E] denote the QCB function with oracle access to the tweakable blockcipher E. We consider adversaries making q queries of block length ≤ to QCB[ E], then we have:

Adv Ind-qCPA QCB[ E] (A) ≤ Adv TPRP E(•, ) (5( + 1)q) , ( 1
)
where the right-hand term is the maximal advantage over all adversaries querying E(•, ) with at most 5( + 1)q pre-declared tweaks.

Proof. Suppose A is an adversary trying to break the IND-qCPA security of QCB[ E]. A performs q encryption or challenge queries of maximum block length (the exact bit length of the queries can be chosen freely in the range 0, . . . , n ). Consider the query number i made to QCB (encryption or challenge). From Proposition 2, in this query, the tweakable block cipher E is queried with tweaks in the set T (IV i ) having a fixed size |T (IV i )| = 5( + 1).

We can therefore see A as an algorithm performing at most q(2 + 3) queries to E, with each tweak lying in the fixed set T = ∪ q i=1 T (IV i ) with |T | ≤ 5q( + 1) (each query contains at most message and AD blocks, padding blocks and a final checksum block). If we replace E with Π for a random Π, we get:

Adv Ind-qCPA QCB[ E] (A) -Adv Ind-qCPA QCB[ Π] (A) ≤ Adv TPRP E(•, ) (5( + 1)q) . ( 2
)
Finally, consider an adversary A playing an IND-qCPA game with QCB[ Π]. Recall that in the challenge phase, A picks two classical plaintext/AD pairs (M 0 , A 0 ) and (M 1 , A 1 ) of the same length, after which the challenger picks a random bit b and gives (C b , T b )-the encryption (and tag) of (M b , A b )-to A. Since the tweaks used for computing this encryption are all different from all the tweaks used during the query phase, and since Π is an ideal tweakable random j There is only one case in which the use of a counter may enable an adversary to choose his IVs adaptively: he may wait for the counter to increase in order to reach a wanted IV. But the IV increases only when a message is encrypted so waiting for an IV increase should be essentially considered as costly as performing a query, which implies that the IVs that will be used will be in {IV1, . . . , IV1 + (q -1)} .

permutation, the distribution of (C b , T b ) is independent of the distribution of the responses received by A during the query phase. Since b is a random bit, if b is the bit output by A, the probability that b = b is always 1/2. Furthermore, this holds irrespective of the choice of A. Thus,

Adv Ind-qCPA QCB[ Π] (A) = 0. ( 3
)
Our result follows directly by putting this equality into Equation 2.

Theorem 4 is the only result required if we use a dedicated TBC. If we want to use a block cipher, we can replace E by the key-tweak insertion TBC of Section 4. The security will then hold in the ideal cipher model. We use Proposition 1 in the special case where s 0 = 0 (in the reduction, there is no second phase of classical queries).

Corollary 2. In the case of the key-tweak insertion TBC of Section 4, we consider adversaries making also q queries to E ± and we have:

Adv Ind-qCPA QCB[ E] (A) ≤ Adv TPRP E(•,
),E ( ) (5( + 1)q, q ) ≤ 8 5( + 1)qq 2 2 n . (4)

Unforgeability

Now, we prove that QCB is BZ-unforgeable. Again, the first statement holds in the standard model, the second in the ideal cipher model.

Theorem 5.

Let A be an adversary making q superposition queries to QCB, of maximally blocks each (message and AD), and q queries to E. Let A succeed if it outputs q + 1 valid quadruples (A, IV, C, T ). Then the success probability of A is upper bounded as:

Pr [A succeeds] ≤ Adv STPRP E ± (•, ) (B) + 3 + c 2 n ,
where c is the constant from Corollary 1 and B an adversary playing the modified STPRP game against E ± , who uses at most 5q pre-declared tweaks, makes at most q queries in the quantum phase, saves at most (q + 1)(2 + 4)n classical bits to carry on to the next phase, and makes at most (q + 1)(2 + 2) queries in the classical phase.

In the case of the key-tweak insertion TBC of Section 4, we consider adversaries making also q queries to E ± and we have:

Pr [A succeeds] ≤ 8 5 qq 2 2 n + 3 2 nq 2 2 n .
Proof. Let G 0 be the original BZ game in which A interacts with QCB, instantiated with the TBC E and a randomly selected key k. Let G 1 be the game in which E is replaced by a family of independent random permutations Π t for all tweaks t. We first show the following lemma, where B is as described in the theorem statement.

Lemma 3. Pr

G0 [A succeeds] ≤ Pr G1 [A succeeds] + Adv STPRP E ± (•, ) (B) .
Proof. The proof of this lemma is similar, but not equivalent to the proof of Theorem 4. In G 0 , A performs q encryption queries of block length at most . Consider the i th query. From Proposition 2, in this query, the tweakable block cipher E is queried with tweaks in the set T (IV i ) having a fixed size |T (IV i )| = 5( + 1). We can therefore use A to create a strong TPRP adversary B for our modified game. B first declares the tweak-set T = ∪ q i=1 T (IV i ) with |T | ≤ 5q( + 1), and then runs A, performing at most q queries to E, with each tweak lying in T . A outputs q + 1 quadruples, which B stores in s 0 classical bits; since each quadruple has at most 2 + 4 n-bit blocks ( + 1 each for A and C, one each for IV and T ), s 0 ≤ (q + 1)(2 + 4)n. Finally, the validity of these quadruples is checked using q 2 non-adaptive classical queries to the TBC (decryption attempts); each quadruple needs at most 2 + 2 TBC calls to verify ( + 1 each for A and C), so q 2 ≤ (q + 1)(2 + 2).

If we replace E with Π for a random Π, we go from G 0 to G 1 . We therefore have Pr

G0 [A succeeds] ≤ Pr G1 [A succeeds] + Adv STPRP E ± (•, ) (B) .
Our goal is now to bound Pr G1 [A succeeds]. We run A. Let I = {IV i | 1 ≤ i ≤ q} be the q declared IVs that A uses during its encryption queries. Let also

S = {(A i , IV i , C i , T i ) | 1 ≤ i ≤ q + 1}
denote the forge-set, i.e., the q + 1 quadruples in A's output. Finally, let [[•]] denote block-length. We define the following disjoint bad events which correspond to A winning the game:

• bad-a: For some i, IV i ∈ I.

• bad-b:

For some i, k = i, IV i = IV k ∈ I, and [[C i ]] = [[C k ]] • bad-c: For some i, k = i, IV i = IV k ∈ I, [[C i ]] = [[C k ]],

and [[A

i ]] = [[A k ]]. • bad-d: For some i, k = i, IV i = IV k ∈ I, [[C i ]] = [[C k ]], and [[A i ]] = [[A k ]].
A succeeds in G 1 when the q + 1 quadruples she outputs are valid. As the q + 1 outputs shall be distinct and |I| = q, this implies that one of the bad events has occurred. We therefore have Pr

G1 [A succeeds] ≤ Pr G1 [bad-a] + Pr G1 [bad-b] + Pr G1 [bad-c] + Pr G1 [bad-d] . (5)
We bound separately the probability of each bad event in order to conclude. For a quadruple (A, IV, C, T ), with A = (A 0 , . . . , A j , pad(A * )) and C = (C 1 , . . . , C , pad(C * )), we define

M i := Π -1 (0,IV,i) (C i ), pad(M * ) := Π -1 (1,IV, ) (C * ) and M CS := pad(M * ) ⊕ i=0 M i . If the quadruple (A, IV, C, T ) is valid in game G 1 , this gives us Π (4,IV, ) (M CS ) ⊕ Π (3,IV,j) (pad(A * )) ⊕ j i=0 Π (2,IV,i) (A i ) = T . ( 6
)
From there, we have for each i ∈ {0, . . . , }

M i = Π -1 (4,IV, ) T ⊕ Π (3,IV,j) (pad(A * )) ⊕ j i=0 Π (2,IV,i) (A i ) ⊕ pad(M * ) ⊕   k =i M k   . ( 7
)
This means that from a valid quadruple (A, IV, C, T ), we can reconstruct each M i = Π -1 (0,IV,i) (C i ) without any query to Π 0,IV,i or Π -1 0,IV,i (but with access to other Π t and Π -1 t , in particular to compute pad(M * ) and the M k for k = i). Similarly, for each i ∈ {0, . . . , j}, we have

Π (2,IV,i) (A i ) = T ⊕ Π (4,IV, ) (M CS ) ⊕ Π (3,IV,j) (pad(A * )) ⊕   k =i Π (2,IV,k) (A k )   . (8)
This means that for a valid quadruple (A, IV, C, T ), we can reconstruct each

Π (2,IV,i) (A i ) without any query to Π (2,IV,i) or Π -1
(2,IV,i) (but with access to other Π t and Π -1 t ). With these 2 constructions in mind, we can bound the probability of each bad event with the following lemmas.

Lemma 4.

Pr

G1 [bad-a] ≤ 1 2 n .
Proof. Assume A outputs a quadruple (A i , IV i , C i , T i ) with IV i / ∈ I. Since IV i / ∈ I, the permutations Π 0,IV i ,0 and Π -1 0,IV i ,0 have not been queried to compute the quadruple. From the above discussion, if the quadruple is valid, we know how to construct a valid input/output pair (M i 0 , Π (0,IV i ,0) (M i 0 ) = C i 0 ) without any calls to Π 0,IV i ,0 or Π -1 0,IV i ,0 . Because Π 0,IV i ,0 is a uniformly random permutation and independent from the others, this happens with probability 1 2 n .

Lemma 5.

Pr

G1 [bad-b] ≤ 1 2 n . Proof. Assume A outputs two quadruples (A i , IV i , C i , T i ) and (A k , IV k , C k , T k ) such that IV i = IV k ∈ I, and [[C i ]] = [[C k ]].
Without loss of generality, we assume that there exists u such that IV i = IV u , and i = [[C i ]] is different from the output block length u of query number u (which is a fixed value of the query). This property must be true for i or for k. If the adversary succeeds, the quadruple (A i , IV i , C i , T i ) must be valid even though the function Π 4,IV i , i has never been queried. Let

j i = [[A i ]]. From (A i , IV i , C i , T i ), we define M i v := Π -1 (0,IV i ,v) (C i v ), • ∃u, A i u = A k u .
From the construction following Equation 7, we can construct two different input/output pairs (A i u , Π 2,IV i ,u (A i u )) and (A k u , Π 2,IV i ,u (A k u )) without additional queries to Π ± 2,IV i ,u . We conclude using a similar argument as above.

In order to conclude, notice that we have to be in one of the 2 cases above if the 2 quadruples are valid, otherwise they are equal.

The first assertion of the theorem follows from Equation 5and Lemmas 3-7.

For the second assertion specific to the key-tweak insertion TBC, we use the following additional lemma to bound Adv STPRP E ± (•, ) (B). Lemma 8. When B plays the modified STPRP game against the key-tweak insertion TBC of Section 4 and makes an additional q queries to E ± ,

Adv STPRP E ± (•, ) (B) ≤ 8 5 qq 2 2 n + 3 2 nq 2 2 n .
Proof. From Proposition 1 and the definition of Adv STPRP E ± (•, ) (B), we have

Adv STPRP E ± (•, ) (B) ≤ 8 mq 2 2 k + q 2 s 0 2 • 2 k ,
where m, q 1 , s 0 , q 2 are defined as in Proposition 1. From the description of B in the theorem statement, we can plug in the bounds m ≤ 5q , q 1 ≤ q , s 0 ≤ (q + 1)(2 + 4)n, q 2 ≤ (q + 1)(2 + 2), and put k = n to get

Adv STPRP E ± (•, ) (B) ≤ 5 qq 2 2 k + 2(q + 1) 2 ( + 1)( + 2)n 2 n .
Finally to obtain the bound in the lemma we apply the simplification 2(q + 1) 2 ( + 1)( + 2) ≤ 9q 2 2 which holds for any reasonable choice of q and (for instance, q ≥ 2, ≥ 2 and q + ≥ 6).

Substituting the bound from Lemma 8 in the first inequality of the theorem yields the second inequality, thus completing the proof.

Discussion on Security Notions

In this section, we take a broader viewpoint at suitable notions of quantum security for a combined AEAD mode. In particular, we show an attack that breaks the qIND-qCPA notion [START_REF] Mossayebi | Concrete security against adversaries with quantum superposition access to encryption and decryption oracles[END_REF][START_REF] Chevalier | On the security notions for encryption in a quantum world[END_REF] for all online modes (hence all practical AEAD modes). We also discuss the definition of blind unforgeability from [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF].

The qIND-qCPA Notion and Attacking all Online Modes

It is well-known that for any mode of encryption that XORs a keystream to the message, IND-CPA security implies IND-qCPA. In other words, a quantum adversary does not benefit from having superposition query access. This comes from the malleability of such a mode. However, such a mode also admits a well-known quantum distinguishing attack using a single superposition query (see e.g. [START_REF] Bonnetain | Hidden Structures and Quantum Cryptanalysis[END_REF]). This attack applies regardless of f , and in particular if f is a random oracle (the one-time pad).

The qIND-qCPA Notion. In [START_REF] Chevalier | On the security notions for encryption in a quantum world[END_REF], Chevalier, Ebrahimi and Vu propose the "qIND-qCPA" security game where an adversary must distinguish between a quantum oracle for E K (M ; IV ) = M ⊕ f (K, IV ) (with IV selected uniformly at random at each new query) and a random oracle. They use Zhandry's recording technique [START_REF] Zhandry | How to record quantum queries, and applications to quantum indifferentiability[END_REF] in the latter case. They also show that certain modes like CFB, OFB and CTR are insecure under this notion. By design, the qIND-qCPA security notion makes the one-time pad attack valid.

We can extend the one-time pad distinguisher in order to attack not only keystream-based modes like CTR, but all "online" modes. By "online" mode, we mean a mode of encryption in which the plaintext blocks are read and encrypted in sequence, so that the first ciphertext block C 0 depends only on the first plaintext block M 0 , the second ciphertext block C 1 depends only on M 0 , M 1 , etc. In fact, it is enough to have one bit of the complete ciphertext, say the last one, independent from one bit of the complete plaintext, say the first one. For the sake of simplicity, we consider messages of a fixed size (since we make a single query anyway). Note that a similar result was proposed in [START_REF] Carstens | On quantum indistinguishability under chosen plaintext attack[END_REF].

Lemma 10. Let E K (M ; IV ) be an encryption function of messages of length m, where the first ciphertext bit is independent of the last plaintext bit. Then there exists a quantum adversary A O making a single query to its oracle O and distinguishing E K (M ; IV ) ("real world") from a random family of permutations Π K,IV (M ) ("random world") with probability of success 3 4 ≥ 1 2 .

Proof. Our distinguisher is based on Deutsch-Jozsa's algorithm and on the postprocessing of quantum oracles of Lemma 2. The adversary fixes all the bits of M except the last one to an arbitrary value, say 0, and puts |0 + |1 in the last bit. She queries the oracle and truncates the output to its first bit. Her state becomes:

|0 |f (0) + |1 |f (1)
, where f is the first ciphertext bit as a function of the last plaintext bit (after the other bits have been fixed). She then uses Deutsch-Josza's algorithm to determine whether f is constant or non-constant. If f is constant, she decides that this is the real world and otherwise, the random world.

• In the random world (O = Π K,IV (M )), this f should remain a random function. Thus the outputs are equal only with probability 1 2 : the guess is correct with probability 1 2 . • In the real world, f is always constant. The guess is always correct.

Overall, the adversary is correct with probability 1 2 1 + 1 2 = 3 4 . Using a full block instead of a mere bit makes the success probability exponentially close to 1 with a single query, as in the one-time pad attack.

A consequence of this attack is that, while the qIND-qCPA definition seems nontrivial, it cannot be achieved by an online mode, including e.g. CBC or our proposal QCB. If we require the adversary to distinguish the mode from an ideal online mode, instead of a random permutation, our attack should not be applicable anymore. However, the definition and proofs of security may be far more involved, and we leave further exploration of this topic as an open problem.

Unforgeability for a Combined AEAD Mode

The Blind Unforgeability notion was introduced in [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF] as a replacement for BZunforgeability for MACs. In [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF], the authors prove that it is possible to create a BZ-secure MAC scheme (given by a pair Mac K , Ver K ) such that, after having made q superposition queries to some subset of the message space, one can forge the MAC of another message outside this space.

Note that the example given in [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF] is very technical, and relies heavily on the fact that the MAC treats differently different subsets of its input. This is usually not the case for practical constructions (including QCB).

Blind-unforgeability (BU) is a stronger security notion defined with the following game: the adversary is given access to a blinded version of Mac K , that returns ⊥ on some fraction of the message space. To win, the adversary has to output a valid forgery in this space. In the game, the uniform random blinding B is created by putting every message of the message space with probability . Alternatively, the adversary could choose her own blinding, but this is equivalent for inverse-polynomial values of : in [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF] (Theorem 2) the authors prove that an adversary capable of outputting a "good" forgery will still do so even if the MAC has been blinded.

BU game

Setup: the adversary selects a parameter < 1. The challenger picks a random key K, a random blinding B which is a fraction of the message space M of size .

Forgery: the adversary produces a pair (M, T ) and wins if M ∈ B and Ver K (M, T ) = . MAC queries: the adversary queries the "blinded" MAC:

M → ⊥ if M ∈ B , Mac K (M ) otherwise . ( 9
)
The following result, together with the example given in [START_REF] Alagic | Quantum-access-secure message authentication via blind-unforgeability[END_REF], shows that BU-unforgeability is a strictly stronger notion than BZ-unforgeability for a MAC.

Theorem 6 ([1], Theorem 1). Any BU-unforgeable MAC is BZ-unforgeable.

This notion is adapted for a standalone MAC. In our case, we consider a combined AEAD mode, and we would need to adapt the definition. We can propose, for example, to blind the message space. We select a subset B of message, AD and IVs (possibly the same pairs of AD and message for all IVs, or selected differently for each one). We give the adversary access to an oracle that encrypts (IV, A, M ) if it does not belong to B and otherwise, returns ⊥. The adversary then succeeds if she outputs a valid quadruple (A, IV, C, T ) whose corresponding message M is such that (IV, A, M ) ∈ B .

The main difference with the original BU definition is that the condition of success relies on the message M , which is not necessarily an output of the forgery (the adversary can forge on an unknown message M ). Despite that, we conjecture that this definition is non-trivial and that it might be proven for QCB. This proof would likely be more technical than our original one, and we leave it as an open problem.

Conclusion

In this paper, we designed the first AEAD of rate one with quantum security guarantees. With a definition similar to TAE and OCB, our proposal, QCB, retains high security guarantees as soon as it is used with a quantum-secure tweakable block cipher. We explicited this security requirement and proposed a construction based on a block cipher, in the ideal cipher model: the key-tweak insertion of Section 4.

In the classical setting, the LRW construction provides a TBC of rate one (one block cipher call per TBC call) from a PRP assumption. Ours requires related-key security for the underlying block cipher. Although we do not rule out the possibility of a rate-one TBC without related-key security, the LRW approach does not seem applicable.

Thus, an interesting open question is whether it is possible to build a postquantum AEAD of rate one from a block cipher, with a qPRP assumption only. It may be possible to obtain directly the security without relying explicitly on a secure TBC, though this was the subject of our first attempt, which failed due to a new attack on OCB with a single query.

In our security proofs, we used the IND-qCPA and BZ security notions for indistinguishability and unforgeability. We note that other security definitions have been proposed in the more recent literature and seem worth investigating.

Let G 1 be a hybrid game in which E ± is replaced by a family of permutations Π t1 , . . . , Π tm , and E ± is replaced by E ± , which is equal to E ± for all keys, except K ⊕ t 1 , . . . , K ⊕ t m , where we constrain:

E ± K⊕ti = Π ti . Game G1[K] ∀i ∈ [m], Πt i $ ← -Pn. ∀K ∈ K, E K $ ← -Pn. ∀i ∈ [m], EK⊕t i := Πt i , ∀K / ∈ {K ⊕ ti} i∈[m] , E K := E K . Run A Π ± (•, ),E ± ( )
.

Notice that if we define E K (t, x) := E t⊕K (x), we have in this game that

∀i ∈ [m], ∀x, E K (t i , x) = Π ti (x), which implies that we have A E ± K (•, ),E ± ( ) = A Π ± (•, ),E ± ( )
when we only query Π t (x) for tweaks t = t 1 , . . . , t m . Let φ K be the final state of A 1 in game G 0 [K] and χ K its final state in game G 1 [K].

Lemma 11. For any key

K ∈ K, φ K = χ K . ( 10
)
Proof. During the first phase, since the quantum queries concern only tweaks of the pre-declared set, the two games are syntactically equivalent. The only change is in the order in which we select the new permutations at random. In G 0 , we first pick E K for each K ∈ K and we define E accordingly. In G 1 [K], we select first randomly the permutations for E and then the other permutations

E K for K / ∈ {K ⊕ t i } i∈[m] .
Next, we create another hybrid G 2 in which A interacts with the family Π, and the unmodified E ± , which is then independent of Π.

Game G2 ∀i ∈ [m], Πt i $ ← -Pn. ∀K ∈ K, E K $ ← -Pn. ∀K ∈ K, EK := E K . Run A Π ± (•, ),E ± ( ) .
Notice that it is equivalent to write directly E K $ ← -P n in this game but writing it the way we did will make notations easier in the proof. Let |ψ be the final state of A 1 in game G 2 . Using a query magnitude argument, we will bound the difference between |ψ and φ K on average over K. In other words, A 1 does not see the difference between the real and ideal worlds. Lemma 12. Consider a fixed choice of E and Π. Let φ K and |ψ be the final states of A 1 , respectively in G 1 [K] and G 2 . Then: We then take the average over K:

E K $ ← -K φ K -|ψ ≤ 2 mq 2 2 k . ( 11
E K $ ← -K φ K -|ψ ≤ 2 mq 2 2 k .
Now, we consider the complete run of A 1 followed by A 2 . Let us fix a choice of E ± , Π ± and K.

Pr[G 0 [K, E ± , Π ± ] ⇒ 1] -Pr[G 2 [E ± , Π ± ] ⇒ 1] ≤ Pr[A E ± •⊕K (•) 2 φ K ⇒ 1] -Pr[A Π ± (•, ) 2 |ψ ⇒ 1]
We introduce the distance between φ K and |ψ (still with a fixed choice of E ± and Π ± ):

≤ Pr[A E ± •⊕K (•) 2 φ K ⇒ 1] -Pr[A E ± •⊕K (•) 2 |ψ ⇒ 1] + Pr[A E ± •⊕K (•) 2 |ψ ⇒ 1] -Pr[A Π ± (•, ) 2 |ψ ⇒ 1] ≤ 4 A E ± •⊕K (•) 2 φ K -A E ± •⊕K (•) 2 |ψ + Pr[A E ± •⊕K (•) 2 |ψ ⇒ 1] -Pr[A Π ± (•, ) 2 |ψ ⇒ 1] ≤ 4 φ K -|ψ + Pr[A E ± •⊕K (•) 2 |ψ ⇒ 1] -Pr[A Π ± (•, ) 2 |ψ ⇒ 1] .

Since we are interested in bounding E

E ± Pr K [G 0 ⇒ 1] -Pr Π ± [G 2 ⇒ 1] ,
the first term on average over K will be bounded by 8 mq 2 2 k . Now we have to study the run of A 2 , which is completely classical (|ψ is measured before the run). We have

|ψ = A Π ± (•, ),E ± ( ) 1 |0
since |ψ was obtained by running A 1 in game G 2 (where there is no key). Thus when we measure it, its result depends on Π ± and E ± . Note also that in A

E ± •⊕K (•) 2
|ψ , we may assume that Π ± and E ± are modified to agree on the tweaks of the pre-declared set (as above in the first phase). Thus, the adversary cannot distinguish simply by re-querying a tweak of the first phase. We consider the following setting: after step 1, A 1 outputs z which has s 0 bits. Then A 2 takes z as input and performs q 2 non adaptive queries (t 1 , x 1 ), . . . , (t q2 , x q2 ) to E ± . We require these queries to be a deterministic function of z. We want to bound

E E ± ,Π ± ,z,K Pr[A E ± •⊕K (•) 2 (z) ⇒ 1] -Pr[A Π ± (•, ) 2 (z) ⇒ 1]
where z may depend on E ± and K is independent of everything. For each z, we can extract deterministically q 2 non adaptative queries (t 1 , x 1 ), . . . , (t q2 , x q2 ) (that depend on z) that will be done to E ± . For a choice of key K, this means A 2 queries E K⊕t1 (x 1 ), . . . , E K⊕tq 2 (x q2 ). We therefore define for each z and K the set S z K = {K ⊕ t 1 , . . . , K ⊕ t q2 } of queried keys. For each z, each K 0 ∈ K appears in exactly q 2 different sets S z K (the sets S z K0⊕ti for i ∈ {1, . . . , q 2 }). With our notations, we can rewrite the above as

E z,K,E ± S z K Π ± S z K Pr K [A E ± •⊕K (•) 2 (z) ⇒ 1] -Pr[A Π ± (•, ) 2 (z) ⇒ 1]
where taking the expectation of E ± S z K means we only specify the function E K0 for K 0 ∈ S z K , and similarly for Π ± S z K . This is equivalent to the previous quantity since for a fixed z, K A 2 makes calls only to functions E ± K0 for K 0 ∈ S z K . Let X K be the distribution associated to E K for each K ∈ {0, 2 k -1}. Because we are in the IC model, each X K is the uniform distribution over the set P n of permutations on n bits. Let X = X 0 , . . . , X 2 k -1 and let s p = log 2 (|P n |). Let O be the output distribution after the first step on s 0 bits and let X K (O = z) be the distribution of E K conditioned on A 1 outputting z after the first step. We have H(X) = 2 k s p and H(X|O) ≥ H(X) -H(O) ≥ 2 k s p -s 0 Let X S z K = X K⊕t1 , . . . , X K⊕tq 2 and X S z K (O = z) = X K⊕t1 (O = z), . . . , X K⊕tq 2 (O = z). Let also X <K = X 0 , . . . , X K-1 . We have the output z, with a random permutation Π (which means that we replace each X K0 (O = z) with X K0 ).

Remark 2. Making the proof work for general adaptative tweaks, which are chosen by the adversary depending on her current state, turned out to be much more difficult than we initially anticipated. In particular, our query magnitude argument cannot be used as is, since we do not know in advance the positions at which we would like to change the outputs of E ± . Despite that, we conjecture that the same bound can be achieved for adaptive tweaks, as there does not seem to be any better attack. We leave this as an open question.

The bound given by Proposition 1 is not tight because of the √ . However, for a constant success probability, the first term in the bound is matched by the following attack.

Lemma 13. There exists a quantum algorithm that for any E, makes q queries to the TBC, q queries to E and succeeds in recovering the key of a key-tweak insertion TBC with probability O qq 2 2 k (thus distinguishing the instance from a random family of permutations).

Proof. The attack runs in three phases:

1. The adversary makes q queries of the form E K⊕i (0) for i = 0, . . . , q -1 and stores the couples E K⊕i (0), E K⊕i⊕1 (0) in a database D. 2. Using Grover's algorithm, the adversary searches for an element z such that (E z (0), E z⊕1 (0)) ∈ D. As D is of size q, Grover search would require O 2 n q queries to succeed with constant probability. After q queries, the probability of success is O qq 2 2 k .

3. Let t, z be the obtained pair such that E z (0) = E K⊕t (0) and E z⊕1 (0) = E K⊕t⊕1 (0). The use of two elements makes the probability of a false positive (a random collision) exponentially low. The adversary then concludes that z = K ⊕ t i.e. K = z ⊕ t and checks that the key was correctly guessed.

If the TBC queried is a random family of permutations, then no solution exists at Step 2. After running q iterations of Grover search, the attacker measures a random element that does not pass the check.

Remark 3. The attack of Lemma 13 works even if the adversary does not control the tweaks queried. It requires O (q) quantum-accessible classical memory. If the tweaks are controlled (but still non adaptatively), the offline Simon's algorithm of [START_REF] Bonnetain | Quantum attacks without superposition queries: The offline Simon's algorithm[END_REF] reduces the memory down to O k 2 qubits. The attack then is exactly the related-key attack of [START_REF] Bonnetain | Quantum attacks without superposition queries: The offline Simon's algorithm[END_REF]Section 6.1]

  Enc K is a standard oracle for Enc K with messages of length m, AD of length a and a fixed IV ∈ IV:

Algorithm 1 QCB 1 : 3 :

 113 Input: message M , associated data A, IV , key K Requirements: Initialization vectors should not be reused Output: ciphertext C, tag T Pad the initialization vector if necessary 2: Split M into full blocks M 0 , M 1 , . . . M and a final block M * (partial or empty) Split A into A 0 , A 1 , . . . A j , A * 4: for all i = 0 to do 5:

  Encryption queries: A chooses a message and AD pair (M, A), the encryption oracle encrypts (IV, M, A) with the current IV and returns the output (C, T ) to A. Queries can be in superposition. Challenge query: A chooses two classical message/AD pairs (M 0 , A 0 ), (M 1 , A 1 ) of the same length and sends them to the challenger. The challenger encrypts (IV, M b , A b ) with the current IV and returns the output (C b , T b ). Guess: A outputs a bit b and wins if b = b .

Lemma 9 (

 9 [START_REF] Anand | Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation[END_REF], informal). Define an encryption mode asE K (M ; IV ) = M ⊕ f (K, IV ) where IV is a randomly chosen IV and f is any function. If E K is IND-CPA, then it is also IND-qCPA.Informal. Given a quantum adversary B that attacks the IND-qCPA security notion, we can construct a (quantum) adversary A that attacks the IND-CPA security of the mode. A simulates B. When B wants a quantum query, A queries E K (0; IV ) and XORs this value on the input register of B.

Definition 1 (Euclidean distance). The

  Euclidean distance between |φ = α i |i and |ψ = β i |i is given by: |φ -|ψ = i |α i -β i | 2 . Two quantum states |φ = α i |i and |ψ = β i |i , obtained after running an adversary in two different scenarios, incur two distributions D and D over the states in the computational basis (we could also take another basis, without any change, since composing by a unitary operator leaves the distance unchanged). These distributions are such that D(i) = |α i | 2 and D (i) = |β i | 2 . The total variation distance between D and D is defined as i |D(i) -D (i)| and equal to i ||α i | 2 -|β i | 2 |. From Lemma 3.6 in [7], we obtain:

Theorem 1 (Adapted from [6], Theorem 3.3). Let

  A be a quantum algorithm that makes q queries to an oracle O and let |ψ 0 , . . . , |ψ q be the current state before each query (|ψ q is the final state). Let O be an oracle that is the same as O, except on some subset D of its inputs, A be the same as A, except that every query to O is replaced by a query to O , and |ψ i the state of A . At each step of the circuit computation, we let |x |y |a denote the basis states, where |x is the input to O (or O ), |y is the output register and |a the rest of the qubits. Let P D be the projector on the basis states such that x ∈ D. Then:

	Considering an oracle
	O with arbitrarily defined input and output registers, we modify O on a subset
	D of its inputs to make the oracle O . If an algorithm asks queries to O, but puts
	only "low amplitude" on the inputs of D, then changing O into O does not have
	any significant impact on the final state.

)

  Proof. Let G 1 [K, E , Π] and G 2 [E , Π] be the games G 1 [K] and G 2 where we additionally fix all the choices of E k and Π ti . Let us also fix such a choice E and Π. Let |ψ i the state ofA 1 in G 2 [E , Π] before the i th query to E ± ( ) and φ K i the state of A 1 in G 1 [K, E , Π] at the same point. Between the two games G 1 [K, E , Π] and G 2 [E , Π], we change the choice of E ± K only for K ∈ {K ⊕ t i } i∈[m]. After q queries, we therefore have by Theorem 1:φ K q +1 -|ψ q +1 ≤ 2 1≤i≤q |P K,t1,...,tm |φ i | ,where P K,t1,...,tm is the projector on the part of the input that corresponds to a key k ∈ {K ⊕ t i } i∈[m] . When K cycles over all possible keys, K = {0, 1} k , the set {K ⊕ t i } i∈[m] describes {0, 1} k exactly m times. Thus, we have:

K∈K

|P K,t1,...,tm

|φ i | 2 = m x∈{0,1} k |P x |φ i | 2 = m .

By normalization, and by Jensen's inequality:

K∈K |P K,t1,...,tm |φ i | 2 ≤ |K| K∈K |P K,t1,...,tm |φ i | 2 = 2 k m .

f For example, indistinguishability under quantum encryption queries can be achieved by the Counter Mode from a classical PRP assumption[START_REF] Anand | Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation[END_REF].

g Three versions of OCB have been proposed. We focus here on the last one, OCB3, while all three suffer from similar superposition attacks.

Acknowledgements. We thank the reviewers from EUROCRYPT 2021, CRYPTO 2021 and ASIACRYPT 2021 for their helpful feedback and insights, which helped us improve the paper and correct technical errors. 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).

pad(M

This means we can construct a pair (M i CS , Π 4,IV i , i (M i CS )) without any calls to Π 4,IV i , i or Π -1 4,IV i , i . Since Π 4,IV i , i is a uniformly random permutation and independent from the others, this happens with probability 1 2 n . Lemma 6.

Pr

Without loss of generality, we assume that there exists u such that IV i = IV u , and

is different from the AD block length j u queried in query u. (This happens either for index i or index k). We focus on this quadruple (A i , IV i , C i , T i ) for which Π 3,IV i ,j i has never been queried. We

If the quadruple is valid, we have

This means we can construct a pair (pad

)) without any calls to Π (3,IV i ,j i ) or its inverse. Since it is a uniformly random permutation and independent from the others, this happens with probability 1 2 n . Lemma 7. Let c be the constant of Corollary 1, we have

) and similarly for C k , A k . Assume the 2 quadruples are valid, we distinguish 2 cases:

According to the construction following Equation 7, we can construct two different input/output pairs

without additional queries to Π ± 0,IV i ,u . However, there has been only 1 call to Π 0,IV i ,u during the game (since each IV in the challenge queries is different). Therefore, we have from Corollary 1 that this can happen with probability at most c 2 n .

Appendix

A Proof of Security of the Key-tweak Insertion TBC

In this section, we let E K (T, x) denote E K⊕T (x), the key-tweak insertion TBC.

We need here the ideal cipher model: E is selected at random from all ciphers. We recall Proposition 1:

Proposition 1. Let A be an adversary who makes q 1 quantum queries to an oracle implementing E ± K or Π ± with a pre-declared set of tweaks of size m, and q queries to E ± , followed by outputting s 0 bits and making q 2 classical queries to the same oracle. Then:

Proof of Proposition 1. Note that in the second phase, the adversary does not query the ideal cipher oracle E ± . Let A 1 be the part of the adversary that runs the first phase (quantum queries) and A 2 that runs the second phase (classical queries).

Let t 1 , . . . , t m be the tweaks of the declared set. This list is not deterministic, but it is given by the game, and does not depend on the adversary's state (in particular, it is non-adaptive). Thus, it suffices to reason with an arbitrary list and to take the average over all possibilities (the bound obtained will be the same in all cases). Note that the definition of our hybrid games will be dependent on this list.

Let G 0 be the "real world" in which A interacts with E ± and E ± , for K $ ← K. We also define the game G 0 [K] where a key K is fixed.

We have by definition:

where to have the first inequality, we write

From there, we have

We then use Pinsker's inequality to bound the Statistical distance between X K (the uniform distribution) and the one obtained conditioned on the output z.

The relation between the relative entropy D and the difference between the entropies comes from the fact that X S z K is the uniform distribution. We then use concavity of the root function.

We bound the distance between the 2 games by bounding the difference when we replace each E K0 for K 0 ∈ S z K on average over the choice of keys K and over