Xavier Bonnetain

María Naya-Plasencia

André Schrottenloher

On Quantum Slide Attacks

Keywords: quantum cryptanalysis, slide attacks, Feistel networks, Simon's algorithm, Kuperberg's algortihm, slidex attacks, cycle finding

At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon's algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with O(n) quantum time and queries.

In this paper we propose many other types of quantum slide attacks, inspired by classical techniques including sliding with a twist, complementation slide and mirror slidex. These slide attacks on Feistel networks reach up to two round self-similarity with modular additions inside branch or key-addition operations. With only XOR operations, they reach up to four round self-similarity, with a cost at most quadratic in the block size. Some of these variants combined with whitening keys (FX construction) can also be successfully attacked. Furthermore, we show that some quantum slide attacks can be composed with other quantum attacks to perform efficient key-recoveries even when the round function is a strong function classically. Finally, we analyze the case of quantum slide attacks exploiting cycle-finding, that were thought to enjoy an exponential speed up in a paper by Bar-On et al. in 2015, where these attacks were introduced. We show that the speed-up is smaller than expected and less impressive than the above variants, but nevertheless provide improved complexities on the previous known quantum attacks in the superposition model for some self-similar SPN and Feistel constructions.

Introduction

For a long time, symmetric primitives were believed easy to protect against quantum adversaries, by simply doubling the key length. As Grover's algorithm allows to perform an exhaustive search in the square root of the classical time, this counter measure was supposed to provide an equivalent ideal security as before. However, little was known on the attacks a quantum adversary could perform.

