Paul Frixons

María Naya-Plasencia

André Schrottenloher

Quantum Boomerang Attacks and Some Applications

Keywords: boomerang attack, post-quantum security, mixing boomerang attack, SAFER++, AES

In this paper, we study quantum key-recovery attacks on block ciphers. While it is well known that a quantum adversary can generically speed up an exhaustive search of the key, much less is known on how to use specific vulnerabilities of the cipher to accelerate this procedure. In this context, we show how to convert classical boomerang and mixing boomerang attacks into efficient quantum key-recovery attacks.

In some cases, we can even obtain a quadratic speedup, the same as simple differential attacks. We apply this technique to a 5-round attack on SAFER++.

Introduction

In symmetric cryptography, cryptanalysis is the base of the confidence we have in the primitives we use. In order to consider a primitive secure, we need to constantly evaluate it with respect to all known attack families. One of the most well known families of attacks is boomerang attacks, introduced by Wagner in [START_REF] Wagner | The boomerang attack[END_REF]. They are a particular type of differential attacks that, instead of considering a long differential trail in the primitive (a propagation of differences from the plaintext through the ciphertext), combine several short ones that have high individual probabilities. While differential attacks usually consider pairs of plaintexts having a certain difference, boomerang attacks use quartets instead. They have shown to be effective (or the most effective known attacks) against several primitives like [START_REF] Dunkelman | A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3g telephony[END_REF][START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF], and have seen many improvements, like recently [START_REF] Cid | Boomerang connectivity table: A new cryptanalysis tool[END_REF].

The quantum security of symmetric primitives has attracted an increasing interest in the last few years. Some works have targeted the security of generic constructions, for example [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][START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF], while others have studied the security of actual designs [START_REF] Bonnetain | Quantum security analysis of AES[END_REF][START_REF] Hosoyamada | Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound[END_REF][START_REF] Bonnetain | Quantum period finding against symmetric primitives in practice[END_REF]. Many have proposed quantum versions of popular classical attacks, like for instance [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF][START_REF] Bonnetain | On quantum slide attacks[END_REF].

In this paper, as in most of these previous works, we consider key-recovery attacks in the single secret-key setting. Here it is well-known that Grover's quantum search algorithm [START_REF] Grover | A fast quantum mechanical algorithm for database search[END_REF] can be used to quadratically speed up the exhaustive search of the key. However, when the design under study admits some vulnerability (e.g., a classical attack exists), a faster quantum key-recovery procedure might exist. Designing such procedures from classical design patterns is often a non-trivial task. It is known that if a classical attack can be represented as a sequence of nested exhaustive searches, then it can be converted into a sequence of quantum searches: this framework was applied in [START_REF] Bonnetain | Quantum security analysis of AES[END_REF] to Square [START_REF] Daemen | AES proposal: Rijndael[END_REF][START_REF] Ferguson | Improved cryptanalysis of rijndael[END_REF] and DS Meet-in-the-Middle attacks [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF][START_REF] Derbez | Improved key recovery attacks on reduced-round AES in the single-key setting[END_REF]. But not all attacks can be covered this way, and many of them still seem difficult to translate.

Boomerang Attacks. In this paper, we consider Boomerang attacks, which form a particular type of differential attacks introduced by Wagner in [START_REF] Wagner | The boomerang attack[END_REF]. We study how to build an efficient quantum version of boomerang attacks and of mixing boomerang attacks [START_REF] Dunkelman | The retracing boomerang attack[END_REF] recently introduced in the context of AES. We propose, for the first time, efficient quantum boomerang attacks, and we apply them to several reduced-round versions of well known ciphers.

The quantum attacks studied in this paper are also based on quantum search. One should note that, since quantum search always provides a quadratic speedup, our procedures admit a quadratic speedup at best. By comparing with the quadratic speedup of exhaustive key search, it follows that we will not be able to attack more rounds than in the classical setting: any quantum attack in our framework can be converted back into a valid classical attack. Though this result can seem rather negative at first sight, our new attacks, like previous works with similar conclusions [START_REF] Bonnetain | Quantum security analysis of AES[END_REF][START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF], tend to show that block ciphers should be assumed to retain half of their bits of classical security against quantum adversaries, even when this security has been reduced with respect to the generic key search.

Outline. In Section 2, we give a broad introduction to the boomerang attacks we will quantize later and detail the quantum tools that we use within this paper. In Section 3, we present quantum algorithms for boomerang distinguishers, lastround attacks and mixing boomerang attacks. In Section 4, we show an attack on 5 rounds of the block cipher SAFER++ (where the best classical attack reaches 5.5 rounds). In Section 5 we study a related-key attack against AES-256, with more details given in Appendix B. We conclude the paper in Section 6.

Preliminaries

In this section, we introduce the classical Boomerang attack from [START_REF] Wagner | The boomerang attack[END_REF] and the Mixing Boomerang attack from [START_REF] Dunkelman | The retracing boomerang attack[END_REF]. We give generic formulas for their time complexity depending on the parameters of the cipher attacked. Next, we introduce our quantum tools. We stress that knowledge of quantum computing is not required to understand our work, as we will use standard quantum algorithms (such as Grover search) as black-box components, and design our attacks from a rather abstract perspective.

Throughout this paper, we consider an 𝑛-bit block cipher 𝐸, with unknown key 𝑘. Standard block ciphers (SPNs or Feistel schemes) are built by iterating a round function, and we will sometimes decompose 𝐸 into subciphers, e.g., 𝐸 = 𝐸 2 ∘ 𝐸 1 where 𝐸 1 forms the 𝑟 1 first rounds and 𝐸 2 the 𝑟 2 last rounds.

Boomerang cryptanalysis is a subset of differential cryptanalysis, which studies the propagation of differences in a cipher. Given a cipher (or subcipher) 𝐸, and a pair of differences (𝛥 in , 𝛥 out ), we say that 𝛥 in → 𝛥 out is a differential for 𝐸 of probability:

Pr ( 𝛥 in 𝐸 -→ 𝛥 out ) = Pr 𝑋 (𝐸(𝑋 ⊕ 𝛥 in ) ⊕ 𝐸(𝑋) = 𝛥 out ) .
Since 𝐸 is a keyed function, the probability of a differential depends on the choice of key. In the analysis, it is usually computed on average over the key.

When running an attack, we consider a black box with a fixed given key. We then assume that the differential probability is equal to the analyzed average (even if there is a small variation in practice, we may run the attack again with another estimate -this is valid for classical as well as quantum attacks).

The Classical Boomerang Attack

We briefly describe the boomerang distinguisher introduced in [START_REF] Wagner | The boomerang attack[END_REF] and the lastround key-recovery attack that can be based on it. The notation that we introduce here (𝐸, 𝑝, 𝑞, 𝛼, . . .) will be kept throughout the paper.

Boomerang Distinguisher. As above, let 𝐸 be a block cipher of block size 𝑛 and key size 𝑘, that can be decomposed into: 𝐸 = 𝐸 2 ∘ 𝐸 1 . We assume that each part has a high-probability differential: 𝛼 → 𝛽 for 𝐸 1 and 𝛿 → 𝛾 for 𝐸 -1 2 .

Pr ( 𝛼

𝐸1 --→ 𝛽 ) = 𝑝 ↓ , Pr ( 𝛽 𝐸 -1 1 ---→ 𝛼 ) = 𝑝 ↑ , Pr ( 𝛿 𝐸 -1 2 ---→ 𝛾 ) = 𝑞 .
The distinguisher is given in Algorithm 1. It uses 4 𝑝 ↓ 𝑝 ↑ 𝑞 2 encryptions, decryptions, and negligible memory. We can check its correctness as follows (see also Figure 1 for the notations):

Step 3: using the differential on 𝐸 1 ; with probability

𝑝 ↓ , 𝐸 1 (𝑃 1 ) ⊕ 𝐸 1 (𝑃 2 ) = 𝛽 = 𝐸 -1 2 (𝐶 1 ) ⊕ 𝐸 -1 2 (𝐶 2 )
Step 4: using the differential on 𝐸 -1 2 ; with probability 𝑞 2 , 𝐸 -1

2 (𝐶 3 )⊕𝐸 -1 2 (𝐶 1 ) = 𝛾 and 𝐸 -1 2 (𝐶 4 )⊕𝐸 -1 2 (𝐶 2 ) = 𝛾.
Thus, by summing these equations:

𝐸 -1 2 (𝐶 3 )⊕ 𝐸 -1 2 (𝐶 4 ) = 𝐸 -1 2 (𝐶 1 ) ⊕ 𝐸 -1 2 (𝐶 2 ) = 𝛽. Step 5: since we have established 𝐸 -1 2 (𝐶 1 ) ⊕ 𝐸 -1 2 (𝐶 2 ) = 𝛽 with probability 𝑝 ↓ 𝑞 2 , it remains to satisfy the differential on 𝐸 -1
1 , and we obtain

𝑃 3 ⊕𝑃 4 = 𝛼 with probability 𝑝 ↑ × 𝑝 ↓ 𝑞 2 .
Then, the full path is satisfied with probability (𝑝 ↓ 𝑝 ↑ 𝑞) 2 instead of 2 -𝑛 for a random permutation, and making 1/(𝑝 ↓ 𝑝 ↑ 𝑞) 2 trials is enough to determine the case. Usually, we also have 𝑝 ↓ = 𝑝 ↑ = 𝑝 and this formula simplifies into (𝑝𝑞) 2 .

Algorithm 1 Boomerang Distinguisher

Input: oracle access to 𝐸 = 𝐸2 ∘ 𝐸1, and its inverse (or a random permutation) Output: "𝐸" or "Random" 1: Repeat (𝑝 ↑ 𝑝 ↓ 𝑞) -2 times ◁ (probability of success of 1 2 ) 2:

Select 𝑃1 at random and set 𝑃2 = 𝑃1 ⊕ 𝛼 3:

Encrypt: 𝐶1 = 𝐸(𝑃1) and 𝐶2 = 𝐸(𝑃2) 4:

Compute: 𝐶3 = 𝐶1 ⊕ 𝛿 and 𝐶4 = 𝐶2 ⊕ 𝛿 5:

Decrypt: 𝑃3 = 𝐸 -1 (𝐶3) and 𝑃4 = 𝐸 -1 (𝐶4) 6:

if 𝑃4 = 𝑃3 ⊕ 𝛼 then return "E" 7: EndRepeat 8: return "Random" Fig. 1. Last-round key recovery Key Recovery on the Last Round. We now explain how to build a key-recovery attack using this boomerang distinguisher.

We append one (or more) additional rounds 𝑅 to the cipher, which is now 𝐸 = 𝑅 ∘ 𝐸 2 ∘ 𝐸 1 (if the additional round is at the beginning, consider 𝐸 -1 ). Let 𝐷 fin denote the set of differences that can be obtained from 𝛿 after the additional rounds, 𝑝 out the probability that we get 𝛿 back from an element in 𝐷 fin by computing the last rounds backwards, and 𝑘 out the number of key bits involved in these additional rounds. We need 𝐷 fin to be a vector space. This is usually the case as most of the time, non-zero components of 𝛿 become unknown after a passage through an S-Box. This property is used to make data structures of the form {𝑋 ⊕ 𝛥/𝛥 ∈ 𝐷 fin }, from which we can extract quadratically many pairs with differences in 𝐷 fin :

∀𝛥 1 , 𝛥 2 , (𝑋 ⊕ 𝛥 1 ) ⊕ (𝑋 ⊕ 𝛥 2 ) = 𝛥 1 ⊕ 𝛥 2 ∈ 𝐷 fin .
To simplify for now, we assume that Algorithm 2 detects a good guess of the 𝑘 out key bits using the boomerang distinguisher. We will now explain its correctness and compute its average time complexity (up to a constant factor).

We start by generating a structure 𝑆 of 1 √ 𝑝𝑜𝑢𝑡𝑝𝑞 ciphertexts with differences in 𝐷 fin . This first step costs a time and memory: , and we know that the actual key 𝐾 out occurs in one of these triplets, because one of the pairs went through the boomerang. Thus, if we have:

|𝐷 fin | 2 𝑛 2 𝑘 out 𝑝out (𝑝𝑞) 2
≤ 2 𝑘out , we have reduced the number of possibilities for 𝐾 out . We perform an exhaustive search over the remaining 𝑘 -𝑘 out bits of key. We obtain a key-recovery attack of total time complexity:

1 √ 𝑝 out 𝑝𝑞 log ( 1 √ 𝑝 out 𝑝𝑞 ) + |𝐷 fin | 2 𝑛 1 𝑝 out (𝑝𝑞) 2 ( 𝐶 out + 𝑝 2 out 2 𝑘 ) , (1)
in number of queries to 𝐸 and 𝐸 -1 or evaluations of the cipher. Note that 𝐶 out is counted relatively to the cost of an evaluation of 𝐸. The memory used is:

max ( 2 √ 𝑝out𝑝𝑞 , |𝐷 fin | 2 𝑛 2 𝑘 out 𝑝out (𝑝𝑞) 2
) . The data used is :

2 √ 𝑝out𝑝𝑞 .
Remark 1. Another situation commonly encountered in Boomerang attacks is when two (or more) boomerang pairs occur within the trials. In that case, it is possible to recognize immediately the good guess of 𝐾 out , as the only one that appears in two (or more) triples in the list 𝐿 triplets .

Mixing Boomerang Attacks

This variant of boomerang attacks [START_REF] Dunkelman | The retracing boomerang attack[END_REF] is related to mixture distinguishers.

Distinguisher. As in Section 2.1, the cipher is decomposed as 𝐸 = 𝐸 2 ∘𝐸 1 and we assume that a good (truncated) differential 𝛼 → 𝛽 exists on 𝐸 1 with probability 𝑝 ↓ forwards and with probability 𝑝 ↑ backwards. We further assume that 𝐸 2 can be divided into a "left" and a "right" part 𝐸 2 = (𝐸 2,𝐿 , 𝐸 2,𝑅 ) (see the notations on Figure 2).

The distinguisher relies on the independence of 𝐸

{ 𝐸 -1 2,𝐿 (𝐶 1,𝐿 ) ⊕ 𝐸 -1 2,𝐿 (𝐶 2,𝐿 ) = 𝛽 𝐿 𝐸 -1 2,𝑅 (𝐶 1,𝑅 ) ⊕ 𝐸 -1 2,𝑅 (𝐶 2,𝑅 ) = 𝛽 𝑅 . (2)
Thus, by definition of 𝐶 3 , 𝐶 4 , we also have 𝐸 -1 2 (𝐶 3 ) ⊕ 𝐸 -1 2 (𝐶 4 ) = 𝛽. Finally in Step 3, with probability 𝑝 ↑ , 𝛽 gets mapped to 𝛼. After (𝑝 ↓ 𝑝 ↑ ) -1 iterations, we obtain a valid quartet with probability 1/2.

Attack on First Round. We append one or more additional rounds 𝑅 before those covered by the distinguisher. Similarly as before, we write 𝐸 = 𝐸 2 ∘ 𝐸 1 ∘ 𝑅. We let 𝐷 start denote the set of differentials that can lead to 𝛼 for the additional rounds 𝑅, 𝑝 in the probability to get 𝛼 from an element of 𝐷 start and 𝑘 in the number of bits of the key involved in the additional rounds. Step 1: Generating Pairs. We generate a list of

1 𝑝in𝑝 ↓ 𝑝 ↑ pairs of plaintexts (𝑃 1 , 𝑃 2 )
such that their difference is in 𝐷 start . Again, there can be one or multiple structures, but as the term 1 𝑝in𝑝 ↓ 𝑝 ↑ (the number of pairs) will appear in the complexity, there is no difference between these two cases.

For each pair (𝑃 1 , 𝑃 2 ) we compute:

(𝐶 1 = 𝐸(𝑃 1 ), 𝐶 2 = 𝐸(𝑃 2 )), (𝐶 3 = (𝐶 1,𝐿 , 𝐶 2,𝑅 ), 𝐶 4 = (𝐶 2,𝐿 , 𝐶 1,𝑅 ), (𝑃 3 = 𝐸 -1 (𝐶 3 ), 𝑃 4 = 𝐸 -1 (𝐶 4 )) . (3)
For each pair, we have

𝑅(𝑃 1 ) ⊕ 𝑅(𝑃 2 ) = 𝛼 with probability 𝑝 in . Then, (𝐸 2 ∘ 𝐸 1 ) -1 (𝐶 3 ) ⊕ (𝐸 2 ∘ 𝐸 1 ) -1 (𝐶 4 ) = 𝛼 with probability 𝑝 ↓ 𝑝 ↑ .
Thus, we expect that one pair satisfies the boomerang distinguisher; by decrypting through 𝑅 we fall back on 𝐷 start .

Thus, we keep only the pairs (𝑃 1 , 𝑃 2 ) such that 𝑃 3 ⊕ 𝑃 4 ∈ 𝐷 start , among which the pair that went through the boomerang must remain. We get a list of Step 2: Sieving Key Bits. For each one of the kept pairs (𝑃 1 , 𝑃 2 ), we determine the values of 𝐾 in (the 𝑘 in bits of key that intervene in 𝑅) such that 𝑃 1 , 𝑃 2 and 𝑃 3 , 𝑃 4 both lead to a difference 𝛼 through 𝑅. The average expected number of possible values for 𝐾 in for each pair is thus 2 𝑘in (𝑝 in ) 2 . We let 𝐶 in denote the cost of finding all these possible values. At a cost of |𝐷start|

2 𝑛 1 𝑝in𝑝 ↓ 𝑝 ↑ 𝐶 in computations, we get a list of |𝐷start| 2 𝑛 1 𝑝 ↓ 𝑝 ↑ 2 𝑘in 𝑝 in elements (𝑃 1 , 𝑃 2 , 𝐾 in ) . If we have: |𝐷 start | 2 𝑛 1 𝑝 ↓ 𝑝 ↑ 2 𝑘in 𝑝 in < 2 𝑘in , (4)
then we have reduced the number of possible values for 𝐾 in and we do an exhaustive search of the remaining 𝑘 -𝑘 in bits of key. The attack has a total time complexity:

1 𝑝 in 𝑝 ↓ 𝑝 ↑ + |𝐷 start | 2 𝑛 1 𝑝 in 𝑝 ↓ 𝑝 ↑ ( 𝐶 in + 𝑝 2 in 2 𝑘 ) , (5)
in number of queries to 𝐸 and 𝐸 -1 or evaluations of the cipher. Note that 𝐶 in is counted relatively to the cost of an evaluation of 𝐸.

Quantum tools

In this paper, we consider quantum algorithms written in the quantum circuit model (see [START_REF] Nielsen | Quantum computation and quantum information[END_REF] for an introduction). A quantum circuit starts with a pool of qubits initialized in a basis state. The state is modified through the application of quantum gates. The time complexity is the number of gates of the circuit. The memory complexity is the width of the circuit, or the number of qubits.

Complexity Estimations. A quantum procedure qualifies as an attack if it runs with a lower time complexity than the corresponding quantum generic procedure (in this paper, key-recovery via Grover's algorithm). Since we only need to perform comparisons, we can use as cost metric the evaluation of the primitive that is attacked. In our case, the time is counted in evaluations of the cipher 𝐸 as a quantum circuit, and the memory in multiples of its block size 𝑛.

Quantum RAM. We shall specify whether or not our algorithms require the quantum RAM model, which can be seen as the quantum counterpart of classical random-access. In this model, a "qRAM" gate of cost 1 allows to perform memory lookups in superposition (see [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF]).

Amplitude Amplification. We will use as a black-box the Amplitude Amplification framework of [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF], which generalizes Grover's quantum search [START_REF] Grover | A fast quantum mechanical algorithm for database search[END_REF].

Theorem 1 ([8], Theorem 2 and 4). Let 𝒜 be a quantum algorithm that uses no intermediate measurements, let 𝑓 : 𝑋 → {0, 1} be a boolean function that tests if an output of 𝒜 is "good". Let 𝑎 be the success probability of 𝒜. Let 𝜃 𝑎 = arcsin √ 𝑎 and 0 < 𝜃 𝑎 ≤ 𝜋 2 . There exists a quantum algorithm Amplify(𝒜, 𝑓 ) that runs in time:

⌊ 𝜋 4𝜃𝑎 ⌋ (2𝑇 𝒜 + 𝑇 𝑓 + 𝒪 (log 2 |𝑋|))
, where 𝑇 𝒜 is the time complexity of 𝒜 and 𝑇 𝑓 is the time complexity of a quantum algorithm for 𝑓 . Measuring the output of Amplify(𝒜, 𝑓 ) yields a "good" output of 𝒜 with probability max(1-𝑎, 𝑎). If 𝑎 is known exactly, then the probability of success can be brought to 1.

We will neglect the term 𝒪 (log 2 |𝑋|) since our complexity is expressed in quantum circuits for the attacked cipher, usually much more expensive. The memory consumed by the procedure itself is also usually negligible with respect to the memory of 𝒜 and 𝑓 .

To the quantum procedure Amplify(𝒜, 𝑓 ), there corresponds a classical exhaustive search procedure with about ( ⌊𝜋/(4𝜃 𝑎 )⌋ ) 2 iterations, which consists in a Repeat loop that calls 𝒜 and tests its output until it satisfies the constraint 𝑓 . Since 𝒜 in Theorem 1 can be any quantum algorithm, especially another quantum search, there is a recursive correspondence between classical procedures made of such Repeat loops and quantum procedures made of nested quantum searches [START_REF] Bonnetain | Quantum security analysis of AES[END_REF]. It follows that many quantum attacks, including the ones of this paper, can be first described classically.

More precisely, we will write down our algorithms using a Repeat block which specifies a number of iterations. Inside, we run a randomized algorithm 𝒜 followed by a test 𝑓 (If block) that checks if the current state is "good" or "bad". It is then expected that, if a good state exists, it is found after the specified number of iterations. Using Theorem 1, we make this algorithm correspond to Amplify(𝒜, 𝑓 ). If a solution exists, then Amplify(𝒜, 𝑓 ) produces it (or a superposition of possible solutions).

Searching for Collisions. We will also need to solve the following problem: given access to a random function 𝑓 : {0, 1} 𝑛 → {0, 1} 𝑚 , where 𝑛 ≥ 𝑚 2 , find a pair (𝑥, 𝑦) such that 𝑓 (𝑥) = 𝑓 (𝑦). This can be done classically by sorting 𝒪 ( 2 𝑚/2 ) queries to 𝑓 . In the quantum setting, we can either use quantum search among the pairs (𝑥, 𝑦), for a time 𝒪 ( 2 𝑚/2 ) and a negligible memory, or quantum collision search. In that case we use Ambainis' algorithm [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF], which works even in the worst case 𝑛 = 𝑚 2 (where a single collision exists on expectation). It requires the qRAM model. The precise analysis made in [START_REF] Childs | Quantum algorithms for subset finding[END_REF] gives a number of ( 𝜋

2

) 2 2 𝑚/3 queries in our case for an overwhelming success. These queries are the dominant term. Note that the lower bound on quantum collision search for random functions [START_REF] Aaronson | Quantum lower bounds for the collision and the element distinctness problems[END_REF][START_REF] Zhandry | A note on the quantum collision and set equality problems[END_REF] prevents the existence of a more efficient algorithm

On Quantum Scenarios

In quantum symmetric cryptanalysis, there exist two scenarios that depend on the capabilities of the attacker. • the Q1 setting allows an attacker to perform quantum computations, but he can only use classical queries to black-box primitives (in this paper, an encryption oracle in the secret-key model). • the Q2 setting allows the attacker to query the black-box as a quantum oracle instead of a classical oracle. Although the latter is much more powerful, it remains nontrivial. Besides, as shown in [START_REF] Bonnetain | Quantum security analysis of AES[END_REF], when attacks requires low data, it is sometimes possible to replace Q2 queries by Q1. Thus, when following classical design patterns to perform quantum key-recoveries, like in [START_REF] Bonnetain | Quantum security analysis of AES[END_REF], it seems more suitable to consider the Q2 model by default and then see if they can be avoided afterwards. Note that it is not unusual for quantum attacks to require superposition queries, as it is the case of many attacks in [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF].

Quantum Boomerang Attacks

In this section, we adapt the attacks presented in Section 2 to the quantum setting.

Quantum Boomerang Distinguisher

Similarly to the differential attacks from [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF], the boomerang distinguisher of Algorithm 1 can be accelerated in the Q2 setting (Algorithm 3). The Repeat loop becomes a quantum search with 𝜋 4 (𝑝𝑞) -1 iterations looking for an element 𝑃 1 such that 𝑃 1 , 𝑃 1 ⊕ 𝛼 forms a boomerang pair. If 𝐸 satisfies the expected property, such a 𝑃 1 will be found, otherwise measuring the result will give us an Algorithm 3 Quantum Boomerang Distinguisher Input: superposition oracle access to 𝐸 = 𝐸2 ∘ 𝐸1, or a random permutation Output: "𝐸" or "Random" 1: Repeat 𝜋 4 (𝑝𝑞) -1 times 2:

Select 𝑃1 at random 3:

If 𝐸 -1 (𝐸(𝑃1) ⊕ 𝛿) = 𝐸 -1 (𝐸(𝑃1 ⊕ 𝛼) ⊕ 𝛿) ⊕ 𝛼 then 4:
the state (𝑃1) is "good" Else the state (𝑃1) is "bad" 5: EndRepeat 6: Measure and check if a solution was found 7: If it was found return "E" Else Return "Random" invalid pair. We make in total 𝜋 4 (𝑝𝑞) -1 × 8 queries to 𝐸 and 𝐸 -1 (each query is made twice for reversibility), which are in superposition since the quantum search space is on the value 𝑃 1 .

Quantum Boomerang Last-rounds Attack

Recall that the last-rounds attack of Section 2.1 is in two phases: first, we use the boomerang property to sieve the 𝑘 out bits that intervene in the last rounds 𝑅. Second, we perform an exhaustive search on the 𝑘 -𝑘 out remaining key bits.

For now, let us put aside the small constant factors. We count all quantum times in evaluations of 𝐸 or 𝐸 -1 and consider a Q2 query to 𝐸 or 𝐸 -1 to cost the same. The generic key-recovery is Grover's exhaustive search, with a time 2 𝑘/2 and a negligible number of Q1 queries. Our first idea is to go below that using the sieve on the 𝑘 out bits of key that the Boomerang property gives. If we can produce the superposition of valid 𝐾 out with a time complexity below 2 (𝑘-𝑘out)/2 , and if there are strictly less than 2 𝑘out elements in this superposition, then we can do better than Grover search: we Amplify an algorithm that first samples a 𝐾 out , then tries to complete the key in time 2 (𝑘-𝑘out)/2 .

In order to produce a possible value of 𝐾 out , we look for a pair 𝐶 1 , 𝐶 2 such that:

• 𝐶 1 ⊕ 𝐶 2 ∈ 𝐷 fin and 𝐶 ′ 1 ⊕ 𝐶 ′ 2 ∈ 𝐷 fin , where 𝐶 ′ 𝑖 = 𝐸(𝐸 -1 (𝐶 𝑖 ) ⊕ 𝛼);
• there exists a subkey 𝐾 out such that (𝐶 1 , 𝐶 2 ) and (𝐶 ′ 1 , 𝐶 ′ 2 ) decrypt to the difference 𝛿 through 𝑅 -1 under 𝐾 out .

Finding such a valid pair 𝐶 1 , 𝐶 2 is a collision search problem, solved with Ambainis' algorithm 4 . Let us assume that 𝐷 fin ≥ 2 𝑛/3 , which corresponds to the case where a single structure is enough. A structure contains |𝐷 fin | 2 pairs, and the constraint

𝐶 ′ 1 ⊕ 𝐶 ′ 2 ∈ 𝐷 fin selects a proportion |𝐷 fin | 2 𝑛
of them. Thus there is at least one solution.

We now check the number of iterations in the loops of Algorithm 4.

Step 1: the number of iterations to perform depends on the probability that a subkey guess 𝐾 out , obtained with the procedure in the loop, is the good one.

In the classical analysis of the procedure, we obtained a list of ) times 2:

Sample a subkey guess 𝐾out using: 3:

Repeat (

1 2 𝑘 out 𝑝 2 out
) times

4:

Use Ambainis' algorithm to find a valid pair (𝐶1, 𝐶2, 𝐶 ′ 1 , 𝐶 ′ 2 ) 5:

Repeat 2 𝑘 out times 6:

Sample a guess of 𝐾out 7:

If 𝑅 -1 (𝐶1) ⊕ 𝑅 -1 (𝐶2) = 𝛿 = 𝑅 -1 (𝐶 ′ 1 ) ⊕ 𝑅 -1 (𝐶 ′ 2 ) then 𝐾out is "good" 8: EndRepeat 9:
If we obtained a valid 𝐾out then (𝐶1, 𝐶2, 𝐶 ′ 1 , 𝐶 ′ 2 ) is "good" 10:

EndRepeat 11:

Given this subkey guess 𝐾out: 12:

Repeat 2 (𝑘-𝑘 out ) times 13:

Sample a choice of the 𝑘 -𝑘out other key bits, check if the full 𝐾 matches 14:

EndRepeat 15:

If we obtained a valid full key 𝐾 then 𝐾out is "good" 16: EndRepeat 17: Measure 𝐾out, recompute 𝐾 and return it tuples. We know that the good one is in one of these tuples. The computation inside the Repeat loop is the same, so the probability of success (the full key is found) is

2 𝑛 |𝐷 fin | (𝑝𝑞) 2
2 𝑘 out 𝑝out and the number of iterations follows.

Step 3: here, we are iterating on tuples (𝐶 1 , 𝐶 2 , 𝐶 ′ 1 , 𝐶 ′ 2 ) until we find a key candidate. The probability that a tuple yields a key candidate is 2 𝑘out 𝑝 2 out , thus there are max(1,

1 √ 2 𝑘 out 𝑝 2 out
) iterations. We will assume 2 𝑘out 𝑝 2 out ≤ 1. Note that the key candidate (actually the superposition of all possible candidates for the given pair) is obtained by exhaustive search, but a more involved procedure could likely be applied in order to reduce the time complexity.

Step 12: having obtained a candidate for 𝐾 out , it remains to try it: for this, we perform a simple Grover search over the remaining 𝑘 -𝑘 out bits.

By changing the loops into nested quantum searches, the quantum time complexity of Algorithm 4 is:

√ |𝐷 fin | 2 𝑛 2 𝑘out 𝑝 out (𝑝𝑞) 2 ( 1 √ 2 𝑘out 𝑝 2 out ( ( 2 𝑛 |𝐷 fin | ) 1/3 + 2 𝑘out/2 ) + 2 (𝑘-𝑘out)/2 ) = √ |𝐷 fin | 2 𝑛 2 𝑘out 𝑝 out (𝑝𝑞) 2 ⏟ ⏞ <2 𝑘 out /2 by the classical analysis ⎛ ⎝ 2 𝑛/3 2 𝑘out/2 𝑝 out |𝐷 fin | 1/3 + 1 𝑝 out + 2 (𝑘-𝑘out)/2 ⏟ ⏞ Exhaustive search ⎞ ⎠ .
The algorithm requires Q2 queries to 𝐸 and 𝐸 -1 , and uses ( 2 𝑛 /|𝐷 fin | ) 1/3 qRAM due to the use of Ambainis' algorithm (or BHT) to find valid pairs. However, if we can replace the factor

( 2 𝑛 /|𝐷 fin | ) 1/3 by ( 2 𝑛 /|𝐷 fin | ) 1/2
, then we can use a Grover search instead of Ambainis' algorithm, and the algorithm will now require a small number of qubits only.

Making the Attack Q1. Recall that the attack requires only a structure of 1 √ 𝑝out(𝑝𝑞) ciphertexts. For each of these, we will have to compute 𝑓 (𝐶) = 𝐸(𝐸 -1 (𝐶)⊕ 𝛼). Thus, all the queries made to 𝐸 and 𝐸 -1 asked during the attack fall actually in a set of size

1 √ 𝑝out(𝑝𝑞) . If we have 1 √ 𝑝out(𝑝𝑞) < 2 𝑘/2
, then we can make all the queries classically beforehand and store the results in a quantum RAM of size 1 √ 𝑝out(𝑝𝑞) . Inside Algorithm 4, we replace the on-the-fly computation of 𝑓 by a memory lookup.

Quantum Mixing Boomerang Distinguisher

We now study the Mixing Boomerang attacks presented in Section 2.2. Since the distinguisher is a single loop similar to Algorithm 1, it can be replaced by a quantum search of a valid pair (𝑃 1 , 𝑃 1 ⊕ 𝛼) with about 1/ √ 𝑝 ↓ 𝑝 ↑ iterations, with Q2 queries and negligible memory.

Quantum First-round Mixing Attack. The attack will work similarly as the quantum last-round attack of Algorithm 4. The main difference is that we do not need a collision search algorithm to filter out the valid pairs (𝑃 1 , 𝑃 2 ) such that

𝑃 3 ⊕ 𝑃 4 ∈ 𝐷 start .
We analyze the time complexity of Algorithm 5, when translated into nested Amplitude Amplifications.

Step 1: here, the number of iterations depends on the number of possible keys 𝐾 in obtained in the sieving step. From the classical analysis, we know that there will be |𝐷start| 2 𝑛

1

𝑝 ↑ 𝑝 ↓ 2 𝑘in 𝑝 in < 2 𝑘in tuples (𝑃 1 , 𝑃 2 , 𝑃 3 , 𝑃 4 , 𝐾 in ) obtained, among which the good subkey 𝐾 in appears (at least once). Thus there are at most

( |𝐷start| 2 𝑛 1 𝑝 ↑ 𝑝 ↓ 2 𝑘in 𝑝 in ) 1/2 iterations.
Step 3: from a valid quadruple (𝑃 1 , 𝑃 2 , 𝑃 3 , 𝑃 4 ), i.e., one that satisfies 𝑃 1 ⊕ 𝑃 2 ∈ 𝐷 start and 𝑃 3 ⊕ 𝑃 4 ∈ 𝐷 start , the probability that we obtain a subkey guess is 2 𝑘in 𝑝 2 in . This gives the number of iterations.

Step 5: the probability for a given pair to be valid is simply |𝐷start| 2 𝑛 .

Step 16: similarly to Algorithm 4, we complete the quantum search for the key.

The total quantum time complexity of Algorithm 5 is given by:

√ |𝐷 start | 2 𝑛 2 𝑘in 𝑝 in 𝑝 ↑ 𝑝 ↓ ( 1 √ 2 𝑘in 𝑝 2 in (√ 2 𝑛 |𝐷 start | + 2 𝑘in/2 ) + 2 (𝑘-𝑘in)/2 ) = √ |𝐷 start | 2 𝑛 2 𝑘in 𝑝 in 𝑝 ↑ 𝑝 ↓ ( 2 𝑛/2 2 𝑘in/2 𝑝 in |𝐷 start | 1/2 + 1 𝑝 in + 2 (𝑘-𝑘in)/2 ) . (6)
Algorithm 5 Quantum first-rounds key-recovery

Input: superposition oracle access to 𝐸 and 𝐸 -1 Output: the full key 1:

Repeat |𝐷 start | 2 𝑛 1 𝑝 ↑ 𝑝 ↓ 2 𝑘 in 𝑝in times 2:
Sample a subkey guess 𝐾in using: 3:

Repeat 1/(2 𝑘 in 𝑝 2 in ) times 4:
Sample a valid (𝑃1, 𝑃2) using: 5:

Repeat

2 𝑛 |𝐷 start | times 6:
Sample a pair 𝑃1, 𝑃2 = 𝑃1 ⊕ 𝛼, compute 𝑃3, 𝑃4 as in the distinguisher 7: The baseline algorithm does not use quantum RAM and requires only a small number of qubits, but it also relies on Q2 queries. Depending on the amount of data required, it may be possible to make it Q1: for this, we query all the 1 𝑝in𝑝 ↑ 𝑝 ↓ pairs required by the classical attack, and store the tuples 𝑃 1 , 𝑃 2 , 𝑃 3 , 𝑃 4 in a quantum RAM. This can only work if

If 𝑃3 ⊕ 𝑃4 = 𝛼, then (𝑃1,
1 𝑝in𝑝 ↑ 𝑝 ↓ < 2 𝑘/2 .

Application to SAFER

SAFER is a family of block ciphers (Substitution-Permutation Networks) that dates back to the SAFER K-64 proposal of [START_REF] Massey | SAFER K-64: A byte-oriented block-ciphering algorithm[END_REF]. SAFER-K-64 was a block cipher of 64 bits. A new version SAFER+, with 128-bit blocks, was a candidate of the AES competition organized by the NIST [START_REF] Massey | Nomination of SAFER+ as candidate algorithm for the advanced encryption standard[END_REF]. Finally, another variant, SAFER++, was submitted to the NESSIE project [START_REF] Massey | Nomination of SAFER++ as candidate algorithm for the new european schemes for signatures, integrity, and encryption[END_REF]. Here, we focus on SAFER++ and more precisely, on the boomerang attack presented in [START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF]. It reaches 5.5 rounds out of 7 total rounds.

Description of the Cipher

We use ⊞ and ⊟ to denote addition and subtraction modulo 2 8 . We consider the version of SAFER++ with a 128-bit key (and 128-bit blocks), which has 7 rounds. The round function (see Figure 4 in Appendix A, or Fig. 1 in [START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF]) consists of key additions, a nonlinear layer and a linear layer. The state and the round keys are represented as 16 bytes numbered from 0 to 15, partitioned into 𝑆 1 = {0, 3, 4, 7, 8, 11, 12, 15} and 𝑆 2 = {1, 2, 5, 6, 9, 10, 13, 14}. A single round performs the following steps:

Upper key addition: bytes in 𝑆 1 of the 16-byte round key are XORed to the corresponding bytes of the block and the others are added modulo 2 8 . Nonlinear layer: it uses two functions 𝑋 and 𝐿: 𝑋(𝑎) = (45 𝑎 mod 257) mod 256, 𝐿(𝑎) = log 45 (𝑎) mod 257 and 𝐿(0) = 128, (7) where 𝐿 is the inverse of 𝑋. Bytes in 𝑆 1 go through 𝑋 and bytes in 𝑆 2 go through 𝐿. Lower key addition: another 16-byte round key is added to the state, using modular addition in 𝑆 1 and XOR in 𝑆 2 . Linear layer: it repeats twice the following: a permutation of the bytes, followed by a Pseudo Hadamard Transform to groups of 4 bytes. This linear layer contains a total of 48 modular additions of individual bytes and can be described by the matrix given in [START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF].

5-Round Classical Boomerang Attack

We present the attack from [START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF]. It relies on a boomerang distinguisher on 4.5 rounds of SAFER++. If 𝐴 denotes the linear layer and 𝑆 the nonlinear layer (𝑋 and 𝐿), the distinguisher works against a sequence

𝐴 0 𝑆 1 𝐴 1 -𝑆 2 -𝐴 2 𝑆 3 𝐴 3 𝑆 4 𝐴 4 .
It would work against 4 rounds if any S-Boxes were used, but it reaches an additional 0.5 round thanks to the following property of the inverse-based S-Boxes in SAFER++:

∀𝑎, 𝑋(𝑎) ⊞ 𝑋(𝑎 ⊞ 128) = 1 mod 256 . ( 8
)
The top part of the boomerang starts with pairs of plaintexts having difference 𝛼 = (0, 𝑥, 0, 0, 𝑥, 𝑥, 0, 0, 0, 0, 0, -4𝑥, 0, 0, 𝑥, -𝑥). This difference is such that it maps to a single active byte after 𝐴 0 , and up to 16 active bytes after 𝐴 1 ∘ 𝑆 1 .

The difference added to ciphertexts is: 𝛿 = (0, 0, 128, 0, 128, 128, 0, 0, 0, 0, 0, 0, 128, 0, 0, 0) .

After 𝑆 -1 4 ∘𝐴 -1 4 , it maps to a difference (0, 0, 0, 0, 0, 𝑥, -𝑥, 0, . . .) with probability 2 -7 (not 2 -8 because the difference 128 maps to odd differences through 𝑋).

Then after 𝐴 -1 3 , bytes 3, 9, 11 and 14 are active. In order to traverse the middle S-Box, the authors observe that if the bytedifferences coming both from the top and the bottom part of the boomerang are 128, then the boomerang traverses this S-Box layer for free. Indeed, if we encrypt 𝑃 1 , 𝑃 2 = 𝑃 ⊞ 128 through 𝑋, we obtain 𝑋(𝑃 ), 1 ⊟ 𝑋(𝑃 ), i.e., two values that sum to 1. If the difference coming from the bottom part is 128, then the second pair of ciphertexts 𝐶 3 , 𝐶 4 = 𝐶 1 ⊞ 128, 𝐶 2 ⊞ 128 still sums to 1. Thus, by going through 𝑋 -1 , they get mapped to a difference 128 with probability 1. Boomerang Attack. The full differential path of the classical 5-round boomerang attack of [START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF] is reproduced in Figure 3. We use

𝑆 0 𝐴 0 𝑆 1 𝐴 1 -𝑆 2 -𝐴 2 𝑆 3 𝐴 3 𝑆 4 𝐴 4
to denote the whole construction. The total probability for the boomerang to occur is: (2 -7-30.4 ) 2 2 -40-8 = 2 -122.8 .

Top boomerang: At the top, the difference is active in 6 bytes in positions 1, 4, 5, 11, 14, 15. This difference propagates to a single active byte after one round (𝐴 0 ∘ 𝑆 0 ) with probability 2 -40 , as there are 5 byte-conditions to meet. This difference is then mapped to a single active byte of difference 128 after the next nonlinear layer 𝑆 We recall the attack procedure from [START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF] in Algorithm 6. It requires 2 78 encryptions.

From a pool of 2 48 plaintexts, we get approximately 2 95 pairs, which have to satisfy an 80-bit condition, so we get 2 15 pairs in Step 4. The probability that the structure contains a boomerang is approximately 2 -27.8 , so by using Algorithm 6 Classical attack on 5-round SAFER++ (adapted from [START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF], Sec.

6.3).

Input: access to 𝐸 and 𝐸 -1 1: Prepare 2 29 structures of 2 48 plaintexts 𝑃𝑖 that take all values in bytes 1, 4, 5, 11, 14 and 15 and are constant in the others 2: For each structure, obtain the ciphertexts 𝐶𝑖 = 𝐸(𝑃𝑖) 3: For each structure, add the difference 𝛿 (one bit in bytes 2, 4, 5, 12) to the 𝐶𝑖 and decrypt: obtain 𝑄𝑖 = 𝐸 -1 (𝐶𝑖 ⊕ 𝛿) 4: For each structure, the 𝑄𝑖 on the values of the bytes that are constant in the 𝑃𝑖 and keep the pairs 𝑄𝑖, 𝑄𝑗 that have zero difference on these ten bytes ◁ We search for a difference after the S-Box of the form (0, 𝑥, 0, 0, 𝑥, 𝑥, 0, 0, 0, 0, 0, -4𝑥, 0, 0, 𝑥, -𝑥) 5: For each possible quartet (𝑃𝑗, 𝑃 𝑘 , 𝑄𝑗, 𝑄 𝑘 ), search for the upper key bytes 𝐾 4 0 , 𝐾 11 0 , 𝐾 14 0 , 𝐾 15 0 such that after the first S-Box layer, we have a difference (𝑥, -4𝑥, 𝑥, -𝑥) (𝑥 odd) between 𝑃𝑗 and 𝑃 𝑘 and between 𝑄𝑗 and 𝑄 𝑘 . The quartets are kept with their partial key and the observed 𝑥. 6: For each quartet, search for the key bytes 𝐾 1 0 and 𝐾 2 0 ′ (upper and lower key addition in byte 0) such that the difference after the first S-Box is the right one. Repeat this for 𝐾 5 0 and 𝐾 6 0 ′ . 7: Find a suggestion of the 8 key bytes that appears twice, and run exhaustive search on the remaining bytes.

2 29 structures, we can expect two boomerang quartets to occur among the 2 44 filtered quartets. Next, we guess 4 bytes of the first upper round key (𝐾 4 0 , 𝐾 11 0 , 𝐾 14 0 , 𝐾 15 0 ) to remove wrong quartets. For each guess, we have a 25-bit condition on both pairs. Thus, 50 bits of restriction on the quartets. At this point, we obtain 2 44 × 2 32 × 2 -50 = 2 26 valid quartets and key guesses. Note that this already yields a valid key-recovery attack, as we have been able to reduce the number of possible 𝐾 4 0 , 𝐾 11 0 , 𝐾 14 0 , 𝐾 15 0 from 2 32 to 2 26 . For the next 4 key bytes guessed at Step 6, there is approximately one choice for each valid quartet currently kept. Thus, at this point, we have 2 26 guesses of 8 bytes of the key, among which we expect the good one to occur. If we ran immediately an exhaustive search for the remaining 8 bytes, we would obtain a complexity 2 26 × 2 8×8 = 2 90 .

However, there are two valid boomerang pairs: one of the key guesses occurs twice. As the key guesses are 8 bytes and there are 2 26 of them, we can expect that random collisions are not likely to occur, and the only key guess occurring twice is the good one. Thus exhaustive search is ran only once. The bottleneck of the complexity lies in encrypting and decrypting the 2 29 structures, for a total of 2 78 time and queries.

Extension. Another half round can be added at the end, by making 30 bits of additional key guess and running Algorithm 6 2 30 times.

Quantum Boomerang Attack

Our quantum attack on 5-round SAFER++ uses the framework of Algorithm 4, adapted to the setting of the classical attack (Algorithm 6). We will first explain its time complexity, and show how it goes below Grover's exhaustive search in time 2 64 . Recall that the time complexity is counted in number of evaluations of SAFER++.

Algorithm 7 Attack on 5-round SAFER++.

Input: superposition access to 𝐸 and 𝐸 -1 Output: the full key 1: Repeat 2 26 times 2:

Sample a guess for 𝐾 4 0 , 𝐾 11 0 , 𝐾 14 0 , 𝐾 15 0 , 𝐾 1 0 , 𝐾 2 0 ′ , 𝐾 5 0 , 𝐾 6 0 ′ using: 3:

Repeat 2 18 times ◁ a valid quartet yields a key guess with prob. 2 -18 4:

Find a valid quartet ◁ Either using Ambainis' algorithm, or quantum search ◁ We need the same number of quartets as classically: 2 78 plaintexts in total 5:

Repeat 2 32 times ◁ at most one solution 6:

Pick a key guess 𝐾 4 0 , 𝐾 11 0 , 𝐾 14 0 , 𝐾 15 0 7: Check if this key guess yields the good difference (𝑥, -4𝑥, 𝑥, -𝑥) for both pairs of the quartet 8:

EndRepeat 9:

If a solution was found, return it (and the quartet) 10: EndRepeat 11:

Search exhaustively for 𝐾 1 0 , 𝐾 2 0 ′ and 𝐾 6 0 ′ (keep at most one value) ◁ there is on average one value; sometimes there can be more; but we only need this to work for the actual boomerang quartet 12:

Given the current guess of 8 bytes of key, complete the key by Grover search 13: EndRepeat 14: Measure and return the full key Assuming that we use Grover search at Step 4 (instead of collision search), the attack would run in approximately:

√ 2 26 ⎛ ⎜ ⎝ √ 2 18 ⎛ ⎜ ⎝ √ 2 80 ⏟ ⏞ Step 4 + √ 2 32 + 2 • 2 16 ⏟ ⏞ Step 11 ⎞ ⎟ ⎠ + √ 2 64 ⏟ ⏞ Step 12 ⎞ ⎟ ⎠ (9)
calls to SAFER++ and its inverse. The dominating term comes from the search for quartets satisfying the partial collision condition on 10 bytes. Indeed, the classical attack can sample these quartets very easily using structures. If we use classical search in Algorithm 7, we can obtain an attack running with polynomial memory in little less time than 2 128 . However, in the quantum setting, additional factors from Amplitude Amplification will prevent that, so we must resort to quantum collision search in Step 4.

Since a structure is of size 2 48 and we need 80 bits of collision, we can use Ambainis' algorithm to produce a superposition of colliding pairs (thus valid quartets) in about (𝜋/2) 2 2 80/3 ≃ 2 28.3 calls to 𝐸 and 𝐸 -1 in superposition.

Assuming that the numbers of iterations are exact, but putting the additional factors of quantum search, we obtain:

2 ⌊ 𝜋 4 2 13 ⌋ ( 2 ⌊ 𝜋 4 2 9 ⌋ ( 2 28.3 × 4 ⏟ ⏞ Step 4 + 2 ⌊ 𝜋 4 2 16 ⌋ ⏟ ⏞ Step 11 +4 • 2 16 ) + ⌊ 𝜋 4 2 32 ⌋ × 4 ⏟ ⏞ Step 12 ) ≃ 2
)
where the time is counted in computations of SAFER++ and its inverse, and we assume that a black-box (quantum) query costs the same. In the last step (quantum exhaustive search over 8 key bytes), we match against two given plaintextciphertext pairs. In Step 12, we know that there is exactly one solution (or none) in a search space of size 2 64 . Thus, we can run exact Amplitude Amplification with ⌊ 𝜋 4 2 32 ⌋ iterations and succeed with probability 1 (either we find the solution, or prove that there is none). For the other loops, we can ensure a high probability of success by making a few assumptions on the classical attack: • the number of valid quartets for each structure is close to the average (this ensures that Ambainis' algorithm works as intended; if necessary we make multiple copies of it); • the actual boomerang pair yields only a single value at Step 11, and our algorithm does not lose it; • the probability, for a given guess of 8 key bytes sampled at Step 2, to be the good one, is close to 2 -26 .

The attack requires 2 27 registers of 256 qubits to store the values of 𝑃 𝑖 and 𝐸 -1 (𝐸(𝑃 𝑖 ) ⊕ 𝛿) for each 𝑃 𝑖 , and 2 53.6 superposition queries to 𝐸 and 𝐸 -1 .

Application to Related-key AES

In Appendix B , we detail the quantum version of a classical related-key attack on AES-256 from [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF]. The classical attack recovers the key in time 2 99.5 using a tuple of 4 related keys. With the same configuration, our quantum attack runs in time 2 96.4 (counted in evaluations of the cipher, forwards and backwards), which is rather a minor improvement compared to what we could do with SAFER++.

The reason for this is that the structure of the attack is different from the framework of Section 3. Here, we are looking among the quartets (and all the key guesses that they generate) for a key guess that appears at least three times. With high probability, there is only one such guess, which corresponds to the three valid boomerang quartets that should exist in the search space.

Classically, it takes time 𝑁 to examine 𝑁 objects and find the one that appears three times. This 3-distinctness problem can be solved quantumly with a generalization of Ambainis' element distinctness algorithm [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF], but it will take time 𝒪 ( 𝑁 3/4 ) , which is far from a square-root speedup. This is the core reason why this attack does not perform well.

In the quantum setting, it is a much better strategy to discriminate the right key guess by checking exhaustively the remaining bits of key (e.g., Step 12 in Algorithm 4). In the attack on AES-256, using the path of [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF], this is not possible because there are too many bits remaining. There probably exists a more suitable path, which would yield a more efficient quantum procedure. We leave this as an open question.

Conclusion

In this paper we proposed an efficient quantum boomerang attack, as well as a variant for mixing boomerang attacks. We proposed several improvements for different cases, as reducing the quantum RAM need or making Q2 attacks work in Q1 under certain circumstances. In some cases, our attacks reach a quadratic speed up with respect to classical attacks. This shows that boomerang attacks are also performant cryptanalysis tools for the post-quantum world, that will be needed for correctly determining the best security margins.

Note that the attack uses a tuple of classically related keys (the same as in the classical attack). In this situation, there is no trivial quantum attack such as the one of [START_REF] Rötteler | A note on quantum related-key attacks[END_REF] (which needs a quantum superposition of related keys).

B.1 Description of AES

The AES [START_REF]Advanced encryption standard[END_REF], designed by Daemen and Rijmen [START_REF] Daemen | AES proposal: Rijndael[END_REF], was the winner of the AES competition organized by the NIST. It is arguably one of the most analyzed ciphers to date. Similarly to SAFER++, it has blocks of 128 bits, divided in 16 bytes numbered from 0 to 1. The state of AES is represented as a square and we will follow the byte numbering of [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF]. Thus, in a plaintext 𝑃 or a subkey 𝐾, the byte 𝑃 𝑖,𝑗 or 𝐾 𝑖,𝑗 is located at row 𝑖 and column 𝑗. The round function of AES applies 4 operations: • AddRoundKey (ARK), which adds the current round key (as described by the AES key-schedule) and a round constant; • SubBytes (SB), which applies the AES S-Box to each byte; • ShiftRows (SR), which shifts the bytes in row 𝑖 of the square by 𝑖 positions to the left; • MixColumns (MC), which applies the (aligned) AES MDS matrix to the columns of the state.

We consider here the related-key attack of [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF] on full-round AES-256 (14 rounds in total, numbered from 1 to 14). This key-recovery has a data and time complexity of 2 99.5 .

B.2 Classical Attack

There are 4 related keys 𝐾 𝐴 , 𝐾 𝐵 , 𝐾 𝐶 , 𝐾 𝐷 in the attack of [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF], where 𝐾 𝐵 , 𝐾 𝐶 , 𝐾 𝐷 are computed from 𝐾 𝐴 . These related keys are used in the four branches of the quartet. We refer to [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF] for the definition of their relations. The path of the boomerang is represented on Figure 6 and Figure 7 from Appendix C. The keyschedule of AES-256 has an internal state of 256 bits in which the full key is first loaded, then updated every two rounds (the first half is used for even rounds, the second half for odd rounds). We let 𝐾 0 , 𝐾 1 , . . . denote these successive 256-bit round keys, where 𝐾 0 = 𝐾 is the master key.

The main requirement for this attack are the differences 1f in the output of the active S-Boxes. With a difference 01 in the input, the output difference is 1f with probability 2 -6 . Thus, assuming that we can start from a pair that satisfies the path of Figure 6 at Round 1, it passes the top differential to the beginning of round 9 with probability 2 -6×5 = 2 -30 . Then we use the ladder switch technique, which means that we consider the S-Boxes on the bytes (0, 0), (0, 1), (0, 2), (0, 3) to belong to the top part of the boomerang and the other ones to belong to the bottom part of the boomerang, this way there is no differential to pay in either parts of the boomerang for this round. In the bottom part of the boomerang, there remains 3 S-Boxes to pass, with a probability 2 -18 . Thus the total probability is 2 -30×2-18×2 = 2 -96 .

We focus now on the key-recovery attack of [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF]. We start from 2 25.5 structures of plaintexts that take all possible values in the 9 bytes (0, 0), (1, 0), (2, 0), (3, 0), (1, 1), (1, 2), (1, 3), (2, 2), [START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF][START_REF] Biryukov | Cryptanalysis of SAFER++[END_REF] (that includes the first column, the second row and the first diagonal) and leave the other constant. For each structure:

). 5. Two filtering steps for these quartets remains. We check whether 𝑃 𝐴,𝑖,0 ⊕ 𝑃 𝐵,𝑖,0 = 𝑃 𝐶,𝑖,0 ⊕ 𝑃 𝐷,𝑖,0 (= 𝛥𝐾 0 𝑖,0 ), 𝑖 > 1 because 𝛥𝐾 0 𝑖,0 is equal for the key pairs (𝐾 𝐴 , 𝐾 𝐵 ) and (𝐾 𝐶 , 𝐾 𝐷 ). 6. Another filtering allows to reduce the number of quartets by a factor 2 6 . There were 2 72 plaintexts in each structure, for a total of 2 97.5 plaintexts. There are 2 144 pairs per structure and a 9-byte condition is required to pass the first round; thus, we can expect 2 144-8×9-96+25.5 ≃ 3 boomerang pairs among them. At the first filtering step, we filter on 7 byte-conditions, in the second, there are two byte-conditions, then a 6-bit condition. Thus there are 2 144-8×9-6+25.5 = 2 91.5 quartets at this point.

We can then begin to sieve some subkey bytes. It is shown in [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF] that by performing a few trials, one can reduce the number of quartets by a factor 2 19 and, for each of the remaining quartets, find 2 6 candidates for a total of 15 key bytes. Notably, 85 bits of 𝐾 𝐴 are found. This makes for a total of 2 78.5 choices for these key bytes. Since there are three boomerang quartets, one of these choices occurs three times (other collisions are unlikely).

B.3 Quantum Attack

The attack of [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF] runs in time 2 99.5 , makes the same number of queries to 𝐸 and 𝐸 -1 , and uses a memory of size 2 77.5 to recover the good guess for some of the key bytes. It falls already below the complexity of Grover search for a single secret-key AES-256. Generic Attack. In the related-key setting, and with an unbounded number of related keys, it is possible to reduce this to 2 256/3 = 2 85.3 queries and time using the same number of related keys (2 85.3 ). This is the quantum counterpart of the classical collision attack using 2 128 related keys, which would simply encrypt a small set of plaintexts 𝑃 𝑖 under all the keys 𝐾, 𝐾 ⊕ 1, . . . , 𝐾 ⊕ 2 128 and find another key 𝐾 ′ such that 𝐸 𝐾 ′ (𝑃 𝑖 ) collides with one of the 𝐸 𝐾⊕𝑗 (𝑃 𝑖 ). The quantum attack uses a smaller set of related keys and uses a Grover search in the second step; the complexities of both steps are balanced at roughly 2 85.3 . More precisely, the quantum search step needs two plaintexts (hence four encryptions per iteration). The first step performs 2 • 2 𝑡 queries and the second 𝜋 4 2 (256-𝑡)/2 iterations, for a total of 𝜋 4 2 (256-𝑡)/2+2 = 2 128-𝑡/2+2.65 encryptions. This is minimized for 𝑡 + 1 = 128 -𝑡/2 + 2.65, i.e., 𝑡 = 86.4 and the total is 2 87.4 encryptions.

Thus, we can choose to compare our attack complexity either with the generic bound of 2 87.4 , if we assume an unbounded number of classically related keys, or with a bound of 2 127 if we assume that only 4 related keys are available (in which case the best procedure is the same as above, but limited by the number of keys that we have). In the former case, the attack will not be valid. That is, the complexity will go above 2 87.4 . It will only be valid for the second definition.

Attack Procedure. We now detail the quantum version of the previous attack. We use the same differential path and the same key relations. Contrary to the attack against SAFER++, we will not combine the boomerang with a complete recovery of the key. Since only 85 bits of the master key are obtained, it may take actually too much time to continue a Grover search on the remaining key bits; we would then need a more involved procedure to get as many key bits as possible within the allowed time. Instead, we will define a function that produces deterministically a quartet and a 85-bit key guess. Roughly speaking, this function starts from a set of plaintext values (some substructure), performs a search of valid quartets on this space, sieves them to obtain a single (expected) quartet leading to 2 6 guesses of key bits, and chooses one of these guesses. It will output 2 78.5 key guesses of 85 bits; we expect one of these guesses to appear more often, due to the boomerang pairs. Thus we can use Ambainis' element distinctness algorithm [START_REF] Ambainis | Quantum walk algorithm for element distinctness[END_REF]. However, we must recognize the only guess that appears three times, not two, so we must use the 3-distinctness algorithm which runs in generic complexity 𝒪 ( 𝑁 3/4 ) for 𝑁 elements (also optimal). The constant in the 𝒪 is the same as in the 2-distinctness algorithm.

We compute the time complexity of Algorithm 8 as follows. It is dominated by the 2 3×78.5/4 ≃ 2 58.9 calls to the function 𝐹 that we defined. Calling 𝐹 requires two loops, one of which corresponds actually to a quantum collision search for quartets matching the 9-byte condition. Note that the computations required to find if there are key guesses, and to select one of them, are negligible with Algorithm 8 Related-key attack on AES-256 (as a classical combination of Repeat loops).

Input:

access in superposition to encryptions and decryptions under 𝐾𝐴, 𝐾𝐵, 𝐾𝐶 , 𝐾𝐷 1: function 𝐹 (𝑖, 𝑏) ◁ 𝑖 is a 72.5-bit value, 𝑏 is a 6-bit value 2:

Depending on 𝑖, choose a set of 2 The complexity that we obtain is slightly below the classical attack complexity, but not significantly. It is also above the quantum bound of 2 87.4 encryptions. We will use also the same number of superposition queries, and about 2 58.9 quantum random-access memory. Our main issue with this method is that the quantum time complexity of 3-distinctness is different than that of 2-distinctness, which is not the case classically. If the good key was the only one appearing twice, instead of three times, we could replace the term 2 58.9 by 2 52.3 and go more significantly below the classical complexity.

Furthermore, this method (using an element distinctness routine on top of the search of quartets) seems intrinsically less adapted than the direct combination with exhaustive search that we used against SAFER++. Thus, it seems necessary to modify the path of the attack in order to find more key bytes with a valid quartet, and to finish faster the recovery of the key. . Bottom part of the boomerang (see [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF], Fig. 7). We use purple for the difference 01 and blue for the difference 1𝑓 .

Fig. 2 .

 2 Fig. 2. First-round mixing boomerang attack.

|𝐷start| 2 𝑛 1 𝑝in𝑝 ↓ 𝑝 ↑ pairs at a cost of 4 𝑝in𝑝

 14 ↓ 𝑝 ↑ computations and data.

Fig. 3 .

 3 Fig. 3. Classical boomerang attack on SAFER++ (Fig. 4 in [3])

Fig. 5 .

 5 Fig. 5. AES byte numbering

CFig. 6 .Fig. 7

 67 Fig.6. Top part of the boomerang (see[START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF], Fig.7). We use purple for the difference 01 and blue for the difference 1𝑓 . The state after the SubBytes layer of round 𝑖 is denoted 𝐴𝑖.

  |𝐷 fin |, in which case a single structure is needed. Otherwise when 1 √ 𝑝out𝑝𝑞 ≥ |𝐷 fin |, we will actually generate multiple structures with |𝐷 fin | ciphertexts each, so that they form a total of

	1 𝑝out(𝑝𝑞) 2 pairs.

1

√ 𝑝out𝑝𝑞 <

fin at Step 4 of Algorithm 2. There are enough quartets (𝐶 𝑖 , 𝐶 𝑗 , 𝐶 ′ 𝑖 , 𝐶 ′ 𝑗 ) in 𝐿 pairs to ensure that, for the good key guess of 𝐾 out , one of them is an actual boomerang quartet. Let 𝐶 out be the time complexity to obtain all valid keys 𝐾 out for a given pair (𝐶 𝑖 , 𝐶 𝑗 ) (Step

  Boomerang last-round attackInput: oracle access to 𝐸 = 𝑅 ∘ 𝐸2 ∘ 𝐸1 Output: guess of partial key 𝐾out involved in the round(s) 𝑅 1: Generate a structure 𝑆 of 1 √ 𝑝 out 𝑝𝑞 ciphertexts of the form: 𝑆 ⊆ {𝑋 ⊕ 𝛥, 𝛥 ∈ 𝐷 fin } 2: 𝐿pairs ← ∅ 3: Compute all the 𝐶 ′ = 𝐸(𝐸 -1 (𝐶) ⊕ 𝛼) for all 𝐶 ∈ 𝑆, sort 𝑆 by values of 𝐶 ′ 4: ForEach pair 𝐶 ′ 𝑘 out 𝑝out 14: return all guesses of 𝐾out in the triplet list Now we will partially decrypt these ciphertexts and obtain pairs with difference 𝛿. Among the 1 𝑝out(𝑝𝑞) 2 pairs (𝐶 𝑖 , 𝐶 𝑗 ) in 𝑆, we expect 1 (𝑝𝑞) 2 of them to be such that 𝑅 -1 (𝐶 𝑖 ) ⊕ 𝑅 -1 (𝐶 𝑗 ) = 𝛿, where 𝑅 involves the actual partial key 𝐾 out used in the last rounds. Then we define 𝐶 ′ 9 in Algorithm 2 is the naive way to do so, but there is usually a better algorithm). Since we expect on average 2 𝑘out 𝑝 2 out such keys, we have 𝐶 out ≥ 2 𝑘out 𝑝 2 out . After having obtained the list 𝐿 pairs of size |𝐷 fin |

					𝑖 , 𝐶 ′ 𝑗 such that 𝐶 ′ 𝑖 ⊕ 𝐶 ′ 𝑗 ∈ 𝐷 fin
	5:	𝐿pairs ← 𝐿pairs ∪ {(𝐶𝑖, 𝐶𝑗, 𝐶 ′ 𝑖 , 𝐶 ′ 𝑗 )}
	6: EndFor		1 𝑝 out (𝑝𝑞) 2 ◁ Note that 𝑆 being sorted, these pairs are computed efficiently ◁ Here |𝐿pairs| = |𝐷 fin | 2 𝑛
	7: 𝐿 triplets ← ∅
	8: ForEach pair 𝐶𝑖, 𝐶𝑗, 𝐶 ′ 𝑖 , 𝐶 ′ 𝑗 ∈ 𝐿pairs
	9:	ForEach possible value 𝐾out of the 𝑘out bits of key
							◁ 2 𝑘 out trials, 2 𝑘 out 𝑝 2 out solutions
	10:		If both (𝐶𝑖, 𝐶𝑗) and (𝐶 ′ 𝑖 , 𝐶 ′ 𝑗 ) lead to a difference 𝛿 through 𝑅 -1 under 𝐾out
	11:		𝐿 triplets ← 𝐿 triplets ∪ {(𝐶𝑖, 𝐶𝑗, 𝐾out)}
	12:	EndFor
	13: EndFor 𝐶 ′ 𝑗 = 𝐸(𝐸 -1 (𝐶 𝑗 ) ⊕ 𝛼). By the boomerang property, with probability (𝑝𝑞) 2 , we ◁ Here |𝐿 triplets | = |𝐷 fin | 2 𝑛 1 (𝑝𝑞) 2 2 𝑖 = 𝐸(𝐸 -1 (𝐶 𝑖 ) ⊕ 𝛼) and
	will have 𝑅 -1 (𝐶 ′ 𝑖 ) ⊕ 𝑅 -1 (𝐶 ′ 𝑗 ) = 𝛿. This difference gets then mapped to 𝐷 fin
	with probability 1. Obtaining the list 𝐿 pairs costs	2 √ 𝑝out𝑝𝑞 data and memory
	and	1 √ 𝑝out𝑝𝑞 log	(	1 𝑝out𝑝𝑞 √	)	computations for sorting the 𝐶 ′ 𝑖 (since 𝐷 fin is a vec-
	tor space, we can sort according to its cosets). This sorting allows to extract
	efficiently the pairs 𝐶 ′ 𝑖 , 𝐶 ′ 𝑗 such that 𝐶 ′ 𝑖 ⊕ 𝐶 ′ 𝑗 ∈ 𝐷 2 𝑛	1 𝑝out(𝑝𝑞) 2 , we find all possible
	key guesses for each of these pairs, that is, all possible 𝐾 out such that (𝐶 𝑖 , 𝐶 𝑗 ) and
	(𝐶 ′ 𝑖 , 𝐶 ′ 𝑗 ) lead to a difference 𝛿 through 𝑅 -1 (in which case they form a boomerang
	quartet). This costs a time |𝐷 fin | 2 𝑛	1 𝑝out(𝑝𝑞) 2 𝐶 out . The list of triplets obtained is of
	size: |𝐷 fin | 2 𝑛	2 𝑘 out 𝑝out (𝑝𝑞) 2

1 √ 𝑝𝑜𝑢𝑡𝑝𝑞 . Algorithm 2

Indeed, in Step 1 we have 𝐸 1 (𝑃 1 )⊕𝐸 1 (𝑃 2 ) = 𝛽 with probability 𝑝 ↓ . By definition of 𝐸, 𝐸 1 (𝑃 𝑖 ) = 𝐸 -1 2 (𝐶 𝑖 ), so in Step 2, we know that 𝐸 -1 2 (𝐶 1 ) ⊕ 𝐸 -1 2 (𝐶 2 ) = 𝛽. If we separate 𝛽 = 𝛽 𝐿 ||𝛽 𝑅 , this rewrites:

  2,𝐿 and 𝐸 2,𝑅 . It requires 1. Select 𝑃 1 at random, set 𝑃 2 = 𝑃 1 ⊕ 𝛼 and encrypt 𝐶 1 = 𝐸(𝑃 1 ) and 𝐶 2 = 𝐸(𝑃 2 ) 2. Compute 𝐶 3 = (𝐶 1,𝐿 , 𝐶 2,𝑅 ) and 𝐶 4 = (𝐶 2,𝐿 , 𝐶 1,𝑅 ) 3. Decrypt: 𝑃 3 = 𝐸 -1 (𝐶 3 ) and 𝑃 4 = 𝐸 -1 (𝐶 4 )

  |𝐷 fin | tuples (𝐶 1 , 𝐶 2 , 𝐶 ′ 1 , 𝐶 ′ 2 , 𝐾 out ), and we took the key 𝐾 out from one of these Algorithm 4 Quantum Last-rounds Key-recovery Input: superposition oracle access to 𝐸 and 𝐸 -1 Output: the full key 1: Repeat ( |𝐷 fin |

	2 𝑛	2 𝑘 out 𝑝 out (𝑝𝑞) 2
			2 𝑘 out 𝑝out
		2 𝑛	(𝑝𝑞) 2

  Bottom boomerang: In the lower part of the boomerang, we start with a difference 128 (changing one bit) in the 4 bytes at positions 2, 4, 5, 12. By decrypting through 𝑆 4 𝐴 4 , this yields a difference 𝑥, -𝑥 in bytes 5 and 6 with probability 1. By decrypting through 𝑆 3 𝐴 3 , this yields a difference active in bytes 3, 9, 11, 14 with probability 2 -7 . Then, by decrypting through 𝐴 2 , we can obtain a difference 128 in all bytes except 2, 4, 9, 12 with probability 2 -30.4 . Middle: In the middle, the S-Box trick allows to traverse the layer 𝑆 2 with probability 1. When going backwards from this middle to the top, everything propagates with probability 1.

[START_REF] Aaronson | Quantum lower bounds for the collision and the element distinctness problems[END_REF]

, with probability 2 -8 , and with probability 1, we obtain a difference 128 in bytes 0, 1, 2, 3, 8, 9, 11, 13, 14, 15 after 𝐴 1 . All other bytes are inactive.

  13.65 ( 2 9.65 (2 30.3 + 216.65 + 219 ) + 2 33.65 ) ≃ 2 53.6 < 2 64 (10

  1. The plaintexts are encrypted under 𝐾 𝐴 and 𝐾 𝐵 and the resulting ciphertexts stored in sets 𝑆 𝐴 and 𝑆 𝐵 . 2. A (carefully chosen) difference 𝛥 𝐶 is XORed to 𝑆 𝐴 and the resulting ciphertexts are decrypted under 𝐾 𝐶 , yielding a set 𝑆 𝐶 of plaintexts. 3. The same 𝛥 𝐶 is XORed to 𝑆 𝐵 and the resulting ciphertexts are decrypted under 𝐾 𝐷 , yielding a set 𝑆 𝐷 of plaintexts. 4. 𝑆 𝐶 and 𝑆 𝐷 are then filtered for valid quartets: we find all the pairs 𝑃 𝐶 ∈ 𝑆 𝐶 , 𝑃 𝐷 ∈ 𝑆 𝐷 such that 𝑃 𝐶 ⊕ 𝑃 𝐷 is 0 in the 7 inactive bytes of the structure ((0, 1), (

  19 subsets of 2 72/3 plaintexts 𝑃𝐴 3:Repeat 219 times 4:Choose one of the 219 subsets for 𝑃𝐴 5: Create a superposition of quartets passing the filter of Step 4 (56 bits), as follows: 6: Create the list of 2 72/3 plaintexts 𝑃𝐴 7: By encrypting under 𝐾𝐴 and decrypting under 𝐾𝐶 , create the set 𝑆𝐶 8: Repeat 2 2×72/3 times 9: Create a single plaintext 𝑃𝐵 ◁ 𝑃𝐵 belongs to a space of size 2 7×9 = 2 72 , by the choice of 𝑃𝐴 10: Encrypt under 𝐾𝐵, decrypt under 𝐾𝐷, obtain 𝑃𝐷 11: Check if there is 𝑃𝐶 ∈ 𝑆𝐶 such that: 𝑃𝐶 ⊕ 𝑃𝐷 is 0 in the 7 inactive bytes wanted (7 bytes), and the condition at Step 5 is also satisfied (2 bytes) Check if the quartet 𝑃𝐴, 𝑃𝐵, 𝑃𝐶 , 𝑃𝐷 yields key guesses ◁ probability 2 -19 16: If it does, return it 17: EndRepeat 18: At this point, we have a (single) quartet returning key guesses: choose one of them depending on 𝑏 19: end function 20: Apply Ambainis' 3-distinctness algorithm to 𝐹 21: Measure and return the single 3-collision among the key outputs of 𝐹 respect to the other factors.

	12:			If there is, return 𝑃𝐷
	13:	EndRepeat
	14:	Find 𝑃𝐷
	15:
	2 • 2 58.9	(	2	⌊ 𝜋 4	√	2 19	⌋ ( 2 • 2 72/3 + 4	⌊ 𝜋 4	2 72/3	⌋	+ negl.	)	+ negl.	)
								≃ 2 59.9 (	2 10.15 (2 25 + 2 25.65 ) )	≃ 2 96.4 . (11)

𝑝 ↓ 𝑝 ↑ encryptions-decryptions, operations and negligible memory. We repeat:

If there are many solutions, an alternative is the BHT algorithm[START_REF] Brassard | Quantum cryptanalysis of hash and claw-free functions[END_REF].

Acknowledgments. This work has been supported by the European Union's H2020 project No. 714294 (QUASYModo) and by the ERC Advanced Grant ALGSTRONGCRYPTO (project 740972).

Appendix

A Round Function of SAFER++

B Application to Related-key AES

In this section, we present the boomerang related-key attack on AES-256 from [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF] and study a corresponding quantum attack. We will see that the classical attack path is actually not adapted to the quantum setting; the quantum attack represents a relatively minor improvement on the classical one, and it can only be considered valid under a restriction on the number of related keys.


C Hureau
email: christelle.hureau@lcc-toulouse.fr

Role of metal ions in Alzheimer's disease: Mechanistic aspects contributing to neurotoxicity

ABSTRACT/WEB SUMMARY

Metal ions have long been linked to the etiology of Alzheimer's disease (AD) via a variety of mechanisms that mainly contribute to a worsening of the pathology. The present chapter proposes a state-of-the-art perspective about the toxic paths related to metal ions, mainly copper and zinc. Copper and zinc that are exchanged within the synaptic cleft can bind to the amyloid-β (Aβ) peptides, a key player in AD. This interaction has two main fallouts: the modulation of the self-assembly ability of the Aβ peptide leading to the formation of amyloid deposits and the production of reactive oxygen species contributing to the overall oxidative stress detected in AD. The molecular basis of these two main toxicity pathways will be described as well as their interrelation and their link with other factors.

Liminary note: Alzheimer's disease is a complex and multifactorial pathology. In the present chapter, the focus is on the role of metal ions in relation with neurotoxic mechanisms. The view is that of a coordination chemist and since the field is fastevolving only recent articles will be quoted except for the "seminal ones".

X.1 Introduction

Alzheimer's disease (AD) was first reported by Alois Alzheimer in 1906 when he described the presence of extracellular deposits in the brain of a 50 years-old woman patient suffering from main memory and behavioral disturbance. 1 Since then, two hypothesis which will be at the core of this chapter have been reported: the amyloid cascade 2,3 and the metal hypothesis. 4 They were firstly described in the 90's and are still used as valuable working bases for both the understanding of the etiology of the disease and the search for therapeutic lines. 4

X.1.1 The amyloid cascade hypothesis

The amyloid cascade assumes that the self-assembly of the amyloid-β (Aβ) peptides is a key and early event in the development of AD. 2 The process takes place extracellularly in the synaptic cleft. The Aβ peptides are crucial biomolecules, originating from the cleavage of the transmembrane amyloid precursor protein (APP) by dedicated proteases. 5 The cleavage is heterogenous both at the N-and C-termini and thus several isoforms exist, 6,7 the longer one being the Aβ1-42 (See sequence in Table 1). Main isoforms at the N-termini are Aβ3/4-y and at the C-termini Aβx-40/42 while some pyroglutamate derivatives Aβp3/p11-y are also present. 8 The importance of the Aβ self-assembly in the pathology is in line with (i) early forms of AD (early-onset (EOAD), counting for about 5% of the total cases) being associated with Aβ mutations [START_REF] Wolfe | Progress in Molecular Biology and Translational Science[END_REF][START_REF] Portelius | [END_REF] or post-translational modifications [START_REF] Portelius | [END_REF][11][12] that increase the peptide self-assembly propensity and (ii) the longer form Aβ1-42 being more prone to self-assemble and more neurotoxic. 7 Although it is well accepted that accumulation of Aβ is tightly linked to AD, its exact role is not clear. Suggestions go from a very central causative role, a risk factor up to a consequence of AD. Accumulation of Aβ originates from a disturbed equilibrium between its production by secretases and its degradation by several proteases.

Increased extracellular content of Aβ is, at least in part, responsible for the formation of Aβ assemblies gathered into deposits, which would instigate further pathological events, including formation of intracellular neurofibrillary Tau tangles, disruption of synaptic connections and neuronal cells death and dementia. 7,13,14

X.1.2 The metal hypothesis

The crucial role of metal ions appeared in the same period and is based on the detection of (i) huge concentration of d-metal ions in the senile plaques (up to mM) while level of such ions are in the µM range in CSF (Cerebro-Spinal Fluid) 15 and (ii) a disturbed metal homeostatis. 16,17 In addition, spectroscopic evidence suggests that Zn and Cu are bound to Aβ in the amyloid plaques. In certain neurons Cu or Zn are expelled into the synaptic cleft, where they can reach concentrations of 1-10 and 10-100 µM, respectively. Hence in some synaptic clefts, high concentrations of looselybound Cu and Zn can be present and they can interact with the Aβ peptides. The interaction between Aβ and metal ions will be detailed below as the first central event leading to neurotoxicity. Further examples of the involvement of metal ions in AD include (i) the binding and regulation of the APP, (ii) a correlation with single nucleotide polymorphism of the Cu transporter ATP7B with sporadic AD and (iii) the decrease of amyloid plaque load in AD mice after disruption of the Zn transporter ZnT-3. 18,19 In addition, studies on postmortem AD brains showed increased of tissue oxidative damages. 20,21 These elevated levels are correlated with the well-known capacity of loosely bound Cu to catalyze the production of reactive oxygen species (ROS). These findings were also confirmed in AD model mice. 22 Hence, redox metal ions can participate to the overall oxidative stress detected in the pathology, by catalyzing the incomplete reduction of dioxygen to ROS. 20,21

X.1.3 Link between the two hypothesis

Metal ions and Aβ self-assembly are related. In vitro, Zn and Cu ions can bind to Aβ 23,24 and modulate its aggregation leading to more toxic species. 25 The increased toxicity could be due to enhanced resistance of aggregated peptides to degradation by protease 26 and/or to formation of oligomeric species able to interact with neuronal membranes (detailed below). 25 In addition, in familial mutants developing EOAD, amino-acid residues able to bind metal ions (histidine (His), aspartate (Asp) are mutated while the self-assembly propensity of the peptides is modified. [27][28][29]

X.1.4 Concluding notes.

Metal ions mediated toxicity of the Aβ peptide is widely studied on its own but also as a model of other amyloid-related diseases, which share many features with AD: 23,30,31 (i) involvement of intrinsically disordered peptides/proteins (IDP) that have the capacity to self-assemble and form β-sheet rich fibrils (defining the amyloid-related diseases) and to bind metal ions; (ii) the detection of amyloid deposits in the vicinity of cells (synaptic cleft in AD, Langherans Islets in Type-2 Diabetes….), (iii) mutations in the peptide sequence of murine animals leading to absence of pathology, and (iv) most importantly for the purpose of the present chapter, the co-presence of abnormally high levels of metal ions in the peptides deposits.

In the present chapter, the ability of metal ions to intervene at several places of toxic pathways will be described (Figure X.1). This mainly includes their intervention in the self-assembly of Aβ and ROS production. A first data to know for assessing their role in such processes is how the metal ions do interact with the Aβ, id est how they bind to the peptides from structural, thermodynamic and kinetic point of views.

[Insert Figure X.1 here]

X.2 Metal ions, Aβ peptides and their interactions

Note: In plaques, mainly Copper (Cu), Zinc (Zn) but also Iron (Fe) are found at high levels. Because the molecular interactions of Fe and Aβ and their biological relevance are still unclear with only very scarce reports on a possible Fe(II) binding to Aβ, [32][33][34] Fe will not be discussed here. The interested readers can find insights into the putative roles of Fe in AD, in the following recent reports (refs. [35][36][37][38][39][40][41][42] ). For similar reasons, the role of Aluminium (Al) in AD is not under focus here, but the interested readers can refer to recent reviews (refs. [43][44][45] ).

In contrast to Fe and Al, the binding ability of Cu and Zn to the Aβ peptides have been studied in depth for more than a decade, but there is no structural data by X-ray crystallography for such metal-complexes of IDP and hence all the binding sites have been proposed from spectroscopic investigations while and the affinity for metal ions were evaluated by complementary methods. The metal binding sites are located in the N-terminal part of the peptides (Table X.1) and to ease the spectroscopic studies Aβx-16 is often used as short and soluble surrogates of the corresponding full-length forms.

X.2.1 Cu(II)

While main studies have focused on the Aβ1-x peptides including the murine variant (Table X.1) and more recently proposed structures have been reported for N-terminally truncated peptides (NT-Aβ). As general and common features the Cu(II) ion lies in an equatorial binding site involving the N-terminal amine, His side-chains, carbonyl function from the peptide bond and, depending on the pH and/or the NT-Aβ isoforms, deprotonated amide bond(s). The apical coordination of water or carboxylate side chains have also been reported. Because Cu(II) is a d 9 ion, several (including advanced) characterization methods (Electron Paramagnetic Resonance (EPR), circular dichroism…) are available and a fair consensus is now shared in the field for Cu(II) binding to Aβ1-x. 23,25,[46][47][48] The main sites of Cu(II) in the key Aβ isoforms are shown in Figure X.2, panel A, while the Cu(II) affinity can range from 10 9 (Aβ1-x) to 10 13 M -1 (Aβ4-x) depending on the nature of the Cu(II) binding site. [49][50][51] Apart from the structural and thermodynamic parameters, the kinetic of Cu(II) binding to various forms of Aβ have been scarcely studied, with binding (kon) rates that depend on the sequence. For Aβ1-x values reported range kon = 2.6 10 6 M -1 s -1 to 5.0 10 8 M -1 s - 1 where the discrepancy may originate from different investigation methods and working conditions. 52,53 For Aβ4-x (or analogues): reported kon value is 2.0 10 8 M -1 s -1 , which corresponds to the anchoring of the Cu(II) forming a 2N intermediate species, 54 but not to its insertion in the ATCUN (Amino-terminal Copper and Nickel Binding) motif (slower step in the milliseconds to seconds time scale). 55,56 [Insert Table X

.1 here] [Insert Figure X.2 here]

X.2.2 Cu(I)

Conversely to Cu(II), the Cu(I) binding site is almost conserved between the various Aβ isoforms provided that at least two His are present in the sequence, since the Cu(I) is linearly bonded between two imidazole rings from His. [59][60][61][62] The His pair involved is still under debate and depends on the peptides. While the nature of the binding site is no more under discussion (Figure X.2, panel B), the affinity is still one main point to solve in the future. Values ranging from 10 6 to 10 10 M -1 are reported, 56,71,[75][76][77] due to different indirect evaluation methods.

X.2.3 Zn(II)

Zn(II) is likely the most difficult ion to study due to its d 10 nature and hence mainly Xray Absorption Spectroscopy (XAS, looking at the Zn) and Zn-induced perturbation of the NMR spectra of the peptides are available techniques. Currently proposed Zn binding sites involved mainly the His side-chains, carboxylates, and N-terminal amine, in a tetrahedral geometry (Figure X.2, panel C). 63,72 The affinity is the low 10 6 range. 78- 80 It is also worth noting that with most of the Aβ isoforms, mainly those bearing either EOAD mutations or post-translational alterations, the formation of dimers (Zn:Aβ = 1:2 or Zn: Aβ = 2:2) is enhanced, an event that can trigger the Aβ self-assembly. [81][82][83][84][85][86][87] With respect to Zn(II), most of the kinetic data reported have been obtained by SPR (Surface Plasmon Resonance) using Acetylated-Aβ counterparts. The kon and koff rates are in the 10 2 M -1 s -1 and 10 -5 s -1 range, respectively. 88

X.2.4 Concluding notes

Taken into account the biological concentration of Zn and Cu within the synaptic cleft upon neurotransmission and their respective affinity for Aβ, the Aβ peptide is able to bind Cu and Zn in vivo.

Another key point to note here is that when bound to Aβ, the metal ions impose their preferred binding sites. This is a main difference with 3D-folded protein where the site is preformed to welcome the cation. In addition, because similar anchors (for instance three imidazoles from His, or 4 carboxylates for Asp and Glu, See Table X.1) are present on Aβ1-x and because of the peptide flexibility, the binding of metal is highly dynamic involving exchange between interchangeable groups for one binding position. 58,89

X.3 Copper mediated ROS production

Oxidative stress is a main component of AD etiology [90][91][92] and many markers have been reported: lipid peroxidation, protein oxidative modifications, RNA and DNA damages. 20,21,93,94 Oxidative stress results from imbalance of ROS produced over ROS detoxified by dedicated enzymes such as catalase. 95 Because redox ions such as Cu in the present case can catalyze the incomplete reduction of dioxygen, they can be involved in the (over)production of ROS that contribute to the overall oxidative stress detected in the pathology, 20,21 in which mitochondria dysfunction also participates. 91,96 Cu in contrast to Zn has the ability to redox cycle between Cu(I) / Cu(II) / Cu(III), while the two main relevant redox states in a biological environment are Cu(I) and Cu(II). 97- 99 It will thus be the main ion involved in ROS formation. Zn doesn't significantly alter the Aβ-mediated Cu ROS production, 100 but indirect pathways linked to Zn dyshomeostasis has been reported to contributed to oxidative stress (for recent reviews, see refs. [101][102][103] ).

X.3.1 Redox properties of Cu(Aβ) species

Redox properties of Cu(Aβ1-x) complex have been studied in details. Because Cu(II) and Cu(I) lie in very different binding sites, the direct electron transfer was precluded and it was proposed that the redox process goes through a chemical -electrochemical chemical path (Figure X.3). The two chemical reactions correspond to pre-equilibria between the Cu(II) (or Cu(I)) species predominantly detected in solution and elusive species in a geometry prone to fast electron transfer, the latter one(s) being known as in-between state(s) (IBS). [104][105][106] The IBS nomenclature originates from the fact that the geometry is common for the two redox state and in-between each geometry of the individual Cu(I) and Cu(II) ions. The IBS has been firstly observed by cyclic voltammetry, hence the electron transfer considered was purely outer-sphere.

Reaching the IBS, the population of which is about 1/1000 is made possible by the highly dynamic of ligand exchange around the Cu ion, as discussed below. The redox signature of Cu(Aβ4-x) have been also reported several times and show a very stable Cu(II) species that can undergo reduction process at very low potentials (< -1 V vs. SCE) while oxidation to Cu(III) is possible but beyond the biological potential range. 66,107,108 When starting from Cu(I) the species can get oxidized at approx. 0.3 V vs. SCE. 56 [Insert Figure X.3 here] In vitro studies of the ROS production ability of Cu(Aβ1-x), thus performed in presence of physiological substrates, id est dioxygen and ascorbate as the reductant have also been reported. 77,105,106,109 The peptide-bound Cu is less efficient in ROS formation than loosely buffer-bound Cu in line with a sluggish electron transfer observed by cyclic voltammetry. 104 Recent in-depth characterizations of the influence of peptide modifications on the rate of ROS production 105,106 and in silico modelling 110 reveal that the in the IBS, the Cu ions lie in environment involving the terminal amine and/or the carboxylate side chain of Asp1, and one or two imidazole rings. The intervention of an IBS is anticipated for Cu(Aβ4-x) as well as for most IDP able to bind Cu in the two redox states.

In brief, the mechanism of ROS production by Cu(Aβ) species depends the coordination site of Cu(II) and hence of the sequence of the Aβ (the Cu(I) site being similar for the various isoforms).

X.3.2 Oxidative damages.

The oxidation of surroundings biomolecules and of the peptide itself is one main biological fallout of the ROS produced by Cu(Aβ) species and one main origin of metalrelated toxicity. The nature of the oxidative damages undergone by the Cu(Aβ)induced ROS are strongly impacted by the level of external reductant in the medium with a double-faced role: from fuel of the ROS production reaction to sacrificial anti-oxidants. 111,112 ROS can also further evolve to RNS (Reactive Nitrogen Species), including peroxynitrite that is formed via the reaction between O2°-113 and NO°. 20

X.3.2.1 General targets

Nucleic acids damages include the formation of oxidized nucleic bases, such as formation of 8-oxo-2-dehydroguanine, 8-hydroxyguanine, 8-hydroxyguanine, 5hydroxyuracyl. 114,115 Protein damages are characterized by increased levels of protein carbonylation while membrane proteins are more touched than cytoplasmic ones 94 and mitochondrial proteins are also a main target. 116 Another key target is the lipids from membranes: 91,117,118 oxidative damages include formation of 4-NHE (4hydroxynonenal), which can further react with lipoic acid or membrane proteins.

Alteration of membrane integrity via membrane proteins and lipids damages further

trigger other events such as Ca 2+ homeostasis that would in turn increase the ROS level, 119 leading to a vicious circle.

X.3.2.2 Aβ oxidative damages

Cu(Aβ1-x) can produce ROS, mainly O2°-, H2O2 and HO°. Upon attack of HO°, the peptide can undergo several kind of oxidative damages. They have been recently reviewed (in ref. 20,120 and refs. therein). In brief, Asp1 can undergo hydroxylation, oxidative fragmentation and decarboxylation-deamination, His (His6, His13 and His14) can be oxidized into 2-oxo-His, Phe into hydroxy-phenylalanine, Tyr (Tyr10) can evolved to dityrosine, and Met (Met35) to methionine sulfoxide.

X.3.3 Influence of Aβ self-assembly

One interesting point is that oxidation of the peptide could influence the (metalmodulated) self-assembly properties of the Aβ peptide because it touches residues involved either in metal binding or important for the self-assembly (Tyr, Met, Phe within the hydrophobic core, Table X.1). For instance, several recent studies reported on the effect of di-tyrosine formation on the self-assembly of Aβ1-40/42 and a general consensus for a strong slow-down of the assembly process and the formation of shorter species compared to the non-oxidized counterpart. [121][122][123] Another key residues scrutinized was Met35. Recent reports agree on the inhibition of fibrils formation with shorter fragments while the kinetic of the self-assembly can either be fastened or slowed-down. [124][125][126][127] Met35-oxidized peptide assemblies are reported to be less toxic than the unaltered counterparts.

It is worth noting that only the effect of site-specific oxidations has been reported until now, while the effect of a global oxidation process touching all the possible residues (Asp1, His, Tyr, Phe and Met) 128, 129 has not been reported so far, although it would be more biologically relevant.

X.3.4 Concluding remark.

Aβ self-assembly is altered by oxidative damages, in link with Cu(Aβ) ROS production.

Hence Cu ions, ROS formation and Aβ self-assembly process are related (Figure X.1).

X.4 Modulation of Aβ self-assembly by Cu and Zn

X.4.1 General features

The other important event in the amyloid cascade is the self-assembly of the Aβ peptides, since the propensity to self-assemble is linked to toxicity.

The self-assembly process is a nucleation-elongation type polymerization process involving various supramolecular interactions between monomers. The peptides exist in various supramolecular polymeric forms, id est monomeric: 1 repeat, oligomeric: number of repeats form 2-20, and protofibrillary and fibrillary states; the latest two being found in the deposits also known as senile or amyloid plaques in AD patients brains. According to the amyloid cascade hypothesis the monomeric soluble form are not toxic conversely to species present during the self-assembly process. The selfassembly process lead to the thermodynamically stable fibrils made of β-sheets, but metastable species such as oligomers and also amorphous aggregates (meaning aggregates where the polymers involved are less structured than in the fibrils, so with a weaker β-sheet content) do exist as well. A schematic view of the self-assembly process is shown in Figure X.4. While dead-end fibrillary products had long been regarded as the toxic species, the paradigm has recently shifted towards the intermediate size species, mainly the oligomers. 14,25,[130][131][132][133][134] The gold standard in the study of self-assembly relies on the use of probes that acquire fluorescence upon interaction (ANS, Bis-ANS, Congo-Red 135 …) and intercalation (thioflavin-T (ThT)) with the various aggregates, 136,137 while ThT is specific of β-sheets-containing species. 138 The kinetic of the self-assembly is mathematically described by a s-shape curve

X.4.2 Mechanisms of toxicity.

In the following, we focus only on toxicity mechanisms in link with the intervention of metal ions in the self-assembly.

Firstly, the importance of Cu and Zn (to a lesser extent) has been evidenced in many studies by the use of ligands able to remove metal ions from Aβ thus preventing their influence on its self-assembly and restoring cell viability. 25,139 In a few reports an enhancement of the toxicity is described after the use of a Cu(II) chelator, that although being not the searched effect, are of crucial importance to document on the mechanism(s) of metal-associated toxicity. 140 At the molecular level, several hypothesis explain the role of metal ions in link with peptides self-assembly:

(i)
Metal-assisted formation of oligomers and their stabilization. Oligomers are currently regarded as the most toxic species among those present during the self-assembly process. Several modes of action have been reported. They include:

formation of pores into the cellular membranes thus modifying the metal (mainly Ca 2+ ) homeostasis; strong interactions with membranes thus perturbing the membrane integrity. 14,25,[141][142][143][144] The identification of the exact role of metal ion in assisting the formation of oligomers and in their stabilization is still scarce, 145,146 with the possible role of inducing covalent cross-linked peptides via oxidative damages. [147][148][149] (ii) Triggering of the self-assembly, consuming the non-toxic monomers species. 150 Possible modes of action include the bridging of two monomers, this has been more particularly been proposed for Zn ; 151, 152 modifying the folding of the monomers to more aggregation prone species. 148

(iii) Preclusion of degradation pathways. Two possible mechanisms are reported. First, in link with oxidative damages of the Aβ peptide formation of covalent dimers (dityrosine bridged peptides for instance) can lead to less degradable peptides deposits by Aβ degrading proteases. 153,154 Besides, in link with metal homeostasis perturbation (see below) some biological cascades are down-regulated leading to a weaker expression of degrading enzymes.

(iv) Modification of the self-assembly kinetic 155 and paths and of the morphology of the assemblies formed. While metal ions alter the self-assembly process of the Aβ peptides, the role of Cu(II) and Zn(II) in this process is still highly under debate with sometimes deeply divergent reports. The more general trend reported for Cu(II) is the slow-down of the aggregation with a role on the elongation phase, where Cu(II) prevents the additions of monomer at the extremities of the filaments. 25,156 For Zn a chaperon-like effect is observed as low ratio (< 0.1) 157 while amorphous assemblies are formed at superstoichiometry. 46 Two main consensual results are: (i) under the very same self-assembly conditions, Cu and Zn influence differently the process and (ii) the stoichiometry between metal and peptide is crucial, with substoichiometric (< 0.1) ratio of metal : peptide impacting the kinetic without strong change in the morphology of the aggregates formed, while superstoichiometric ratio (>1) induce changes in the morphology with more amorphous aggregates formed. 23,46,150,156 The discrepancies between the various reports originate from the various conditions used in the in-vitro self-assembly studies. Main parameters that can change the influence of metal ions are : environmental parameters (pH, buffer, ionic strength, agitation, vessels …), intrinsic conditions (peptide concentration, metal concentration), and the main issue is the perfect monomerization of the peptide, any kind of preformed oligomers will indeed deeply impact the kinetic of the self-assembly by seeding effect. It is thus important to note here that a key bottleneck to the better understanding of the role of metal ions in the self-assembly process is the difficulty to get reproducible and relevant data in vitro. 158 This is one main challenge the chemist will have to keep on facing in the near future.

For Cu(I), its impact on Aβ self-assembly has been poorly investigated due to the difficulty to keep the reduced state intact during the whole process. A recent study reports on the possible mild triggering of the self-assembly via formation of Cu(I)bridged dimer. 159 When Ag(I) is used as a redox stable Cu(I) surrogate, it retards Aβ fibrils elongation. 160

X.4.3 Influence of the aggregation state on the Cu(Aβ)-induced ROS production

The influence of nature of polymers (monomers, oligomers and fibrils) on the ROS production have been shown to follow the order of monomers > oligomers >> fibrils for Aβ1-x but also for other IDP. 161 The reason why the Cu ion is less efficient in promoting ROS production once inserted in fibrils can origin from the less accessibility of substrates and/or to the impossibility of making an IBS once the flexibility of the peptide is hampered by the fibrils structures. 105 Here, an apparent contradiction appears, which is why the oligomers are more toxic while they do produce less ROS. A reconciliation is found if one considers that because oligomers do interact with membranes (more than monomers), the ROS are then produced in a place where they are highly noxious, thus disrupting the membranes integrity by oxidation of the lipid bilayer, as recently reviewed in ref. 162 .

X.4.4 Other important points to consider

While most of in vitro studies on the Cu(II) and Zn(II) effects on the self-assembly of Aβ have been performed with the Aβ1-x, there is a few reports with other Aβ isoforms.

Mainly, EOAD variants as well as NT forms have been studied. As a general trend and in line with the amyloid cascade hypothesis, the EOAD variants show higher propensity to self-assemble in presence of Cu(II) 29 or Zn(II) 28 with respect to the Aβ1-x counterparts. For Aβ4-40 isoform, Cu(II) has a similar effect than on the Aβ1-40. 67 In addition to metal ions, many other biomolecules can influence Aβ self-assembly 163 and can also modulate the metal-altered Aβ self-assembly by external partner. The most significant case is that of membranes, which can help promoting metal-induced oligomerization as reviewed in ref. 162 .

Metal ions can also affect Tau aggregation, 164 where Tau is an intracellular microtubule associated protein responsible for maintaining the stability of microtubule in axons. 165 Mainly an acceleration of the self-assembly and an increase of the toxicity in presence of Zn [166][167][168][169][170] or Cu(II) 171 was reported. Because (i) Tau is mainly an intracellular protein, (ii) because the level of intracellular metal ions is tightly controlled, thus questioning the relevance of the metal ions -Tau interaction and (iii) because the coordination between Tau and metal ions is still poorly investigated, 172-174 the present chapter doesn't focus on the possible toxicity induced by metal ions -Tau interactions.

X.4.5 Future lines of researches

The field of amyloid-forming peptides in link with AD but also other diseases is fast expanding. In this context, future research lines could include investigations of several modulators of Aβ self-assembly at the same time, of Aβ relevant mixtures, 67 of crosstalk between different amyloid-forming peptides (such as Tau and Aβ). 175, 176

X.5 Metal targeting compounds

Because metal ions coordination to Aβ peptides is linked to toxic fallouts, mainly alteration of the Aβ self-assembly and production of ROS, targeting metal ions is currently regarded as an interesting way to alleviate metal ions -related toxicity. Due to its redox ability, Cu is the main target. Many approaches are currently developed and the interested reader can refer to recent reviews on this topic (refs. 46,139,[177][178][179][180][181][182][183][184][185] ). [189][190][191] Other research lines for therapeutics could include fighting the effect of metal-related toxicity, mainly by the use of suicide anti-oxidants 120,[192][193][194] or of (bio)molecules able to overcome the effect of metal ions on the Aβ self-assembly. 163,195

X.6 Concluding remarks

In this chapter, the main toxic pathways linked to metal ions have been described in tight connection with the coordination chemistry of copper or zinc and the Aβ peptides and its consequences on the ROS production and the peptide self-assembly. The role of metal ions is extremely difficult to delineate while AD is multifactorial, but it seems that this topic is more than ever a timely line of research. The better description of how the metal ions influence the pathology is mandatory to discover curative therapeutics that are still severely missing.

FIGURE AND TABLE CAPTIONS

( 2 𝑘)

 2 𝐹(𝑡) = 𝐹 0 + 𝐹 𝑚𝑎𝑥 -𝐹 0 1+𝑒 -𝑘(𝑡-𝑡 1/2 ) ; 𝑡 𝑙𝑎𝑔 = 𝑡 1/2 -, where the three phases (nucleation, elongation and plateau) are described by the tlag, k and Fmax parameters, respectively (Figure X.4). [Insert Figure X.4 here]

Abbreviations 4 -

 4 Abbreviations

Figure X. 1

 1 Figure X.1 Toxic pathways related to metal coordination to the Aβ peptides and

Figure X. 2

 2 Figure X.2 Coordination sites of Cu(II) (A), Cu(I) (B) and Zn(II) (C) to various Aβ

Figure X. 3 .

 3 Figure X.3. IBS species and ROS production.

Figure X. 4

 4 Figure X.4 Formation of Aβ fibrils.

73 Figure X. 4

 734 Figure X.4

Table Captions Table X . 1

 CaptionsX1 Sequences of significant isoforms. Binding residues are highlighted in blue (Cu(II) binding, in thin line = from peptide backbone), orange (Cu(I) binding) and green (Zn(II) binding) for 1:1 metal ions : A complexes, residues involved in self-assembly are underlined (solid lines correspond to -strand and dotted line to the turn), residues undergoing oxidative damages are underlined with double red lines.

	Table X.1
		1	5	10	15	20	25	30	35	40 42	refs.
		DAEFR	HDSGY	EVHHQ	KLVFF	AEDVG SNKGA IIGLM VGGVV IA	57, 58
	Aβ1-42	DAEFR	HDSGY	EVHHQ	K					59-62
		DAEFR	HDSGY	EVHHQ	K					63
	Aβ3-42		EFR HDSGY EVHHQ K					50, 64, 65
	Aβ4-42		FR FR	HDSGY HDSGY	EVHHQ EVHHQ	K K					50, 51, 62, 66, 67 62
	Aβ5-42		R HDSGY EVHHQ K					68
	Aβ11-42				EVHHQ K					69
	Aβp3-42		pEFR HDSGY EVHHQ K					64, 65

Acknowledgments

ERC StG-638712 aLzINK is acknowledged for financial support. All the past and current collaborators and the "Alzheimer and amyloids" team in Toulouse are warmly acknowledged.

THE FOLLOWING IMAGES SHOULD BE SUPPLIED AS SEPARATE FILES in