Indeed, many new results have recently appeared in this direction, like quantum generic meet-in-the-middle attacks on iterative block ciphers [START_REF] Kaplan | Quantum attacks against iterated block ciphers[END_REF], quantum linear and differential attacks [START_REF] Kaplan | Quantum Differential and Linear Cryptanalysis[END_REF], an analysis of the FX construct against quantum adversaries [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FX-construction[END_REF], improved algorithms for collisions or multicollisions [START_REF] Chailloux | An efficient quantum collision search algorithm and implications on symmetric cryptography[END_REF][START_REF] Hosoyamada | Quantum multicollisionfinding algorithm[END_REF] and [KM10, [START_REF] Kuwakado | Security on the quantum-type Even-Mansour cipher[END_REF][START_REF] Bonnetain | Quantum key-recovery on full AEZ[END_REF] that respectively analyze the security of 3-round Feistel schemes, the Even-Mansour construction and quantumly break the AEZ primitive for authenticated encryption.

Related work.

In [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF], Kaplan et al. considered the superposition query model and, amongst other results, provided for the first time an exponential acceleration of a classical cryptanalysis. Using Simon's algorithm [START_REF] Daniel | On the Power of Quantum Computation[END_REF] the complexity of quantum slide attacks on the alternate-key cipher with bit-wise additions was shown to be of O(n) in that model. In [START_REF] Alagic | Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts[END_REF] some ideas for countering these attacks were proposed. The most interesting one, using modular addition, has recently been studied in detail in [BNP]. This paper provides detailed cost estimates of attacks built over Kuperberg's algorithm [START_REF] Kuperberg | A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF], that applies to modular additions (while Simon's algorithm only concerns bit-wise additions). The authors also propose an algorithm for the case of several parallel modular additions and estimate the cost thereof.

In an independent and very recent result [START_REF] Dong | Quantum attacks on some feistel block ciphers[END_REF], quantized versions of some advanced slide attacks on 2k-and 4k-Feistel schemes were proposed. They correspond respectively to Section 3.4 and a small part of Section 5. The authors also propose a quantum attack on GOST, which is not linked to quantum slide attacks. In [START_REF] Dong | Quantum key-recovery attack on feistel structures[END_REF], the three round distinguisher of [START_REF] Kuwakado | Quantum distinguisher between the 3-round Feistel cipher and the random permutation[END_REF] is exploited to reduce by three the number of keys to search for in a Feistel cipher with independent keys. In [START_REF] Hosoyamada | Quantum meet-in-the-middle attacks: Applications to generic feistel constructions[END_REF], some meet-in-the-middle attacks on Feistel constructions are proposed, in a more restricted model, and the same observation as [START_REF] Dong | Quantum key-recovery attack on feistel structures[END_REF] is presented.

Motivation and Summary of our results.

In this paper we propose the quantized version of several advanced slide attacks proposed in [START_REF] Biryukov | Advanced Slide Attacks[END_REF], like slide attacks on Feistel constructions, the complementation slide attack and the slide with a twist technique. We also present situations where quantum attacks can be composed, allowing for instance to perform efficient key-recovery attacks even when the round functions are clasically strong. We provide the complexities of these attacks when the key is inserted with bitwise-addition (where Simon applies), or with modular additions.

We also propose a quantum version of mirror slide attacks from [START_REF] Dinur | Reflections on slide with a twist attacks[END_REF], and quantum slide attacks exploiting cycle finding, as was proposed in [START_REF] Bar-On | Efficient Slide Attacks[END_REF]. We show that the quantum speedup of the latter is much smaller than expected by the authors.

All these attacks contribute to a better understanding of the post-quantum security of symmetric primitives.

We display in Section 1 all quantum improvements of existing slide attacks that we know of, including our new results.

Organization. The paper is organized as follows. Section 2 presents some preliminaries, as the quantum algorithms used in the paper, and the general principles of slide attacks. Section 3 proposes new quantum advanced slide attacks, considering XOR and modular additions with respect to the ones from [START_REF] Biryukov | Advanced Slide Attacks[END_REF] and [START_REF] Orr Dunkelman | Slidex attacks on the even-mansour encryption scheme[END_REF], mainly considering Feistel networks. Section 4 presents new attacks composing quantum algorithms even when the round function is classically hard to attack, with an improved version of encased algorithm when the key and branch transformations are the same. Section 5 combines the principles of the previous sections to attack 4-round self-similar Feistel ciphers. Section 6 describes our quantum slide attacks when exploiting cycle finding, and the paper is concluded in Section 7.

Preliminaries

In this section we provide a brief introduction to classical and quantum slide attacks, the considered quantum adversary model, and some quantum algorithms used throughout the paper. A description of the results from [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF] regarding quantum slide attacks using Simon's algorithm is also given. A summary of the classical attacks we considered can be found in the Appendix.

Classical Slide Attacks

Slide attacks were introduced in [START_REF] Biryukov | Slide Attacks[END_REF]. In their common principle, they are applied independently from the number of rounds, by exploiting structural properties of the cipher, especially self-similarity.

Notations. We consider a cipher E k : {0, 1} n → {0, 1} n , constructed from a round function F (x, k) : {0, 1} n × {0, 1} m → {0, 1} n applied a certain number of times. There are r rounds and they use round subkeys k 1 , . . . k r derived from the master key K of the cipher. In such constructions, we consider mainly two group operations: the bitwise xor addition, denoted ⊕, and the modular addition, denoted +. By abuse of notation, a general group law will also be denoted +.

Assumptions. We assume that F is a weak function, in the sense that given a pair of equations F (x 1 , k) = y 1 and F (x 2 , k) = y 2 , it is computationally easy to retrieve the key k. Notice that in some settings, F may be more difficult to attack; in which case we will need more of these equations. Moreover, the notion of weakness is broader in a quantum setting. This is developed in Section 4.

Basic slide property.

Suppose that all the round subkeys are equal:

k 1 = k, . . . k r = k;
i.e the scheme is one-round self-similar. From the structure of the cipher, which is r similar applications of the same permutation x → F (x, k), we may write a simple equality, the

P 0 F (•, k) F (•, k) . . . C 0 P 1 F (•, k) . . . F (•, k) C 1
E K (F (x, k)) = F (E K (x), k) (1)
Basic slide attack. The goal of the attacker is to find two pairs x, y satisfying F (x, k) = y.

The birthday paradox implies that, among O 2 n/2 plaintext-ciphertext couples P, C, there exists a slide pair: P 0 , C 0 and P 1 , C 1 such that F (P 0 , k) = P 1 . In that case, we also have:

F (C 0 , k) = C 1 .
Since we suppose F weak, these two equations suffice to retrieve the key k.

Hence, the simplest attack setting consists in performing O 2 n/2 queries, then checking for each pair P 0 , C 0 and P 1 , C 1 if it is a slide pair; and in that case returning the key k. This requires O 2 n/2 memory and O(2 n ) time independently of the length of k (as soon as the slide equations allow to retrieve it).

Example of weak round function.

In the case of a keyed permutation F (x, k) = k⊕Π(x), as shown in Figure 2, a slide pair (P 0 , C 0 ), (P 1 , C 1 ) satisfies

F (P 0 , k) = P 1 i.e P 1 = k⊕Π(P 0 ), which is equivalent to C 1 = k⊕Π(C 0 ). Hence it suffices to check if P 1 ⊕C 1 = Π(P 0 )⊕Π(C 0 ). P 0 k Π k Π . . . k C 0 P 1 k Π . . . k Π k C 1 P 1 C 0 Figure 2:
Example of slide attack on a cipher with a weak round function Slide attacks have been successfully applied to the TREYFER cipher, variants of DES and Blowfish and Feistel constructions [START_REF] Biryukov | Slide Attacks[END_REF]. We do not study stream ciphers in this paper and focus on block ciphers.

Some Definitions

We define quickly some generic constructions mentioned in the rest of this paper.

rk-Feistel and rk-SPN. We name rk-Feistel and rk-SPN versions of those ciphers where the round keys form a periodic sequence of period r. In particular, 1k-Feistel denotes the case where all subkeys are equal. It may be useful to see those schemes as a composition of the same, repeated, but more intricate, round function

F = F (k 1 ) • . . . • F (k r ).
Whitened Feistels. We also consider what has been called the DESX construction, which consists in adding additional independent whitening keys to a Feistel cipher, that is:

W F eistel : {0, 1} k × ({0, 1} n ) 3 → {0, 1} n ( k , k x , k y , m ) → k y ⊕ F eistel(k, m ⊕ k x ) .
This is an example of the FX construction, which consists of applying key whitenings to a block cipher. In this paper, the notation rk-WFeistel refers to a rk-Feistel scheme augmented by key whitenings.

The Attack Model

In this paper we consider the well introduced and defined model of superposition quantum queries. It means that the adversary is not only allowed to perform local computations on a quantum computer, but is also allowed superposition queries to a remote quantum cryptographic oracle. Given a superposition of inputs to this oracle, it returns the superposition of the outputs. This setting has been described in [START_REF] Damgård | Superposition Attacks on Cryptographic Protocols[END_REF][START_REF] Boneh | Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World[END_REF][START_REF] Zhandry | How to Construct Quantum Random Functions[END_REF]. The considered attacks will be denoted as superposition attacks. This model, though strong, is simple and non-trivial, and security in this model implies security in any other scenario. It is a well accepted model and, for discussions on its importance, we refer to [START_REF] Gagliardoni | Semantic Security and Indistinguishability in the Quantum World[END_REF] and [START_REF] Gagliardoni | Quantum Security of Cryptographic Primitives[END_REF].

Cost Metric.

The cost metric we use is the number of quantum encryption/decryption queries we perform, and the number of quantum gates we have to use. Our quantum time unit is the cost of one query. We estimate that one quantum query costs Ω(n 2 ) quantum gates, as we are considering block ciphers, for which we want a dependency between all the input and output bits. Hence, we estimate that an algorithm with n 3 operations has a cost similar as n queries.

Quantum Slide Attacks

Quantum Slide Attacks are built upon classical ones and they reduce drastically their cost, thanks to the use of quantum algorithms and the model of superposition queries. Classically, the general layout of a slide attack is to perform a certain amount of queries, among which, thanks to the analysis, we expect one or more slide pairs to occur. Sometimes these pairs can be detected; sometimes one merely tries all possibilities. Using these pairs, one can then break a smaller component of the cipher (e.g its weak round function F (•, k)) and retrieve some secret material (e.g some subkeys).

In the quantum setting, an exponential speedup can be obtained by the use of a quantum Hidden Shift Algorithm. In turn, this puts heavier constraints on the structure of the attack. Instead of merely promising that some slide pairs will be found, we must ensure that a Hidden Shift property holds, that must be valid for all inputs. When rewriting classical into quantum slide attacks, we will call this property a slide-shift property.

Generically, it consists in a functional equality, g 0 (x) = g 1 (x + s), with two functions g 0 and g 1 depending on the encryption scheme and some publicly known parameters or components, and s a secret value (generally a subkey) that we seek. This is not always doable (in particular, it requires that all the inputs belong to a slide pair), which explains why some slide attacks have a more efficient quantum counterpart than others. Moreover, the cost depends on the group law +. For the bitwise XOR additions, we rely on the polynomial-time Simon's quantum algorithm [START_REF] Daniel | On the Power of Quantum Computation[END_REF], and for modular additions, the subexponential-time Kuperberg's quantum algorithm [START_REF] Kuperberg | A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF], which are described below.

Quantum Slide Attacks were first introduced in [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF], where the authors show that such rewriting is doable for Figure 2. Their slide-shift property is the equality, for all x:

Π(E k (x)) ⊕ k = E k (Π(x ⊕ k)) .
Hence g 0 (x) = g 1 (x ⊕ k) where g 0 (x) = Π(E k (x)) and g 1 (x) = E k (Π(x)) ⊕ x, and since superposition queries to E k are authorized, Simon's algorithm can be applied.

Composing Algorithms

The previous method recovers a value s, which depends on the instance. This value can be fixed, but it can depend on some context parameters, becoming s(y) for a given y, independent of the inputs of g 0 and g 1 . In that case, we can see the quantum algorithm as a classical oracle to the function y → s(y). Classically, the function s is often assumed to be weak, that is, the secrets we seek can be found with a few input-output pairs. But we can go further, and do all the computation reversibly on the quantum computer, which means we can make a quantum oracle to the function s, and apply any quantum algorithm on it. The relevant security notion for s becomes its quantum security, and not only the classical one.

As we want to make a proper unitary that computes the function y → s(y), the cost is doubled, as all the intermediate computations need to be uncomputed. This is a case of quantum algorithm composition, as the Grover-meets-Simon technique [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FX-construction[END_REF]. Exemples of compositions are presented in Section 4 and 5.

Quantum Hidden Shift Algorithms

Simon's Algorithm

Simon's algorithm [START_REF] Daniel | On the Power of Quantum Computation[END_REF] is a quantum algorithm designed to solve the following problem:

Problem 1 (Simon's Problem). Let G : {0, 1} n → {0, 1} n . Given the promise that there exists s ∈ {0, 1} n such that for any

(x, y) ∈ {0, 1} n , [G(x) = G(y)] ⇔ [x ⊕ y ∈ {0 n , s}], find s.
This problem is a hidden subgroup problem in the group ((Z/(2)) n , ⊕). Due to the structure of the group, it can also solve a problem of hidden shift in it, which is as follows:

Problem 2 (Simon's Problem, Hidden Shift Version)). Let g 0 , g 1 : {0, 1} n → {0, 1} n two permutations such that there exists s ∈ {0, 1} n such that, for all x, g 0 (x) = g 1 (x ⊕ s). Find s.

Proof.

Let G :

{0, 1} × {0, 1} n → {0, 1} n (b, x) → g 0 (x) if b = 0 g 1 (x) if b = 1 . G satisfies G(b 0 , x 0 ) = G(b 1 , x 1 ) if and only if (b 0 ⊕ b 1 , x 0 ⊕ x 1 ) ∈ {(0, 0), (1, s)}.
Simon's algorithm finds a value v that satisfies v • s = 0 in only one query. Hence, one will have enough information to retrieve s with little more than n queries.

In order to retrieve the secret, we then need to solve a linear system. The cost of this part is in O n 3 gates. As one query is estimated to cost Ω(n 2 ) gates, the time cost will also be n. In the case of a purely quantum implementation, we estimate the cost to be 2n, to take into account the uncomputing of the intermediate values.

Use in Cryptanalysis.

In cryptanalysis, the function G under study is built from a block cipher and possibly public components; we suppose that all can be queried in quantum superposition. The implication: [G(x) = G(y)] ⇒ [x ⊕ y ∈ {0 n , s}] might not be true; indeed, some additional, random collisions can occur.

As shown in [KLLN16a, Bon18, LM17], Simon's algorithm is still very efficient in that case. There is a fixed multiplicative overhead estimated to be close to 3 [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF], around 2 [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FX-construction[END_REF] or less than 1.2 [START_REF] Bonnetain | Quantum key-recovery on full AEZ[END_REF], the algorithm being less efficient if some differentials occurs with a high probability.

We will consider here a cost of n queries for Simon's algorithm, as the overhead does not change much on the complexity. The failure rate of this algorithm decreases exponentially with the number of queries once the threshold is passed, hence we will also neglect the failure probability of the algorithm when we use it as a routine for another quantum algorithm.

Kuperberg's Algorithm and Variants

Kuperberg's Algorithm aims at solving the abelian hidden shift problem, defined as: Problem 3 (Abelian Hidden shift problem). Let (G, +) an abelian group, g 0 , g 1 : G → G two permutations such that there exists s ∈ G such that, for all x, g 0 (x) = g 1 (x + s). Find s.

Many variants of Kuperberg's algorithm have been proposed [START_REF] Kuperberg | A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF][START_REF] Kuperberg | Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[END_REF][START_REF] Regev | A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space[END_REF]. As we consider symmetric primitives, we're mainly interested in the case of addition modulo a power of two, which is fairly common. Moreover, we want concrete estimates for given parameters. This case has been studied in [BNP], where various algorithms and explicit costs for groups of the form (Z/(2 w )) p are proposed.

Concretely, the cost estimate (in quantum memory, time and queries) is 2

√ 2 log 2 (3)n 2 1.8 √ n for the group Z/(2 n ).
The authors also propose an algorithm with a cost of 2(p/2 + 1) w for the group (Z/(2 w )) p , which is especially interesting for small w, as it is polynomial in p, and generalize these algorithms to any group of the form (Z/(2 w )) p . As the worst case is for Z/(2 n ), we will consider this complexity in our cost estimates. As before, for a purely quantum implementation, we estimate that the cost is doubled.

Quantum Slide-shift Attacks

In this section, we first present a quantum slide attack on an iterated keyed permutation, similar to the one in [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF], but with modular additions instead of xor, therefore using the precise results from [BNP] for applying Kuperberg's algorithm. Next, we present new advanced quantum slide attacks on Feistel networks, with slide attacks based on one-round self-similarity and advanced sliding techniques from [START_REF] Biryukov | Advanced Slide Attacks[END_REF], applied to Feistel variants. We consider all the possible combinations of modular additions and XORs. We also use some ideas from [START_REF] Orr Dunkelman | Slidex attacks on the even-mansour encryption scheme[END_REF] (mirror slidex attack). The round function is assumed weak.

Key-alternating Cipher with Modular Additions

The slide attack on the key-alternating cipher is described in Figure 3 (the primitive in itself is the first line of the figure).

denotes a modular addition. The round permutation is denoted Π and the whole encryption function E k .

As with the Simon attack, we can define the following function:

G : {0, 1} × {0, 1} n → {0, 1} n b, x → g 0 (x) = Π(E k (x)) -x if b = 0, g 1 (x) = E k (Π(x)) -x if b = 1.
Also as in the previous attack, we know that all

x satisfy Π(E k (x)) + k = E k (Π(x + k))
because of the sliding property. Then we can see that G verifies the conditions of the

P 0 k Π k Π . . . k C 0 P 1 k Π . . . k Π k C 1 P 1 C 0
(x) = g 1 (x + k): G(0, x) = Π(E k (x)) -x = E k (Π(x + k)) -k -x = G(1, x + k).
We reasonably assume that both E k • Π and Π • E k are indistinguishable from a random permutation, and we can apply Kuperberg's algorithm. This way we can recover k with a complexity of 2 1.8 √ n quantum time and queries.

Feistel Scheme with One Round Self-similarity and Modular Additions

We consider from now on Feistel schemes, like the one represented in Figure 4. The block message is decomposed in two branches, one branch has a round key added, and a round function applied to it, and is next added (by a xor or a modular addition) to the other branch before the two branches swap places. This is repeated a number of times before generating the ciphertext. For a Feistel construction, if we consider a slide attack over one round, the right part of the first plaintext R (left side in Figure 4) will be the same as the left part of the second plaintext, L . Classical adversaries could use a fixed right part, and take random plaintexts for the left part.

In our quantum attack, we will consider a fixed and known value for these variables R 0 = R = L . As the value of R = R 0 is fixed, we can consider in our attack the variable k = f (R 0 + k), represented in Figure 4, as an equivalent key, and this will be the value retrieved by Kuperberg's algorithm. We denote one encryption function as E k , we denote by T runc L and T runc R the function that truncates a Feistel state to only its left or right part respectively, and the round function as f , as represented in Figure 4. We first describe the function that we will use in our attack:

G : {0, 1} × {0, 1} n/2 → {0, 1} n/2 b, x → g 0 (x) = T runc R (E k (x, R 0 )) if b = 0, g 1 (x) = T runc L (E k (R 0 , x)) if b = 1.
From Figure 4 we can verify the slide shift equation g 0 (x) = g 1 (x + k ). By applying Kuperberg's algorithm we will recover the value of k = f (R 0 + k) for the fixed value of R 0 that we fixed in the beginning. Since we know R 0 , we can retrieve the actual value of k when f is weak. The cost of this attack, that considers modular additions, is 2 1.2 √ n . If instead we had xors, the analysis is quite similar, and the time complexity is reduced to around n. This basic attack is generalized to any non-denegerate function f in Section 4 (it works as long as the key k is added or xored as on Figure 4).

The Quantum Complementation Slide Attack

We illustrate the complementation slide attack [START_REF] Biryukov | Advanced Slide Attacks[END_REF] on a Feistel cipher with 2-round self-similarity, like for instance 2k-DES, introduced in [BW99]. We consider the 3 possible

L f k R f k f k N M k R L L f k R f k f k N M N M R = L M = N M + f (N + k) = M
Figure 4: Slide attack on Feistel scheme with one round self-similarity and modular addition ways of adding the keys when determining the attack complexities, but we only describe the attack considering key insertions and round combinations by modular additions. In the next section, we will consider the case where both operations are different.

The main idea of this attack, described in Figure 5, is to consider not two rounds for the slide pair, but just one. This implies that the round-keys of the middle rounds are not the same, which can be compensated by adding a relative difference between the complemented slide pairs. We will describe here the attack for the case when the key and the Feistel combination are done with modular additions. As can be seen in the figure, if we denote by ∆ = k 0 -k 1 and if the following equations are verified: R = L -∆ and L + f (R + k 0 ) = R + ∆, then, the outputs of both plaintexts, (M, N ) and (M , N ) verify N = M -∆ and N = M + f (k 1 + N + ∆) -∆. It is easy to verify that, with such inputs, all the transformations through the f functions will be the same pairwise through all the slid pairs. The combination of both halves ensures that the input round differences stays as wanted, and the same property can be found at the end of the functions.

In this case, in order to quantize the attack, we propose to combine an exhaustive search with Grover and Kuperberg's algorithm for solving the hidden shift problem. Here, for the sake of simplicity, we limit ourselves to describing the generic lines of the attack.

We perform an exhaustive search on ∆. The size of a block and of the whole key is n. Considering the value of R fixed to a chosen and known one, we can redefine an equivalent round-key k 0 = f (R + k 0 ): the correspondence between k 0 and k 0 is bijective, and when we recover k 0 we can immediately deduce k 0 . The exhaustive search can be combined with Kuperberg's algorithm applied to the following function (keeping in mind that R and ∆ are known to the attacker):

G : {0, 1} × {0, 1} n/2 → {0, 1} n/2 b, x → g 0 (x) = T runc R (E k (x, R)) + ∆ if b = 0, g 1 (x) = T runc L (E k (R -∆, x + ∆)) if b = 1.
From Figure 5 we can verify that g 0 (x) = g 1 (x + k 0 ). For each of the tested values for ∆, by applying Kuperberg's algorithm we will recover the value of k 0 for the fixed value of R that we fixed in the beginning, R 0 . From k 0 and R 0 we directly recover k 0 because f is weak, and with ∆, this implies the value of k 1 . When the tested value for ∆ is the correct one, we should also obtain a collision given by N = M + f (k 1 + N + ∆) -∆, which happens with a random probability 2 -n . When this is the case, this implies that we The cost for this if all the transformations were xors would be of n2 n/4 , compared to 2 n/2 from the quantum accelerated exhaustive search of the generic attack. If we have modular additions instead, the cost becomes 2 1.2 √ n+n/4 , which is still better than generic exhaustive search of the key. We can however do better if the key and branch addition are exactly the same. This is developed in Section 4.

L f k 0 R f k 1 f k 0 f k 1 N M R + ∆ L -∆ Encryption L f k 0 R f k 1 f k 0 f k 1 N M M -∆ N + ∆ Encryption

Sliding with a Twist

A further improved variant of the slide attacks is the sliding with a twist, also introduced in [START_REF] Biryukov | Advanced Slide Attacks[END_REF], that can be applied against some Feistel constructions when we have superposition access to the decryption oracle.

This attack applies to ciphers with the same structure as in Figure 6, and small variants can also be applied to DESX or to reduced-round versions of GOST. The quantum version can be applied as long as the two branches are added with a xor. The round key can be added also by modular addition or multiple modular additions. We will describe the attack considering key insertions and round combinations by xor, the addition of the key being irrelevant for the complexity.

The main idea of this attack is to consider that encryption of a two-round self similarity Feistel cipher is a slid version of its decryption, modulo the final twists, that are easily taken into account. For (L, R), (M, N ) as inputs and outputs of the encryption function and (M N ), (L , R ) as inputs and outputs of the decryption one, we have that if

R = N and M = L ⊕ f (R ⊕ k 0 ), then R = N and L = M ⊕ f (N ⊕ k 0 ).
We can consider now R = N as a fixed chosen value. Like the previous attack, if we consider an equivalent key k 0 = f (R ⊕ k 0 ), we can apply Simon's algorithm. Let us denote the decryption function D k .

G : {0, 1} × {0, 1} n/2 → {0, 1} n/2 b, x → g 0 (x) = T runc R (E k (x, R)) = N if b = 0, g 1 (x) = T runc R (D k (x, R)) = R if b = 1.
From Figure 6 we can verify the slide shift equation g 0 (x) = g 1 (x ⊕ k 0 ). Simon's algorithm recovers the value of k 0 , and from it, also the one of k 0 with negligible complexity

L M f k 0 N R f k 1 f k 0 f k 1 N M Encryption f k 1 N M f k 0 f k 1 f k 0 R L M N

Decryption

Figure 6: Representation of the sliding with a twist technique because f is easy to invert. We can repeat a similar attack peeling off one layer in order to recover also k 1 with comparable complexity.

The cost when all the transformations are xors is n, compared to 2 n/2 for the quantum accelerated exhaustive search. If we have modular additions between branches, this attack does not apply, as the decryption scheme has subtractions instead of additions.

Composing Quantum Attacks: Key-Recovery with Strong Round Functions

In this section, we propose efficient key-recovery attacks on self-similar Feistel constructions when using some classically strong round functions. We show that as long as the round function is vulnerable to quantum attacks, the key will be recovered with a complexity at most the cost of the quantum round attack multiplied by the cost of the quantum attack on the one-round self-similar Feistel (that will be around n if the branch addition is bitwise, or around 2 1.2 √ n if it is a modular addition), by composing both algorithms. This composition allows to recover the key and perform an attack in cases that are classically sound.

In what follows, we describe the generic case and show an even more efficient attack when the round function has the form f (x + k) (with f strong as, for instance, a hash function) and the branch and key additions are the same.

General Attack

In the attacks presented in the previous section, the round function was supposed to be weak. If it was not, we would still be able to recover the values of k = f k (R 0 ). The problem next would be to recover k, which would not be directly possible.

We show here how to quantumly attack the round function in some common cases. In the previous attacks, the value of R 0 was fixed to a random chosen value. This means that we can repeat the same operation for several values R i .

L f k R 0 f k f k N M R L L f k R f k f k N M N M R 0 = L L = R -f k (R) M = N M + f k (N ) = N

Case f(x+k).

We consider here that the round function is a key addition composed with a public function f , as this is a fairly common design. We use the attack of Section 3.2, which, given a value R 0 , produces f (R 0 + k). As presented in Section 2.4, we consider this attack as a quantum black box H, that takes an input x, and produces f (x + k). Given this H, we can construct the following function G:

G : {0, 1} × {0, 1} n/2 → {0, 1} n/2 b, x → g 0 (x) = H(x) = f (x + k) if b = 0, g 1 (x) = f (x) if b = 1.
It is now easy to identify k as the hidden shift of G.

The cost of the attack is summarized in Table 2 for a Feistel scheme with one-round self-similarity, and it is easy to extend it to other scenarios. For the case of two modular additions we can still have different operators if they use, for instance, a different bit order.

Generalization of the attack. We described the attack for a Feistel round function of the form f (x + k), but we can use this attack for any keyed function vulnerable to quantum key recovery, like Even-Mansour (see Figure 8), a 3-round Feistel, a self-similar Feistel. . . Using the same principle as above, we manage to craft a quantum oracle to the inner round function. Now, we can attack it using any quantum algorithm that needs a quantum superposition access on it, without any additional constraint. The total cost of the attack is the cost to attack the round function multiplied by the cost of the slide attack. This means that the one-round self-similar Feistel construct offers essentially the security of its inner round function. This is not the case classically, as the cost to find a slide pair is 2 n/2 ; it would generally be the cost of the total attack, as the inner round function operates on n/2 bits.

For the example in Figure 8, the exhaustive search is classically in 2 n/2 , quantumly in 2 n/4 . The classical slide attack can find a pair (x, f k (x)) in 2 n/4 queries. Once this is done, we can easily retrieve some other slide pairs using the slide pairs at the output of the cipher, and do the standard slide attack to break Even-Mansour in 2 n/4 more queries and time. The quantum slide attack performs in n2 1.2 √ n queries.

With the Same Branch and Key Addition

If the round function is f (x+k) and the branch and the key addition both use the same law, the attack can be made more efficient. We can consider a Feistel construct E k composed of a certain number of iterations of the function f k (x, y) = y, x + f (y + k). In that case, we have

f k (x, y) + (k, k) = f 0 (x + k, y + k), hence E k (x, y) + (k, k) = E 0 (x + k, y + k). We can then consider G : {0, 1} × {0, 1} n/2 → {0, 1} n b, x → g 0 (x) = E k (x, x) + (x, x) if b = 0, g 1 (x) = E 0 (x, x) + (x, x) if b = 1.
The hidden shift is k here.

Case f (x + k), 2-rounds Self-Similarity. It can also be generalized if the Feistel has two alternating keys (k 0 , k 1 ), we can use

G : {0, 1} × {0, 1} n/2 2 → {0, 1} n b, x, y → g 0 (x) = E k0,k1 (x, y) + (x, y) if b = 0, g 1 (x) = E 0,0 (x, y) + (x, y) if b = 1.
As we have the same property E k0,k1 + (k 0 , k 1 ) = E 0 (x + k 0 , y + k 1 ), the hidden shift is (k 0 , k 1 ).

Table 2 presents a summary of the costs of this attack, depending on the group operation for the branch addition, and the key addition. + can represent a modular addition, or multiple additions in parallel, as long as it is the same operation at each round. It can be different for the branch and the key, except for the sixth and last attack in the table.

Advanced Quantum Slide Attacks on Feistels

In this section, we give our best attacks on self-similar Feistel schemes, most of them based on slide shift properties. These attacks reach up to four rounds of self-similarity, they run very efficiently and also concern whitened versions, but the operations used (branch or key addition, whitenings) are limited to xors.

Mirror Slidex Attack on 2k-WFeistel.

The mirror slidex attack [START_REF] Orr Dunkelman | Slidex attacks on the even-mansour encryption scheme[END_REF] applies to any cipher that can be decomposed as

E = E 2 • E 1 • E 0 where E 1 is an involution (E 1 • E 1 = Id).
It is in fact a generalization of the sliding with a twist, which corresponds to the case where E 2 = Id.

√ n +, + f (x + k) 2 1.2 √ n
Need the exact same addition

+, ⊕ f k (x) n2 1.2 √ n
Simon calls purely quantum Kuper.

+, + f k (x) 2 2.4 √ n+1
Kuper. calls purely quantum Kuper.

⊕, ⊕ f (x ⊕ k) n 2-Round self-similarity +, + f (x + k) 2 1.8 √ n
2-Round self-similarity, Need the exact same addition In that case, the equation that we can write is:

E -1 0 •E -1 2 •E(P ) = E -1 •E 2 (E 0 (P ))
. If E 0 and E 2 have a good form, we can turn it into a slide shift property, and quantumly attack using Simon's or Kuperberg's algorithms. A classical mirror slidex does not necessarily give rise to a quantum one.

Consider a 2k-WFeistel scheme as in [DKS15, Section 7.3] (2K-DESX in the paper). The authors combine the mirror slidex with the complementation slide. This is also what we do, although we prefer writing the attack as an updated slide shift. Let us denote

E(x) = k post ⊕ E k (k pre ⊕ x)
where E is the full cipher, k pre and k post are the pre and post-whitening keys, of size n each (they are xored to the full state of the cipher), and E k is a 2k-Feistel scheme of alternating keys k 0 , k 1 of size n 2 each. We have E k (x) = k post ⊕ E(k pre ⊕ x). We also denote k L post , k R post , k L pre , k R pre the respective left and right sides of the whitening keys. The whole key of E is k 0 , k 1 , k pre , k post of size 3n. We note ∆ = k 0 ⊕ k 1 . Recall the slide shift property coming from the complementation slide technique:

T runc R (E k (x, R)) ⊕ ∆ = T runc L (E k (R ⊕ ∆, x ⊕ f (R ⊕ k 0 ) ⊕ ∆)) .
We replace calls to E k by E, which is our oracle, and obtain that:

T runc R (E(x ⊕ k L pre , R ⊕ k R pre )) ⊕ k R post ⊕ ∆ = T runc L (E(R ⊕ ∆ ⊕ k L pre , x ⊕ k R pre ⊕ f (R ⊕ k 0 ) ⊕ ∆)) ⊕ k L post .
Let us denote ∆ = ∆ ⊕ k L pre ⊕ k R pre as an adapted value of ∆, we rewrite:

T runc R (E(x, R)) ⊕ ∆ ⊕ (k L pre ⊕ k R pre ⊕ k L post ⊕ k R post ) = T runc L (E(R ⊕ ∆ , x ⊕ ∆ ⊕ f (R ⊕ k 0 ))) .
Our new slide function is:

G : {0, 1} × {0, 1} n/2 2 → {0, 1} n/2 b, x, y → g 0 (x, y) = T runc R (E k (x, R)) ⊕ y if b = 0, g 1 (x, y) = T runc L (E k (R ⊕ ∆ , x ⊕ ∆ )) ⊕ ∆ ⊕ y if b = 1.
where we guess the value of ∆ . Then G verifies the slide shift property g 0 (x, y) = g

1 (x ⊕ f (R ⊕ k 0 ), y ⊕ (k L pre ⊕ k R pre ⊕ k L post ⊕ k R post )
). Now, as we did in Section 4, we can consider this whole slide attack as a black box, that, given an input R, outputs f (R ⊕ k 0 ). As f is public, we can create a quantum oracle to the function

G (R) = f (R) ⊕ f (R ⊕ k 0 )
. This function has k 0 as a hidden period, which can be recovered, by reusing Simon's algorithm.

Since ∆ is guessed, we deduce

k 1 ⊕ k L pre ⊕ k R pre .
There now remains only one unknown subkey in the Feistel. We can apply the quantum attack on the FX construction [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FX-construction[END_REF] to recover it and the whitening keys in O n2 n/4 queries and time.

If different operations are used (e.g, modular additions for the whitenings and a xor inside the mirror property), this attack does not seem to work anymore, as the whitening and the slide operation would not commute. Furthermore, using decryption queries (as in the sliding with a twist attack on 2k-Feistel) does not seem to allow the complexity to decrease, due to the presence of the whitenings. A guess of n 2 bits of information, with Grover, seems still mandatory.

Attacking 4k-Feistel and 4k-WFeistel

Combining twist and complementation slides enables the authors in [START_REF] Biryukov | Advanced Slide Attacks[END_REF] to attack a 4k-Feistel. In this section we show how to efficiently quantize this attack and extend it to 4k-WFeistel. The main idea is that encryption and decryption can be compared in this way (see Figure 9):

k 0 k 1 k 2 k 3 k 0 k 1 . . . k 3 k 2 k 1 k 0 . . .
So that the keys k 0 and k 2 always coincide, whereas the keys k 3 and k 0 correspond to rounds having a constant difference.

The slide pairs will have a difference ∆ = k 1 ⊕ k 3 as can be seen in Figure 9, similarly to the complementation slide technique. We gather from [BW00] that a slide pair (P, C) = (L, R), (M, N ) (in input to the encryption function), (P , C ) = (L , R ), (M , N ) (in input to the decryption function) satisfies the following properties:

L , R = M ⊕ ∆ ⊕ f (k 0 ⊕ N ), N M , N = L ⊕ f (R ⊕ k 0 ) ⊕ ∆, R For all P = (x, R) we write D k (M , N ) = (L , R ), M = T runc L (E k (x, R)), N = T runc R (E k (x, R)), which gives: D k (x ⊕ f (R ⊕ k 0 ) ⊕ ∆, R) = M ⊕ ∆ ⊕ f (k 0 ⊕ N ), N =⇒ T runc R (D k (x ⊕ f (R ⊕ k 0 ) ⊕ ∆, R)) = T runc R (E k (x, R))
Hence, for a fixed R, we have the following function G:

G : {0, 1} × {0, 1} n/2 → {0, 1} n/2 b, x → g 0 (x) = T runc R (D k (x, R)) if b = 0, g 1 (x) = T runc R (E k (x, R)) if b = 1.
The hidden shift between g 0 and g 1 is f (R ⊕ k 0 ) ⊕ ∆. As in Section 4, we remark that the function R → f (R ⊕ k 0 ) ⊕ ∆ ⊕ f (R) has k 0 as hidden period, which can be recovered with Simon's algorithm. The total cost is around n 2 /2 queries (the input space is of size n/2, the inner Simon needs uncomputation), for recovering k 0 . Once k 0 is known, we can directly use the first attack to get ∆ = k 1 ⊕ k 3 , at a negligible cost of n/2.

L f k 0 R M ⊕ ∆ N f k 1 f k 2 f k 3 f k 0 f k 1 f k 2 f k 3 M N M N f k 3 f k 2 f k 1 f k 0 f k 3 f k 2 f k 1 M ⊕ ∆ N f k 0 L R
Moreover, we can "shift" the cipher, that is, suppress the first round of encryption, and add it at the last round, in order to get access to the same cipher, but with keys (k 1 , k 2 , k 3 , k 0 ) instead of (k 0 , k 1 , k 2 , k 3 ). Hence, we can repeat the same attack, to get k 1 , and ∆ = k 2 ⊕ k 0 . With k 1 and ∆, we obtain k 3 , and with k 0 and ∆ , we obtain k 2 . The total cost is around n 2 , for a total key size of 2n bits.

As this attack uses the sliding with a twist technique, it does not transpose well to modular additions (the decryption oracle would use subtractions instead of additions).

Attacking 4k-WFeistel. Building on the 4k-Feistel attack of above, we can further extend it to 4k-WFeistel, with key whitenings k pre and k post . Indeed, if we rewrite the slide shift equation:

T runc R (D k (x ⊕ f (R ⊕ k 0 ) ⊕ ∆, R)) = T runc R (E k (x, R))
using the whole primitive

E(•) = k post ⊕ E k (k pre ⊕ •)
, we obtain:

T runc R (D(x ⊕ k L post ⊕ f (R ⊕ k 0 ) ⊕ ∆, R ⊕ k R post )) ⊕ k R pre = T runc R (E(x ⊕ k L pre , R ⊕ k R pre )) ⊕ k R post
which we rewrite:

T runc R (D(x ⊕ δ L ⊕ f (R ⊕ k 0 ⊕ k R post ), R)) = T runc R (E(x, R ⊕ δ R )) ⊕ δ R where δ R = k R pre ⊕ k R post and δ L = k L pre ⊕ k L post ⊕ k 1 ⊕ k 3 . Now, we can use the function G : {0, 1} × {0, 1} n/2 2 → {0, 1} n/2 b, x, y → g 0 (x, y) = T runc R (D(x ⊕ f (y ⊕ (k R post ⊕ k 0 )), y) ⊕ y if b = 0, g 1 (x, y) = T runc R (E(x, y)) if b = 1.
We have g 0 (x, y) = g 1 (x ⊕ δ L , y ⊕ δ R ). However, to implement g 0 , we need to know the value (k R pos ⊕ k 0 ). Hence, we first guess the value of (k R post ⊕ k 0 ) using Grover's algorithm, and combine it with Simon's algorithm as studied in [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FX-construction[END_REF]. In time and queries 2n2 n/4 , this attack recovers δ L , δ R and (k R pos ⊕ k 0 ). Now, we can perform the analogue of the classical attack: swapping the encryption and the decryption, we obtain

k L pre ⊕ k L post and k R pre ⊕ k R post ⊕ k 0 ⊕ k 2 , which allows to obtain k 0 ⊕ k 2 , k 1 ⊕ k 3 and k pre ⊕ k post . This step costs O n2 n/4 time.
But we can also move differently δ R in the slide shift property:

T runc R (D(x ⊕ δ L ⊕ f (R ⊕ k 0 ⊕ k R pre ), R ⊕ δ R )) = T runc R (E(x, R)) ⊕ δ R .
We now interpret this as a hidden shift equation on x only and, given an arbitrary R, we can recover f (R ⊕ k 0 ⊕ k R pre ). In turn, this gives us the value k 0 ⊕ k R pre for a total of n 2 queries.

Since we have already guessed (k R pos ⊕ k 0 ), we deduce k 0 , k R pre , k R post , and k 2 from k 0 ⊕ k 2 . Only n 2 bits of key material remain unknown in the Feistel, as k 1 ⊕ k 3 has been previously obtained. We can break the complete cipher and finish the key-recovery by applying the Grover-meet-Simon attack on the FX construction of [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FX-construction[END_REF], in time O n2 n/4 . As this attack uses the sliding with a twist technique, it does not transpose well to modular additions.

A variant of 4k-WFeistel. We follow [DKS15, Section 7.4] and consider the 4k-WFeistel scheme (4K-DESX in the paper), with two whitening keys k pre and k post and four alternating keys k 0 , k 1 , k 2 , k 3 scheduled in 4m + 1 rounds as:

(k 0 , k 1 , k 2 , k 3 ) m , k 0 .
Slide pairs (P, C), (P , C ) have the properties:

P ⊕ C = k pre ⊕ k post ⊕ (k 1 ⊕ k 3 ||0) E k (P ⊕ k pre ) = E -1 k (C ⊕ k post ) ⊕ (k 1 ⊕ k 3 ||0)
Where the term ∆ = k 1 ⊕ k 3 intervenes as in the complementation slide to correct the inversion of E k . We can rewrite this as a slide shift equation holding for all input x:

E k (x) = E -1 k (x ⊕ (∆||0)) ⊕ (∆||0) =⇒ E(x ⊕ k pre ) ⊕ k post = E -1 (x ⊕ k post ⊕ (∆||0)) ⊕ k pre ⊕ (∆||0) =⇒ E(x) ⊕ x = E -1 (x ⊕ ∆ ) ⊕ x ⊕ ∆
where ∆ = k pre ⊕ k post ⊕ (∆||0), a slide shift equation holding for all x. We can retrieve ∆ in only n queries, achieving a very efficient distinguisher. Obtaining the rest of the key seems more difficult.

Enhanced Reflection Attack

The enhanced reflection attack was introduced in [DDKS15], as an improvement of the mirror slidex attack, for ciphers of the form E = E 2 • E 1 • E 0 where E 1 is an involution. It requires to find P such that E 0 (P ) is a fixpoint of E 1 . This happens with probability 2 -n/2 . In this case we get directly C = E 2 (E 0 (P )).

In the case of 4-key-alternating Feistels, in this section, multiple pairs (P, C) are needed but the fixpoints can be detected. Notice that these attacks do not use a slide shift property as above.

Enhanced reflection attack on 4k-Feistel. In [START_REF] Dinur | Reflections on slide with a twist attacks[END_REF], the authors use a reflection attack on 4k-Feistel (which they name 4k-DES), where the four alternating subkeys are denoted k 0 , k 1 , k 2 , k 3 . They prove (4.1.3, Property 3) that if (P, C) is a plaintextciphertext pair for 4m-round 4k-Feistel, such that in the encryption process of P we have

X L 2m-1 = X L 2m+1 ⊕ ∆ where ∆ = k 1 ⊕ k 3 , then P L = C L and P R = C R ⊕ Out 4m ⊕ ∆. Out 4m is the output of the internal mixing function f at the 4m-th step, so Out 4m = f (X R 4m ⊕ k 3 ) = f (C R ⊕ k 3 ).
Reflection points, that satisfy these properties, can be detected by P L = C L . Only O 2 n/2 known plaintexts are required. Given at least three of them, the adversary guesses ∆, then tries to obtain k 3 from the equation: if ∆ is good, this works and both k 1 and k 3 can be obtained.

To complete the attack, the authors note that a similar reflection property holds with the equation P R = C R to detect reflection points, and

P L = C L ⊕ Out 1 ⊕ (k 0 ⊕ k 2 ).
In a quantum setting, only O 2 n/4 superposition queries are enough, to retrieve the reflection points, using Grover search over all plaintexts P . Again, trying all values of ∆ requires O 2 n/4 work. All subkeys are recovered in time O 2 n/4 . Enhanced reflection attack on 4k-WFeistel. The attack above on 4k-Feistel, using reflection points, can be turned into an attack for 4k-WFeistel. Suppose that E(x) = k post ⊕ E (k pre ⊕ x) where E is a 4k-Feistel procedure. The adversary first has to guess k L pre ⊕ k L post . To do this, remark that reflection points for E of the form P , C turn into reflection points for E that satisfy

P L ⊕ C L = k L pre ⊕ k L post .
In this, the correct value of k L pre ⊕ k L post appears with probability 2 • 2 -n/2 , whereas all incorrect values have probability 2 -n/2 of appearance. This allows to retrieve k L pre ⊕ k L post using O n2 n/2 memory and time, the bottleneck of the attack. Indeed, reformulated in an abstract way, the problem that we are solving is:

Problem 4 (Most frequent value). Given a function f : [N 2 ] → [N ] such that any value in [N ] appears N 2 N +1 times in the images of f , except a single value y, which appears 2N 2 N +1
times (twice as much); find y.

Assume that we make c(2 n/2 + 1) queries for some c. Due to Chernoff and union bounds, given δ, γ < 1, the probability that the number of y among the queries is below than (1 -δ)2c is less than exp(-δ 2 c). The joint probability that the count of some output, different from y, exceeds (1 + γ)c, is less than 2 n/2 exp(-γ 2 c/3). We tailor c, δ and γ so that these probabilities become negligible in n, avoiding the case of a failure. If we take c = 2n, δ = 1 8 and γ = 3 4 , we find that it suffices to look for the element which appears more than 7 2 n times. As soon as the value of k L pre ⊕ k L post is obtained, the reflection points can be detected via the equation

P L ⊕ C L = k L pre ⊕ k L post
, and the second equation:

P R = C R ⊕ Out 4m ⊕ (k 1 ⊕ k 3 ) ⊕ k R pre ⊕ k R post = C R ⊕ f (C R ⊕ k 3 ) ⊕ (k 1 ⊕ k 3 ) ⊕ k R pre ⊕ k R post
For example, the adversary guesses (k

1 ⊕ k 3 ) ⊕ k R pre ⊕ k R
post and checks that two reflection points indeed yield the same value for k 3 .

A quantization of this attack would require to solve efficiently the problem of finding the value of k L pre ⊕ k L post . This seems actually difficult, and we don't know of any quantum algorithm for Problem 4 that would improve by more than a constant factor the number of queries required. The main difficulty, due to which the well-known algorithms for element distinctness [START_REF] Ambainis | Quantum algorithm for element distinctness[END_REF], collision [START_REF] Brassard | Quantum Algorithm for the Collision Problem[END_REF] or multicollision [START_REF] Hosoyamada | Quantum multicollisionfinding algorithm[END_REF] cannot be applied, seems to be that the most frequent value is not known beforehand. We leave this as an open question.

On Quantum Attacks Exploiting Cycle Finding

A generic framework of cycle-based slide attacks is presented in [BOBDK18, Section 4.1]. The authors suggest that it could be accelerated in a similar way as the slide attacks from [START_REF] Kaplan | Breaking Symmetric Cryptosystems Using Quantum Period Finding[END_REF], expecting for instance exponential speedups. In this section we find much smaller improvements than expected, as the attack do not seem to have a slide-shift structure. We are nevertheless able to propose some improved-over-classical quantum associated attacks.

Definition of a Cycle Slide Attack

We suppose that E k = f k for some function f k , which happens to be immune to simpler slide attacks such as those presented above for 1k-, 2k-and 4k-Feistel schemes. Consider a message P and the cycle built from P using E k : P, E k (P ), E 2 k (P ), . . . Let m 2 be the period of this cycle. Let also m 1 be the period of the f k -cycle, that is, the smallest integer such that f m1 k (P ) = P . Then one has m 2 = m 1 /gcd(m 1 , ). Moreover, suppose that gcd(m 1 , ) = 1, then m 1 = m 2 = m. This condition cannot be checked directly by the attacker, since he does not have access to f k . By Bezout's theorem, there exists d 1 , d 2 such that d 1 m -d 2 = 1. This gives:

f d1m-d2 +1 k (P ) = P f d1m+1 k = f d2 k (P ) = E d2 k (P ) f k (P ) = E d2 k (P )
Hence (P, E d2 k (P )) is a slide pair. Moreover, (E t k (P ), E d2+t k (P )) is one for every t. This gives a certain number of slide pairs "for free", depending on the length of the cycle. Once they have been obtained, we can use them to perform an attack on f k and try to recover the key material.

General cycle size. We assume that E k is a random permutation. In that case, the i-th largest cycle has size e -i+1 (1 -1/e) 2 n (on average), the largest having size (1 -1/e) 2 n . In particular, on average, half of the points lie on the largest cycle. Finding a cycle of E k then requires c2 n chosen plaintext queries for some c < 1, which is a little less than the entire codebook.

The main interest is the time complexity: suppose that the attack on f k needs time O(t), then the total time complexity is O(t + 2 n ) and not O(t2 n ) as would require a standard slide attack (see [BOBDK18, Section 4.1]).

Combining cycles. It is important to note that the probability of success (i.e, m 1 is prime with ) is strictly smaller than one, exactly φ( )/ where φ is Euler's totient function. The only way to check that the slide pairs obtained were good is to try to attack f k . Hence, it may be difficult to combine (when needed) the data obtained from multiple cycles.

In particular, if one is not able to tell if a given cycle is a good one (i.e, m 1 is prime with ), the complexity can increase dramatically, since we would require all cycles to be good at the same time: it happens only with probability (φ( )/ )

t if there are t of them.

Classical Examples and Applications. The cycle slide attack is applied in [START_REF] Bar-On | Efficient Slide Attacks[END_REF] against a palindromic Feistel scheme, where the keys are scheduled as: In [BOBDK18, section 5], the authors present attacks on GOST. First:

k 0 , k 1 . . . k r , k r , k r-1 , . . . k 0 , k 0 , k 1 , . . .
• A distinguishing attack on 8-round GOST with unknown S-boxes, using 2 36 known plaintexts and time (it relies on differentials);

• A key-recovery attack on 8-round GOST with unknown S-boxes, based on a differential attack, using 2 36.5 known plaintexts, data and time.

This allows to attack the 24 first rounds of GOST, that correspond to f 3 k where f k is an 8-round GOST, efficiently using the cycle-based slide attack. This requires 2 63 chosen plaintext and time.

The authors also attack the palindromic full GOST: having a palindromic key, it is in fact f 4 k where f k is a palindromic Feistel scheme. Hence the cycle-based attack works more efficiently (the cycles have small size). The distinguishing attack allows to retrieve the good slide pairs, and once there are enough, the key-recovery attack is launched on f k . The total needs 2 40 chosen plaintexts, memory and time.

Quantization of a Cycle-based Slide Attack

At the end of [BOBDK18, Section 4.1], the authors suggest that a quantum period-finding algorithm could be applied to cycle-based slide attacks. To the best of our knowledge, this seems not possible. Indeed, given a point P , the period that is of interest here is the one of the function:

G : d ∈ Z → E d k (P ) If the function G(d) = E d
k (P ) was implemented using a quantum circuit, we could indeed use Shor's period-finding algorithm to retrieve the cycle length. But this would require to call E d k in superposition over d, which seems highly difficult. The encryption oracle E k is actually only accessed through queries x → E k (x), in superposition over x. To compute E d k for some d, one still needs to perform d successive calls to E k . A superposition oracle for G is indeed constructible, but it would have the same time complexity as the classical one (the highest value of d in the input). On the contrary, Shor's algorithm uses an oracle for f (r) = a r mod n, and fast exponentiation allows to compute it efficiently. Quantization. It is however possible, using Grover search, to improve on the classical complexity of some cycle slide attacks. Finding a point that lies on a cycle of length smaller than d, if there are k such points, can be done in O 2 n /k calls to a testing subprocedure G, implemented using a quantum algorithm, that computes: G(P ) = 1 ⇐⇒ ∃u ≤ d, E u k (P ) = P . As in the classical case, such a procedure will make successive calls to E k , in total d of them, running in overall time O(d) (with d superposition queries to E k ).

In a random permutation, there are on average 1/d cycles of length d; and d points of period less than or equal to d. So using Grover's algorithm, one can find a superposition of points that lie on a cycle of length less than d in O √ d2 n calls to E k . In the classical case, we do not have much choice: the cycle slide pairs found will fall on a large cycle, with high probability. On the contrary, in the quantum setting, we can specifically look for points lying on a short cycle. Surprisingly, finding fixed points, or points on very short cycles, costs less than finding points on bigger cycles, due to the cost of iterating E k . But the smallest the cycle, the least slide pairs we can get from it.

If the attack on f k needs time O(t) and O(s) slide pairs, we conclude that the quantized version of cycle-based sliding costs O t + √ s2 n quantum and classical computations alike. When s becomes large, we arrive at O(t + 2 n ) and there is no improvement w.r.t the classical setting.

To summarize, cycle-based slide attacks seem to be eligible to an interesting quantum speedup when the cipher E k = f r k does not enjoy a slide-shift property as before, but has a sufficiently weak round function f k , so that a small number of slide pairs suffice to get the subkey material.

Example. For example, this would speed up (but not much) the attack on 24-round GOST of [START_REF] Bar-On | Efficient Slide Attacks[END_REF], since we can tailor the cycle length to our needs.

The attack on f k requires 2 36.5 slide pairs. Using Grover search, one can find a cycle of this length (or little more) in around √ 2 36.5 2 64 ) time and queries. This diminishes the amount of work towards around 2 50 superposition queries instead of 2 64 classical.

Quantum Cycle-based Slide Attacks

We are inspired by [START_REF] Bar-On | Efficient Slide Attacks[END_REF] and the attacks against the SA construction and weak variants of AES. In the classical as in the quantum versions, most of the computation time required is due to finding the actual slide pairs (via the cycle).

Two Keys and Two Permutations. Consider a cipher with alternating keys k 0 , k 1 , xored or modularly added, and two permutations Π 1 , Π 2 . In the case of a SPN, Π 1 = Π 2 = Π are the same.

P k

0 Π 1 k 1 Π 2 k 0 Π 1 . . . k 1 C P k 0 Π 1 . . . k 1 Π 2 k 0 Π 1 k 1 C
Figure 10: Slide attack against a key-and permutation-alternating cipher This scheme resists to the basic slide attack, but we can write

E k • Π 2 = f r k (x) where f k (x) = Π 2 (k 1 ⊕ Π 1 (k 0 ⊕ x))
, and apply the cycle-finding technique. In O 2 n/2 superposition queries to E k and computations, we can recover a small number of slide pairs, say two, from small cycles of E k • Π 2 . Recall that n is the block size here; the key length is 2n. Therefore we obtain two equations:

y = Π 2 (k 1 ⊕ Π 1 (k 0 ⊕ x)) y = Π 2 (k 1 ⊕ Π 1 (k 0 ⊕ x ))
Since the permutations can be inverted, we find:

Π -1 2 (y) ⊕ Π -1 2 (y ) = Π 1 (k 0 ⊕ x) ⊕ Π 1 (k 0 ⊕ x )
Solving this equation on k 0 , if Π 1 has no specific property, can be done in O 2 n/2 time using Grover's algorithm, the same complexity as the first stage. This improves on the Grover-meets-Simon technique of [START_REF] Leander | Grover Meets Simon -Quantumly Attacking the FX-construction[END_REF], which would perform in O n2 n/2 queries and more time (the Grover oracle requires to solve linear systems in superposition).

Attacking 3k-SPN. Cycle-finding can further be applied on a 3k-SPN construction, where there is a unique permutation Π = A • S, with A a linear layer and S a non-linear layer of S-Boxes. Still using O 2 n/2 queries, we now write the slide equations as:

y = Π(k 2 ⊕ Π(k 1 ⊕ Π(k 0 ⊕ x))) y = Π(k 2 ⊕ Π(k 1 ⊕ Π(k 0 ⊕ x ))) =⇒ Π -1 (y) ⊕ Π -1 (y ) = Π(k 1 ⊕ Π(k 0 ⊕ x)) ⊕ Π(k 1 ⊕ Π(k 0 ⊕ x ))
To solve efficiently this equation in k 0 and k , we first guess k 0 using Grover's algorithm. The equation on k 1 becomes:

A -1 (Π -1 (y) ⊕ Π -1 (y )) = S(k 1 ⊕ Π(k 0 ⊕ x)) ⊕ S(k 1 ⊕ Π(k 0 ⊕ x ))
Furthermore, we may consider each S-Box separately and solve the equation on k 1 , S-Box by S-Box. if s is the bit size of an S-Box, the final complexity of this attack is O 2 (n+s)/2 computations, with O 2 n/2 oracle queries.

Attacking 4k-AES. In the case of AES, we can add one more round. Suppose that, by the cycle, we obtain four equations of the form:

A -1 (Π -1 (y) ⊕ Π -1 (y )) = S(k 2 ⊕ Π(k 1 ⊕ Π(k 0 ⊕ x))) ⊕ S(k 2 ⊕ Π(k 1 ⊕ Π(k 0 ⊕ x )))
We use the fact that a column of Π(x) does only depend on a diagonal of x. Since we need only to guess k 2 byte per byte, we need also only to guess k 1 column by column, assuming that the full k 0 is guessed. The cycle step has a complexity of approximately 2 64 queries (usually, queries to an AES-like black-box should cost a non-negligible quantum time).

The equation step has a complexity of approximately 2 64 × 2 16 (2 4 × 4) × 4 2 84 calls to Π: each guess of k 0 is tested by searching the good k 1 (column by column) and k 2 (byte per byte).

Against 3k-Feistel. A Feistel scheme with a mixing function f , alternating three keys k 0 , k 1 , k 2 , xored or modularly added, is immune to the complementation slide and sliding with a twist techniques. It seems difficult to write a slide shift property for this cipher. Let us write the round function g as:

L, R → R + f (k 1 + L + f (k 0 + R)), L + f (k 0 + R) + f (k 2 + f (k 1 + L + f (k 0 + R)))
and suppose that we can invert f . In O 2 n/2 queries, we can find two slide equations g(L, R) = L , R , which imply f (k 1 + L + f (k 0 + R)) = L -R. Regardless of the function f , we can invert it in time O 2 n/4 using Grover and recover two equations k 1 + L + f (k 0 + R) = X. We take the difference (or sum if we replace + by ⊕) to eliminate k 1 , and we can solve the remaining equation on k 0 using Grover in O 2 n/4 time. Once this is done, k 1 can be found via the relation

k 1 = f -1 (L -R) -L -f (k 0 + R) and k 2 via L + f (k 0 + R) + f (k 2 + f (k 1 + L + f (k 0 + R))) = R .
The whole attack requires O 2 n/2 time and queries due to the cycle finding, with any function f . Against 4k-Feistel. If we append one more round key k 3 , the round function g becomes:

L, R → L + f (k 0 + R) + f (k 2 + f (k 1 + L + f (k 0 + R))), R + f (k 1 + L + f (k 0 + R)) + f (k 3 + L + f (k 0 + R) + f (k 2 + f (k 1 + L + f (k 0 + R))))
Again, we can find some slide equations g(L, R) = L , R from a cycle in O 2 n/2 queries. We guess the subkey k 0 . For each guess, we can rewrite the equations as if there were only 3 subkeys, and solve them in time O 2 n/4 using multiple Grover instances, as seen above, regardless of the properties of f . The whole attack requires O 2 n/2 time and queries, the two steps (cycle finding and solving equations) are now balanced. The time complexity is greater than the other 4k-Feistel attacks seen above, but there is no restriction on the function f and the operations used; furthermore, we only use encryption queries, not decryption queries (which is the case of the twist).

Conclusion

In this paper, we presented various quantum slide attacks, which target the two main families of block ciphers: SPN and Feistels. The concrete cost of these attacks vastly depends on the structure, that is, is there a slide-shift property or not, and in that case, what is the group law used, whether it is XOR or modular addition (or parallel modular additions); dependencies which do not occur classically. However, for usual parameters in symmetric schemes, slide-shift properties remain extremely competitive when compared to exhaustive search.

We also showed that the relevant security notion for the inner function in a quantum slide-shift attack is its quantum security, which demonstrates a very powerful chaining property of some quantum attacks. We used this chaining property to attack 4-round self-similar Feistel ciphers, at a quadratic cost.

We provided a detailed analysis of cycle-based slide attacks, thought to be quantumly very efficient, showing a smaller than expected improvement with respect to the classical attacks.

Classical slide attacks have shown the importance of a good key schedule, as self-similarity in a cipher allows for powerful breaks. In the quantum setting, these results seem to put even more weight on this design principle, as the attacks become much more efficient. Furthermore, as their cost is very low, a possible future direction for improvement would be to consider new attack patterns, intrinsically infeasible in a classical setting, with stronger functions relating the slide pairs. Also, using modular additions instead of bitwise additions as suggested in [START_REF] Alagic | Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts[END_REF] does not seem to counter the attacks, as already pointed out in [BNP]. While the quantum complexity of an attack goes from polynomial to subexponential, it would require unrealistic state sizes to assert enough security. Protecting against slide attacks, classical and quantum, using e.g a good key schedule, seems a much more desirable option.

Figure 1 :

 1 Figure 1: Illustration of the basic slide property

Figure 3 :

 3 Figure 3: Slide attack on the key-alternating cipher with modular additions

Figure 5 :

 5 Figure 5: Representation of the complementation slide attack

Figure 7 :

 7 Figure 7: Slide attack on a generic one-round self-similar Feistel

Figure 8 :

 8 Figure 8: Example of a vulnerable Feistel

Figure 9 :

 9 Figure 9: Complementation and twist combined on a 4k-Feistel scheme

Table 1 :

 1 Quantum slide attacks

	Cipher		Attack details	Queries	Decryption	Source
							oracle
	1k-Feistel (XOR) 1k-Feistel (additions) 1k-Feistel (any)	Basic slide Basic slide Composed slide	n/2 2 1.2 √ n/2 to 2 2.4 n	√	n	[DDW18] Section 3.2 Section 4
	2k-Feistel (XOR)	Complementation	n2 n/4	Section 3.3
	2k-Feistel (XOR)	Sliding with a twist n/2		Yes	[DDW18]
	2k-Feistel (XOR) 2k-Feistel (additions) 2k-Feistel (additions)	Composed slide Complementation Composed slide	n 2 1.2 2 1.8	√ √	n+n/4 n	Section 4 Section 3.3 Section 4
	3k-Feistel (any)	Cycle finding	2 n/2		Section 6.3
	4k-Feistel (XOR)	Complementation,	4n 2			Yes	Section 5
			sliding with a twist
	4k-Feistel (XOR)	Enhanced reflection 2 n/4		Section 5.3
	4k-Feistel (any)	Cycle finding	2 n/2		Section 6.3
	4k-Whitened Feistel	Complementation,	n 2 2 n/4	Yes	Section 5
	(DESX) (XOR)	sliding with a twist	n2 n/4 (Distinguish)
	2k-Whitened Feistel	Mirror slidex	n2 n/4	Section 5
	(DESX)
	4k-Whitened Feistel	Mirror slidex	n (Distinguish)	Yes	Section 5
	(DESX)	(variant)
	(XOR)
	1k-SPN (XOR) 1k-SPN (additions)	Basic slide Basic slide	n 2 1.8	√	n	[KLLN16a] Section 3.1
	2k-SPN (any)		Grover-meet-Simon n2 n/2	[LM17]
	2k-SPN (any)		Cycle finding	2 n/2		Section 6.3

Table 2 :

 2 Summary of the slide attack costs, n is the block size.

	Branch, Key add. Round function quantum query cost	Remark
	⊕, any	Weak	n/2
	⊕, ⊕	f (x ⊕ k)	n/2
	⊕, ⊕ ⊕, +	f k (x) f k (x)	n 2 /2 n2 1.2 √	n	Simon calls purely quantum Simon Kuper. calls purely quantum Simon
	+, any	Weak	2 1.2

  The function f k is a Feistel scheme with 2r keys scheduled as k 0 , k 1 . . . k r , k r , k r-1 , . . . k 0 . In that case, the average cycle length of a plaintext P is of order O 2 n/2 , limiting considerably the cost of the attack and making it possible. But since the cycle is of length O 2 n/2 , it gives only O 2 n/2 slide pairs: the distinguishing attack on f k required should need only O 2 n/2 plaintext-ciphertext pairs.

Table 3 :

 3 Classical slide attacks on specific constructions

	Cipher	at-	Attack details	Encryption	Time Decryption	Memory Source
	tacked				queries	queries
	2K-DES (64-			2 32	2 50	2 32	[BW99], Sec-
	bit blocks)							tion 4
	TREYFER			2 32	2 40	2 32	[BW99], Sec-
	(64-bit blocks)						tion 5
	DESX (64-bit	Sliding with a	2 32,5	2 87,5	2 32,5	[BW00], Sec-
	blocks)		twist,	known-				tion 4
			plaintext only
	GOST	(20	Sliding with a	2 33	2 70	2 65	[BW00], Sec-
	rounds)		twist					tion 5
	2K-AES (128-			2 69	2 69	2 69	[BOBDK18],
	bit blocks)							Section 2.3
	3K-AES (128-			2 81	2 81	2 81	[BOBDK18],
	bit blocks)							Section 2.3
	24-round		Slide and trun-	2 63	2 63	2 63	[BOBDK18],
	GOST with	cated differential				Section 5.3
	unknown		on 8 rounds
	S-Boxes
	Palindromic			2 40	2 40	2 40	[BOBDK18],
	GOST with						Section 5.4
	unknown
	S-Boxes

A Summary of Classical Slide Attacks

We provide in Tables 3 and4 a (certainly non exhaustive) list of classical slide attacks that we studied for quantum improvements. They are not ordered by efficiency. We refer to the corresponding source for a presentation of the attack principle. Table 3 contains attacks on specific constructions, while Table 4 contains attacks on generic constructions (n is the block size of the cipher attacked; for a Feistel network, round keys have size n/2). Note that memory usage and required access to a decryption device play a role in the usefulness of these slide attacks.


Rachel Freire
email: rachel@rachelfreire.com

Paul Strohmeier
email: p.strohmeier@di.ku.dk

Cedric Honnet
email: cedric@honnet.eu

Jarrod Knibbe
email: jarrod@di.ku.dk

Sophia Brueckner
email: sbrueckn@umich.edu

Designing eTextiles for the Body: Shape, Volume & Motion

Keywords: eTextile, tailoring, fabric, sewing, craft, wearables ACM Classification Human-centered computing~Human computer interaction (HCI), Hardware~Sensors and actuators

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

Introduction

The academic interest in textiles as a design material is gradually increasing. This can be seen from the number of publications at TEI and less specialized venues, such as CHI (Figure 1). With some exceptions (e.g.: [START_REF] Berzowska | Memory rich clothing: second skins that communicate physical memory[END_REF]3]) this work appears driven by computer-scientists and designers who have little experience or training in working with textiles. The result are designs such as the popular multiplexed sensor matrix (e.g.: [START_REF] Donneaud | Designing a Multi-Touch eTextile for Music Performances[END_REF]4,5]). This is an obvious design from a computer-science perspective, but rather counter-intuitive from a fashion or tailoring perspective: individual textile elements of garments have complex shapes which are rarely square.

Such a sensor and its corresponding schematic can be seen in Figure 2. The organization of the schematic and the organization of the textile are almost identical. This is not required by the technology and, looking at patterns used for creating garments (see figure 4), possibly not desirable.

We believe that technology should adapt to the shape of the body and that compelling wearable technology is not a plastic gadget attached to clothing, but clothing which is technology. To achieve this, we suggest that considerations regarding the body's shape and movements must be made much earlier in the design process than is current practice.

We are hosting this studio to improve our own understanding of how to design fashionable and functional eTextile garments. While we share the workflows and methods which we have developed for ourselves, we hope to learn from the diverse background of the other participants of the studio.

While the workshop will be focused on fabrication skills, we will discuss potential applications for the near future as well as speculate on the long-term future of clothing and wearable technology.

Studio Proposal

This studio has a two-part structure, a masterclass designed by us and a collaborative prototyping session in which the studio hosts and the participants together apply the methods demonstrated in the masterclass.

Masterclass

We will start out with a master-class-crash-course on fashion-design and functional materials lead by Rachel Freire. Rachel will introduce the group to her method of using heat-bonding to integrate conductive fabric traces in her designs (Figure 3). She will discuss and share her approach to creating patterns (Figure 4) which eventually transform from two dimensional layouts into three dimensional garments (Figure 5 & 6).

Collaborative Prototyping

After the masterclass, the studio will split into smaller interests groups. These groups will use the rest of the day to explore ideas through physical prototyping.

All studio hosts have extensive experience in working with textiles. They each contribute unique perspectives and will share their experience with embedded development, sensor design, Sci-Fi prototyping, EMSstimulation, haptic feedback and connected devices in the context of eTextiles. We hope that participants will diversify this further. Together, hosts and participants will create subgroups and spend an afternoon prototyping wearable concepts.

We will provide a selection of fabrics, mannequins and tailoring tools as well as basic electronics to facilitate the prototyping of novel eTextile technologies.

Participant Profile

To start prototyping as fast as possible, we expect all participants to have prepared some concepts or ideas that they would like to explore. We will also only bring very basic electronic prototyping supplies and assume all participants will bring their prototyping platform of choice and any more advanced tools, materials or devices they might want to use.

We are looking for participants with an interest in eTextiles and basic electronic hardware or software prototyping skills. We assume that participants will have basic electronic prototyping skills. We do not expect participants to have prior experience or skills working with fabric, though if they do that is a plus.

Studio Topics to be Covered

We will discuss methods for designing eTextiles that both conform and contrast to the shape and motion of the body (see Figure 5 &6). We will introduce participants to functional and non-functional materials which are used for designing eTextiles. We will present basic methods for designing patterns as well as measuring and fitting garments. We will discuss approaches for sensing in eTextiles and demonstrate manufacturing techniques based on heat-bonding as a quick and accessible way to prototype and iterate.

Studio Goals

We pursue goals on different levels with this studio. First off, we hope to help people expand their knowledge of eTextile design. In doing so we hope to also improve our own understanding of the domain.

Through prototyping we plan to achieve a tangible outcome consisting of a series of eTextile garments.

Our intent is for such a tangible outcome to support future collaboration between participants. The workshop will foster ideation on current and near future applications of eTextiles as well as their future role in transhumanism and our cyborg evolution.

Figure 2 -

 2 Figure 2 -Number of papers at CHI that refer to 'eTextiles', 'e-textiles' or 'electronic textiles' in their text (orange) and number of papers at TEI that refer to textiles or fabric in their abstract (blue). (Tool for full-text search of the CHI proceedings is still under development and not yet published. CHI data for 2017 not yet available. TEI data based on manual search. Graph makes no claim to completeness).

Figure 1 -

 1 Figure 1 -Pressure-Matrix Sensor by Donneaud et al. [2] and corresponding schematic.

Figure 3 -

 3 Figure 3 -Traces are added to fabric by layering heat bonding method

Acknowledgements

This work was supported by the European Research Council, grant no. 648785, by Labex SMART (ANR-11-LABX-65) and by French state funds under reference ANR-11-IDEX-0004-02. The authors would like to thank Maurin Donneaud from DataPaulette.

International Conference on New Interfaces for Musical

Expression -NIME '17