# On Quantum Slide Attacks

Xavier Bonnetain, María Naya-Plasencia, André Schrottenloher

► To cite this version:

Xavier Bonnetain, María Naya-Plasencia, André Schrottenloher. On Quantum Slide Attacks. SAC 2019 - Selected Areas in Cryptography, Aug 2019, Waterloo, Canada. pp.492-519, 10.1007/978-3-030-38471-5_20. hal-04321743

HAL Id: hal-04321743

https://inria.hal.science/hal-04321743v1

Submitted on 4 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à 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.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# On Quantum Slide Attacks

Xavier Bonnetain¹,², María Naya-Plasencia² and André Schrottenloher²

¹ Sorbonne Université, Collège Doctoral, F-75005 Paris, France

² Inria de Paris, France

**Abstract.** 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. First, we are able to quantize classical advanced slide attacks on Feistel networks. With modular additions inside branch or key-addition operations, these attacks reach up to two round self-similarity. With only XOR operations, they reach up to four rounds self-similarity, with a cost at most quadratic in the block size.

Moreover, some of these variants combined with whitening keys (FX construction) can be successfully attacked. We show how these results relate to general quantization principles of classical techniques including *sliding with a twist*, *complementation slide* and *mirror slidex*.

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.

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

# 1 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 [Kap14], quantum linear and differential attacks [KLLN16b], an analysis of the FX construct against quantum adversaries [LM17], improved algorithms for collisions or multicollisions [CNPS17, HSX17] and [KM10, KM12, Bon18] 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 [KLLN16a], 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 [Sim94] 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 [AR17] some ideas for countering these attacks were proposed. The most interesting one, using modular addition, has recently been studied in detail in [BNP18]. This paper provides detailed cost estimates of attacks built over Kuperberg's algorithm [Kup05], 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 [DDW18], 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 [DW17], the three round distinguisher of [KM10] is exploited to reduce by three the number of keys to search for in a Feistel cipher with independent keys. In [HS17], some meet-in-the-middle attacks on Feistel constructions are proposed, in a more restricted model, and the same observation as [DW17] is presented.

**Motivation and Summary of our results.** In this paper we propose the quantized version of several advanced slide attacks proposed in [BW00], 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 [DDKS15], and quantum slide attacks exploiting cycle finding, as was proposed in [BOBDK18]. 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 classical advanced slide attacks. Section 3 proposes new quantum advanced slide attacks, considering XOR and modular additions with respect to the ones from [BW00] and [DKS15], 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.

## 2 Preliminaries

In this section we provide a brief introduction to classical slide attacks and advanced slide attacks from the literature. A summary of the classical attacks we considered can be found in the Appendix.
<table><caption>**Table 1:** Quantum slide attacks</caption><thead><tr><th>Cipher</th><th>Attack details</th><th>Queries</th><th>Decryption oracle</th><th>Source</th></tr></thead><tbody><tr><td>1k-Feistel (XOR)</td><td>Basic slide</td><td>n/2</td><td></td><td>[DDW18]</td></tr><tr><td>1k-Feistel (additions)</td><td>Basic slide</td><td>2<sup>1.2√n</sup></td><td></td><td>Section 3.2</td></tr><tr><td>1k-Feistel (any)</td><td>Composed slide</td><td>n/2 to 2<sup>2.4√n</sup></td><td></td><td>Section 4</td></tr><tr><td>2k-Feistel (XOR)</td><td>Complementation</td><td>n2<sup>n/4</sup></td><td></td><td>Section 3.3</td></tr><tr><td>2k-Feistel (XOR)</td><td>Sliding with a twist</td><td>n/2</td><td>Yes</td><td>[DDW18]</td></tr><tr><td>2k-Feistel (XOR)</td><td>Composed slide</td><td>n</td><td></td><td>Section 4</td></tr><tr><td>2k-Feistel (additions)</td><td>Complementation</td><td>2<sup>1.2√n+n/4</sup></td><td></td><td>Section 3.3</td></tr><tr><td>2k-Feistel (additions)</td><td>Composed slide</td><td>2<sup>1.78√n</sup></td><td></td><td>Section 4</td></tr><tr><td>3k-Feistel (any)</td><td>Cycle finding</td><td>2<sup>n/2</sup></td><td></td><td>Section 6.3</td></tr><tr><td>4k-Feistel (XOR)</td><td>Complementation, sliding with a twist</td><td>4n<sup>2</sup></td><td>Yes</td><td>Section 5</td></tr><tr><td>4k-Feistel (any)</td><td>Cycle finding</td><td>2<sup>n/2</sup></td><td></td><td>Section 6.4</td></tr><tr><td>4k-Whitened Feistel (DESX)</td><td>Complementation, sliding with a twist</td><td>n2<sup>n/2</sup></td><td>Yes</td><td>Section 5</td></tr><tr><td>2k-Whitened Feistel (DESX)</td><td>Mirror slidex</td><td>n2<sup>n/4</sup> (Distinguish)</td><td>Yes</td><td>Section 3.5</td></tr><tr><td>4k-Whitened Feistel (DESX) (variant)</td><td>Mirror slidex</td><td>n (Distinguish)</td><td>Yes</td><td>Section 3.5</td></tr><tr><td>1k-SPN (XOR)</td><td>Basic slide</td><td>n</td><td></td><td>[KLLN16a]</td></tr><tr><td>1k-SPN (additions)</td><td>Basic slide</td><td>2<sup>1.78√n</sup></td><td></td><td>Section 3.1</td></tr><tr><td>2k-SPN (any)</td><td>Cycle finding</td><td>2<sup>n/2</sup></td><td></td><td>Section 6.3</td></tr><tr><td>3k-SPN (any)</td><td>Cycle finding</td><td>2<sup>n/2</sup></td><td></td><td>Section 6.3</td></tr></tbody></table>

We next present the considered quantum adversary model, and some quantum algorithms used throughout the paper. A description of the results from [KLLN16a] regarding quantum slide attacks using Simon's algorithm is also given.

## 2.1 Classical Slide Attacks

Slide attacks were introduced in [BW99]. 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 \to \{0, 1\}^n$, constructed from a round function $F(x, k) : \{0, 1\}^n \times \{0, 1\}^m \to \{0, 1\}^n$ applied a certain number of times. There are $r$ rounds and they use round subkeys $k_1, \dots, k_r$ derived from the master key $K$ of the cipher.

**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, \dots, k_r = k$; i.e the scheme is one-round self-similar. From the structure of the cipher, which is $r$ similar
<figure><img src="image_2.png" /><figcaption>**Figure 1:** Illustration of the basic slide property</figcaption></figure>

applications of the same permutation $x \mapsto F(x, k)$, we may write a simple equality, the slide property:

$$E_K(F(x, k)) = F(E_K(x), k) \qquad (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 \oplus \Pi(x)$, a slide pair $(P_0, C_0), (P_1, C_1)$ satisfies $F(P_0, k) = P_1$ i.e $P_1 = k \oplus \Pi(P_0)$, which is equivalent to $C_1 = k \oplus \Pi(C_0)$. Hence it suffices to check if $P_1 \oplus C_1 = \Pi(P_0) \oplus \Pi(C_0)$.

<figure><img src="image_3.png" /><figcaption>**Figure 2:** Illustration of a slide attack against an example of weak round function (subkey xorings)</figcaption></figure>

Slide attacks have been successfully applied to the TREYFER cipher, variants of DES and Blowfish and Feistel constructions [BW99]. We do not study stream ciphers in this paper and focus on block ciphers.

## 2.2 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) \circ \dots \circ 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:

$$ WFeistel: \left( \begin{array}{c} \{0,1\}^k \\ k \\ \end{array} \right) \times \left( \begin{array}{c} \{0,1\}^n \}^3 \\ k_x, k_y, m \\ \end{array} \right) \rightarrow \left( \begin{array}{c} \{0,1\}^n \\ k_y \oplus Feistel(k, m \oplus k_x) \\ \end{array} \right). $$

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.

## 2.3 Advanced Classical Slide Attacks

**Slidex.** The slidex attack was introduced in [DKS15] and applied to variants of Even-Mansour, DES, XDES. It allows to meet the bound on time for the security of Even-Mansour. The authors noticed already that this attack works even if xor is used for one of the key operations and modular addition for the other.

**Mirror slidex.** The mirror slidex attack [DKS15] applies to any cipher that can be decomposed as:

$$ E = E_2 \circ E_1 \circ E_0 $$

where $E_1$ is an involution ($E_1 \circ E_1 = \text{Id}$).

In that case, the slide pair $(P_0, C_0), (P_1, C_1)$ that we are looking for must satisfy the following property:

$$ E_0(P_0) = E_2^{-1}(C_1) \qquad (2) $$

which in turn implies, after computation, that $E_2^{-1}(C_0) = E_0(P_1)$.

One needs to compute $O(2^{n/2})$ plaintext-ciphertext pairs and to search for pairs such that:

$$ C_1 = E_2(E_0(P_0)) $$

$$ C_0 = E_2(E_0(P_1)) $$

The mirror slidex attack is in fact a generalization of the sliding with a twist technique (the latter being a particular case where $E_2 = \text{Id}$).

**Enhanced reflection attack.** In [DDKS15], an attack is presented which requires to find $P$ such that $E_0(P)$ is a fixpoint of $E_1$. When $E_1$ is an involution, this happens with probability $2^{-n/2}$. This attack aims at improving the mirror slidex attack.

In this case we get directly:

$$ C = E_2(E_0(P)) . \qquad (3) $$

If only one equation suffices to recover the secret key, one may simply try to solve Equation (3) for $2^{n/2}$ plaintexts $P$. When two equations are needed but they have a very simple form (e.g we search for $P_0 \oplus C_0 = P_1 \oplus C_1$), one may compute all possible values and search for collisions, which offers also a quadratic speedup w.r.t the naive examination of all pairs.
**Enhanced reflection attack on 4k-Feistel.** In [DDKS15], the authors use a reflection attack on 4k-Feistel (which they name 4k-DES), where the four alternating subkeys are denoted $k_1, k_2, k_3, k_4$. They prove (4.1.3, Property 3) that if $(P, C)$ is a plaintext-ciphertext pair for $4m$-round 4k-Feistel, such that in the encryption process of $P$ we have $X_{2m-1}^L = X_{2m+1}^L \oplus \Delta$ where $\Delta = k_2 \oplus k_4$, then $P^L = C^L$ and $P^R = C^R \oplus Out_{4m} \oplus \Delta$.

$Out_{4m}$ is the output of the internal mixing function $f$ at the $4m$-th step, so $Out_{4m} = f(X_{4m}^R \oplus k_4) = f(C^R \oplus k_4)$.

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 $\Delta$, then tries to obtain $k_4$ from the equation: if $\Delta$ is good, this works and both $k_2$ and $k_4$ 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 \oplus Out_1 \oplus (k_1 \oplus k_3)$.

While a combination of complementation slide and sliding with a twist can also successfully break 4k-Feistel, the reflection attack benefits from an improved memory complexity.

**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} \oplus E'(k_{pre} \oplus x)$ where $E'$ is a 4k-Feistel procedure. The adversary first has to guess $k_{pre}^L \oplus k_{post}^L$. To do this, remark that reflection points for $E'$ of the form $P', C'$ turn into reflection points for $E$ that satisfy $P^L \oplus C^L = k_{pre}^L \oplus k_{post}^L$.

In this, the correct value of $k_{pre}^L \oplus k_{post}^L$ appears with probability $2 \cdot 2^{-n/2}$, whereas all incorrect values have probability $2^{-n/2}$ of appearance. This allows to retrieve $k_{pre}^L \oplus k_{post}^L$ using $O(n2^{n/2})$ memory and time, the bottleneck of the attack.

As soon as it is done, the reflection points can be detected via the equation $P^L \oplus C^L = k_{pre}^L \oplus k_{post}^L$, and the second equation:

$$ 
\begin{aligned}
P^R &= C^R \oplus Out_{4m} \oplus (k_2 \oplus k_4) \oplus k_{pre}^R \oplus k_{post}^R \\
&= C^R \oplus f(C^R \oplus k_4) \oplus (k_2 \oplus k_4) \oplus k_{pre}^R \oplus k_{post}^R
\end{aligned}
$$

For example, the adversary guesses $(k_2 \oplus k_4) \oplus k_{pre}^R \oplus k_{post}^R$ and checks that two reflection points indeed yield the same value for $k_4$.

## 2.4 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 [DFNS13, BZ13, Zha12]. 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 [GHS16] and [Gag17].

## 2.5 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(\cdot, 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, which is a stronger property 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 rewriting the slide property to the form of 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, 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, and for modular additions, the subexponential-time Kuperberg's quantum algorithm, which are described below.

Quantum Slide Attacks were first introduced in [KLLN16a], where the authors show that such rewriting is doable for Figure 2. Their slide-shift property is the equality, for all $x$:

$$ \Pi(E_K(x)) \oplus K = E_K(\Pi(x \oplus K)) . $$

Hence $g_0(x) = g_1(x \oplus K)$ where $g_0(x) = \Pi(E_K(x))$ and $g_1(x) = E_K(\Pi(x)) \oplus x$, and Simon's algorithm can be applied.

### 2.5.1 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, being an $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 \mapsto s(y)$. The function $s$ is often assumed to be weak, that is, the secrets we seek can be found with a few input-output pairs.

In our case, 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. This means that the relevant security notion for $s$ is its quantum security, and not only the classical one. This is a case of quantum algorithm composition, as the Grover-meets-Simon technique [LM17]. Examples of compositions are presented in Section 4 and 5.

## 2.6 Quantum Hidden Shift Algorithms

### 2.6.1 Simon's Algorithm

Simon's algorithm [Sim94] is a quantum algorithm designed to solve the following problem ($\oplus$ denotes the bitwise addition):

**Problem 1 (Simon's Problem).** Let $G: \{0, 1\}^n \to \{0, 1\}^n$. Given the promise that there exists $s \in \{0, 1\}^n$ such that for any $(x, y) \in \{0, 1\}^n$, $[G(x) = G(y)] \Leftrightarrow [x \oplus y \in \{0^n, s\}]$, find $s$.

This problem is a hidden subgroup problem, in the group $((\mathbb{Z}/(2))^n, \oplus)$. 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 \to \{0, 1\}^n$ two permutations such that there exists $s \in \{0, 1\}^n$ such that, for all $x$, $g_0(x) = g_1(x \oplus s)$. Find $s$.

*Proof.*

$$ \text{Let } G: \quad \begin{array}{ccc} \{0,1\} \times \{0,1\}^n & \to & \{0,1\}^n \\ (b,x) & \mapsto & \begin{cases} g_0(x) & \text{if } b=0 \\ g_1(x) & \text{if } b=1 \end{cases} \end{array} $$

$G$ satisfies $G(b_0, x_0) = G(b_1, x_1)$ if and only if $(b_0 \oplus b_1, x_0 \oplus x_1) \in \{(0,0), (1,s)\}$. $\square$

Simon's algorithm finds a value $v$ that satisfies $v \cdot s = 0$ in only one query. Hence, one will have enough information to retrieve $s$ with little more than $n$ queries.

## 2.6.2 Use in Cryptanalysis.

In cryptanalysis, the function $G$ under study is built from a block cipher and possible other components; we suppose that all can be queried in quantum superposition. The implication: $[G(x) = G(y)] \Rightarrow [x \oplus y \in \{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 [KLLN16a], around 2 [LM17] or less than 1.2 [Bon18], 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.

## 2.6.3 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 $(\mathbb{G}, +)$ an abelian group, $g_0, g_1 : \mathbb{G} \to \mathbb{G}$ two permutations such that there exists $s \in \mathbb{G}$ such that, for all $x$, $g_0(x) = g_1(x + s)$. Find $s$.

Many variants of Kuperberg's algorithm have been proposed [Kup05, Kup13, Reg04]. 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 a given size of parameter. This case has been studied in [BNP18], where various algorithms and explicit costs for groups of the form $(\mathbb{Z}/(2^w))^p$ are proposed.

Concretely, the cost estimate (in quantum memory and query) is $2^{\sqrt{2\log_2(3^2)n}} \approx 2^{1.78\sqrt{n}}$ for the group $\mathbb{Z}/(2^n)^p$. The authors also propose an algorithm with a cost of $2(p/2 + 1)^w$ for the group $(\mathbb{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 $(\mathbb{Z}/(2^w))^p$. As the worst case is for $\mathbb{Z}/(2^n)$, we will consider this complexity in our cost estimates.

# 3 Advanced Quantum Slide Attacks

In this section, we first present a quantum slide attack on an iterated keyed permutation, similar to the one in [KLLN16a], but with modular additions instead of XOR, therefore using the precise results from [BNP18] 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 [BW00], applied to Feistel variants. We consider all the possible combinations of modular additions and
<figure><img src="image_4.png" /><figcaption>Figure 3: Slide attack on the key-alternating cipher with modular additions</figcaption></figure>

XORs. We also use some ideas from [DKS15] (mirror slidex attack). The round function is assumed weak.

## 3.1 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\} \times \{0,1\}^n \rightarrow \{0,1\}^n \\ b, x \mapsto \begin{cases} g_0(x) = \Pi(E_k(x)) - x & \text{if } b = 0, \\ g_1(x) = E_k(\Pi(x)) - x & \text{if } b = 1. \end{cases} $$

Also as in the previous attack, we know that all $x$ satisfy $\Pi(E_k(x)) + k = E_k(\Pi(x + k))$ because of the sliding property. Then we can see that $G$ verifies the conditions of the hidden shift problem as $g_0(x) = g_1(x + k)$:

$$ G(0, x) = \Pi(E_k(x)) - x = E_k(\Pi(x + k)) - k - x = G(1, x + k). $$

We reasonably assume that both $E_k \circ \Pi$ and $\Pi \circ 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.78\sqrt{n}}$ quantum time and queries.

## 3.2 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 $Trunc_L$ and $Trunc_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
<figure><img src="image_5.png" /><figcaption>**Figure 4:** Slide attack on Feistel scheme with one round self-similarity and modular addition</figcaption></figure>

the function that we will use in our attack:

$$ G : \{0, 1\} \times \{0, 1\}^{n/2} \rightarrow \{0, 1\}^{n/2} \\ b, x \mapsto \begin{cases} g_0(x) = \text{Trunc}_R(E_K(x, R_0)) & \text{if } b = 0, \\ g_1(x) = \text{Trunc}_L(E_K(R_0, x)) & \text{if } b = 1. \end{cases} $$

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\sqrt{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-denenerate function $f$ in Section 4 (it works as long as the key $K$ is added or xored as on Figure 4).

## 3.3 The Quantum Complementation Slide Attack

We illustrate the complementation slide attack [BW00] on a Feistel cipher with 2-round self-similarity, like for instance 2k-DES, introduced in [BW99]. We consider the 3 possible 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 $\Delta = K_0 - K_1$ and if the following equations are verified: $R = L' - \Delta$ and $L + f(R + K_0) = R' + \Delta$, then, the outputs of both plaintexts, $(M, N)$ and $(M', N')$ verify $N = M' - \Delta$ and $N' = M + f(K_1 + N + \Delta) - \Delta$. 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,
<figure><img src="image_6.png" /><figcaption>Figure 5: Representation of the complementation slide attack</figcaption></figure>

for the sake of simplicity, we limit ourselves to describing the generic lines of the attack.

We perform an exhaustive search on $\Delta$. The size of a block and of the whole key is $n$. Considering the value of $R$ fixed to a chosen and known one $R_0$, we can redefine an equivalent round-key $K'_0 = f(R_0 + 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 $\Delta$ are known to the attacker):

$$ G: \{0,1\} \times \{0,1\}^{n/2} \rightarrow \{0,1\}^{n/2} \\ b, x \mapsto \begin{cases} g_0(x) = \text{Trunc}_R(E_k(x, R)) + \Delta & \text{if } b=0, \\ g_1(x) = \text{Trunc}_L(E_k(R - \Delta, x + \Delta)) & \text{if } b=1. \end{cases} $$

From Figure 5 we can verify that $g_0(x) = g_1(x + K'_0)$. For each of the tested values for $\Delta$, 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 $\Delta$, this implies the value of $K_1$. When the tested value for $\Delta$ is the correct one, we should also obtain a collision given by $N' = M + f(K_1 + N + \Delta) - \Delta$, which happens with a random probability $2^{-n}$. When this is the case, this implies that we have recovered the correct values of $K_0$ and $K_1$.

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\sqrt{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.

## 3.4 Sliding with a Twist

A further improved variant of the slide attacks is the “sliding with a twist”, also introduced in [BW00], that can be applied in our case when we have access to the decryption oracle in order to use Simon’s algorithm. It is interesting to see that Kuperberg’s algorithm won’t apply here, as the conditions for the attack are not verified: encryption is structurally different from decryption if we consider modular additions.
<figure><img src="image_7.png" /><figcaption>**Figure 6:** Representation of the sliding with a twist technique</figcaption></figure>

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 not relevant for the complexity.

The main idea of this attack, that we can see represented in Figure 6, 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 \oplus f(R \oplus K_0)$, then $R' = N$ and $L' = M \oplus f(N \oplus K_0)$.

We can consider now $R = N'$ as a fixed chosen value $R_0$. Like the previous attack, if we consider an equivalent key $K'_0 = f(R_0 \oplus K_0)$, we can apply Simon's algorithm. Let us denote the decryption function $D_K$.

$$ G: \{0,1\} \times \{0,1\}^{n/2} \rightarrow \{0,1\}^{n/2} \\ b, x \mapsto \begin{cases} g_0(x) = \text{Trunc}_R(E_K(x, R)) = N & \text{if } b=0, \\ g_1(x) = \text{Trunc}_R(D_K(x, R)) = R' & \text{if } b=1. \end{cases} $$

From Figure 6 we can verify the slide shift equation $g_0(x) = g_1(x \oplus K'_0)$. Simon's algorithm recovers the value of $K'_0$, and from it, also the one of $K_0$ with negligible complexity 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 for this in the case that all the transformations were xors would be of $n$, compared to $2^{n/2}$ from the quantum accelerated exhaustive search of the generic attack. If we have modular additions between branches, this attack would not apply, as the decryption scheme should have subtractions instead of additions.
## 3.5 Quantum Mirror Slidex Attacks on Feistel Schemes

When a cipher is of the form $E = E_2 \circ E_1 \circ E_0$ in which $E_1$ is an involution, the equation that we can write, and that corresponds to the mirror slidex attack of [DKS15], is: $E_0^{-1} \circ E_2^{-1} \circ E(P) = E^{-1} \circ E_2(E_0(P))$. We expect it to yield a hidden period, recoverable using Simon's or Kuperberg's algorithms. Although a classical mirror slidex does not necessarily give rise to a quantum one, the case of a self-similar Feistel scheme with key whitenings (which we denote by rk-WFeistel) is very practical.

**Quantum attack on 2k-WFeistel.** We are able to quantize the attack on 2k-WFeistel developed in [DKS15], Section 7.3 (2K-DESX in the paper). The idea relies on mirror slidex combined with the complementation slide. A decryption oracle is required.

Mostly following [DKS15] in the notations, we write:

$$E(x) = k_2 \oplus E_1(k_0 \oplus x)$$

where $E_1$ is a 2k-Feistel scheme of alternating keys $k_a, k_b$, so that the whole key of $E_k$ is $k = k_0, k_2, k_a, k_b$. We note $\Delta = k_a \oplus k_b$. Even if $E_1$ is not exactly an involution, we can use the complementation slide here and correct it with $\Delta||\Delta$, obtaining the main “mirror equation”:

$$E_1(x) = E_1^{-1}(x \oplus (\Delta||\Delta)) \oplus (\Delta||\Delta) .$$

Now, since $E_0$ and $E_2$ are merely key whitenings: $E_0(x) = x \oplus k_0$, $E_2(x) = x \oplus k_2$, we have $E_1(x) = k_2 \oplus E(x \oplus k_0)$ and $E_1^{-1}(x) = k_0 \oplus E^{-1}(x \oplus k_2)$ where $E$ and $E^{-1}$ can be queried, hence:

$$E(x \oplus k_0) \oplus k_2 = k_0 \oplus E^{-1}(x \oplus k_2 \oplus (\Delta||\Delta)) \oplus (\Delta||\Delta) .$$

This gives the slide shift equation:

$$E(y) \oplus y = E^{-1}(y \oplus s) \oplus (y \oplus s)$$

where $s = k_0 \oplus k_2 \oplus (\Delta||\Delta)$ is the promise. We can recover $s$ in $n$ encryption and decryption queries. This is a distinguisher for this construction, but not a complete key recovery. As the total key size is $3n$, we can recover all with an additional exhaustive search at cost $2^n$. This is beaten by the quantum attack on the FX construction [LM17], which has a cost of around $n2^{n/2}$.

However, we may be in a case where $k_0 = k_2$. In that case, we directly recover $(\Delta||\Delta)$, that is, $k_a \oplus k_b$, which means we can apply the quantum attack on the FX construction, but only need to search for one of the two inner keys, at a cost of $n2^{n/4}$.

More generally, if the internal function is an involution or only needs to be corrected by xorings, and if $E_2$ and $E_0$ are key whitenings, the scheme will be vulnerable to this quantum slide attack. If all xors are replaced by modular additions (whitenings as well as the mirror property), we may write: $E_1^{-1}(x) = E_1(x + \delta_a) + \delta_b$, $E_1(x) = E(x - k_0) - k_2$ and $E_1^{-1}(x) = k_0 + E^{-1}(x + k_2)$. This gives a slide equation:

$$E(y) = k_0 + k_2 + \delta_b + E_1^{-1}(x + k_0 + k_2 + \delta_a) .$$

If different operations are used (e.g, modular additions for the whitenings and a xor inside the mirror property), it does not seem to work anymore, as the whitening and the slide operation would not commute.
**A variant of 4k-WFeistel.** We follow [DKS15], section 7.4, and consider the 4k-WFeistel scheme (4K-DESX in the paper) with keys $k_0, k_2, k_a, k_b, k_c, k_d$ and $4m+1$ rounds scheduled as: $(k_a, k_b, k_c, k_d)^m, k_a$.

Slide pairs $(P, C), (P', C')$ have the properties:

$$P \oplus C' = k_0 \oplus k_2 \oplus (k_b \oplus k_d||0)$$
$$E_1(P \oplus k_0) = E_1^{-1}(C' \oplus k_2) \oplus (k_b \oplus k_d||0)$$

As in the paragraph above, the term $(k_b \oplus k_d||0)$ corrects the inversion of $E_1$. Then:

$$E_1(P \oplus k_0) = E_1^{-1}(Pk_0 \oplus (k_b \oplus k_d||0)) \oplus (k_b \oplus k_d||0)$$

Hence for all $x$, $E(x \oplus s) = E^{-1}(x)$ where $s = k_0 \oplus k_2 \oplus (k_b \oplus k_d||0)$, that we can retrieve in $n$ queries.

As before, this very efficient distinguisher may not yield the best key recovery if $k_0 \neq k_2$, but improves the generic quantum attack on the FX construction from $n2^n$ to $n2^{0.75n}$ if $k_0 = k_2$. A more efficient attack with $4m$ rounds is presented in Section 5.

# 4 Composing Quantum Attacks: Key-Recovery with Strong Round Functions

In this section, we propose efficient key-recovery attacks on one-round self-similar Feistel construction 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\sqrt{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.

## 4.1 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$.

**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.5, 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\} \times \{0,1\}^{n/2} \rightarrow \{0,1\}^{n/2} \\ b, x \mapsto \begin{cases} g_0(x) = H(x) = f(x+K) & \text{if } b=0, \\ g_1(x) = f(x) & \text{if } b=1. \end{cases}$$
<figure><img src="image_8.png" /><figcaption>**Figure 7:** Slide attack on a generic one-round self-similar Feistel</figcaption></figure>

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\sqrt{n}}$ queries.

<figure><img src="image_9.png" /><figcaption>**Figure 8:** Example of a vulnerable Feistel</figcaption></figure>
## 4.2 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\} \times \{0,1\}^{n/2} \rightarrow \{0,1\}^n \\ b, x \mapsto \begin{cases} g_0(x) = E_K(x, x) + (x, x) & \text{if } b=0, \\ g_1(x) = E_0(x, x) + (x, x) & \text{if } b=1. \end{cases} $$

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\} \times (\{0,1\}^{n/2})^2 \rightarrow \{0,1\}^n \\ b, x, y \mapsto \begin{cases} g_0(x) = E_{K_0, K_1}(x, y) + (x, y) & \text{if } b=0, \\ g_1(x) = E_{0,0}(x, y) + (x, y) & \text{if } b=1. \end{cases} $$

As we have the same property $E_{K_0,K_1} + (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.

<table><caption>**Table 2:** Summary of the slide attack costs, $n$ is the block size.</caption><thead><tr><th>Branch, Key add.</th><th>Round function</th><th>quantum query cost</th><th>Remark</th></tr></thead><tbody><tr><td>⊕, any</td><td>Weak</td><td>n/2</td><td></td></tr><tr><td>⊕, ⊕</td><td>f(x ⊕ K)</td><td>n/2</td><td></td></tr><tr><td>⊕, ⊕</td><td>f<sub>K</sub>(x)</td><td>n<sup>2</sup>/4</td><td>Simon calls purely quantum Simon</td></tr><tr><td>⊕, +</td><td>f<sub>K</sub>(x)</td><td>n2<sup>1.2√n</sup></td><td>Kuper. calls purely quantum Simon</td></tr><tr><td>+, any</td><td>Weak</td><td>2<sup>1.2√n</sup></td><td></td></tr><tr><td>+, +</td><td>f(x + K)</td><td>2<sup>1.2√n</sup></td><td>Need the exact same addition</td></tr><tr><td>+, ⊕</td><td>f<sub>K</sub>(x)</td><td>n2<sup>1.2√n</sup></td><td>Simon calls purely quantum Kuper.</td></tr><tr><td>+, +</td><td>f<sub>K</sub>(x)</td><td>2<sup>2.4√n</sup></td><td>Kuper. calls purely quantum Kuper.</td></tr><tr><td>⊕, ⊕</td><td>f(x ⊕ K)</td><td>n</td><td>2-Round self-similarity</td></tr><tr><td>+, +</td><td>f(x + K)</td><td>2<sup>1.78√n</sup></td><td>2-Round self-similarity, Need the exact same addition</td></tr></tbody></table>

# 5 Quantum Slide Attacks on 4-Round Self-Similar Feistels

Combining twist and complementation slides enables the authors in [BW00] 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 \dots \\ k_3 k_2 k_1 k_0 \dots$$

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 $\Delta = k_1 \oplus 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 \oplus \Delta \oplus f(k_0 \oplus N), N \qquad (4)$$

$$M', N' = L \oplus f(R \oplus k_0) \oplus \Delta, R \qquad (5)$$

<figure><img src="image_10.png" /><figcaption>Figure 9: Complementation and twist combined on a 4k-Feistel scheme</figcaption></figure>

For all $P = (x, R)$ we write $D_k(M', N') = (L', R')$, $M = \text{Trunc}_L(E_k(x, R))$, $N = \text{Trunc}_R(E_k(x, R))$, which gives:

$$D_k(x \oplus f(R \oplus k_0) \oplus \Delta, R) = M \oplus \Delta \oplus f(k_0 \oplus N), N \\ \implies \text{Trunc}_R(D_k(x \oplus f(R \oplus k_0) \oplus \Delta, R)) = \text{Trunc}_R(E_k(x, R))$$
Hence, for a fixed $R$, we have the following function $G$:

$$ G: \{0,1\} \times \{0,1\}^{n/2} \rightarrow \{0,1\}^{n/2} \\ b, x \mapsto \begin{cases} g_0(x) = \text{Trunc}_R(D_k(x, R)) & \text{if } b=0, \\ g_1(x) = \text{Trunc}_R(E_k(x, R)) & \text{if } b=1. \end{cases} $$

The hidden shift between $g_0$ and $g_1$ is $f(R \oplus k_0) \oplus \Delta$.

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 \oplus k_0) \oplus \Delta$. As $f$ is public, we can create a quantum oracle to the function $G'(R) = f(R) \oplus f(R \oplus k_0) \oplus \Delta$. This function has $k_0$ as a hidden period, which can be recovered, by reusing Simon's algorithm. The total cost is around $2n^2$ queries (the input space is of size $n/2$, but there is a lot of mandatory uncomputing here), for recovering $k_0$. Once $k_0$ is known, we can directly use the first attack to get $\Delta = k_1 \oplus k_3$, at a negligible cost of $n/2$.

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 $\Delta' = k_2 \oplus k_0$. With $k_1$ and $\Delta$, we obtain $k_3$, and with $k_0$ and $\Delta'$, we obtain $k_2$. The total cost is around $4n^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.

**4 Rounds of Feistel.** This attack leads to a very efficient distinguisher on 4 rounds of Feistel, if one has access to both encryption and decryption oracles, which improves on the previous 3-round distinguisher of [KM10] (which only needs encryption) <fnref n="1" />.

**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}$. We remark that $(P, C), (P', C')$ are slide pairs for the underlying 4k-Feistel iff $(P \oplus k_{pre}, C \oplus k_{post}), (P' \oplus k_{pre}, C' \oplus k_{post})$ are slide pairs for the complete scheme (such properties are suggested by [DDKS15]). Using the slide equations above, we rewrite them with the key whitenings:

$$ \begin{aligned} L', R' &= M \oplus k_{post}^L \oplus k_{pre}^L \oplus \Delta \oplus f(k_0 \oplus N \oplus k_{post}^R), N \oplus k_{pre}^R \oplus k_{post}^R \\ M', N' &= L \oplus k_{pre}^L \oplus k_{post}^L \oplus \Delta \oplus f(R \oplus k_{pre}^R \oplus k_0), R \oplus k_{pre}^R \oplus k_{post}^R \end{aligned} $$

Writing $D_k(M', N') = L', R'$, this gives us:

$$ \begin{aligned} \text{Trunc}_R(D_k(L \oplus k_{pre}^L \oplus k_{post}^L \oplus \Delta \oplus f(R \oplus k_{pre}^R \oplus k_0), R \oplus k_{pre}^R \oplus k_{post}^R) \\ = \text{Trunc}_R(E_k(L, R)) \oplus k_{pre}^R \oplus k_{post}^R \end{aligned} $$

We introduce $\delta_R = k_{pre}^R \oplus k_{post}^R$ and $\delta_L = k_{pre}^L \oplus k_{post}^L \oplus \Delta$ (where $\Delta = k_1 \oplus k_3$). Then:

$$ \begin{aligned} \text{Trunc}_R(D_k(L \oplus \delta_L \oplus f(R \oplus \delta_R \oplus (k_{pos}^R \oplus k_0)), R \oplus \delta_R) \oplus (R \oplus \delta_R) \\ = \text{Trunc}_R(E_k(L, R)) \oplus R \end{aligned} $$

Now, we can use the function

$$ G: \{0,1\} \times (\{0,1\}^{n/2})^2 \rightarrow \{0,1\}^{n/2} \\ b, x, y \mapsto \begin{cases} g_0(x, y) = \text{Trunc}_R(D_k(x \oplus f(y \oplus (k_{pos}^R \oplus k_0)), y) \oplus y & \text{if } b=0, \\ g_1(x, y) = \text{Trunc}_R(E_k(x, y)) & \text{if } b=1. \end{cases} $$

<footnote n="1">¹In [Iwa18] a short presentation was given on a more general QCCA 4-round distinguisher of Feistel networks</footnote>
We have $g_0(x, y) = g_1(x \oplus \delta_L, y \oplus \delta_R)$. However, to implement $g_0$, we need to know the value $(k_{pos}^R \oplus k_0)$. Hence, first guess the value of $(k_{pos}^R \oplus k_0)$ using Grover's algorithm, and combine it with Simon's algorithm as studied in [LM17], In time and queries $n2^{n/4}$, this attack recovers $\delta_L, \delta_R$ and $(k_{pos}^R \oplus k_0)$. Now, we can perform the analogue of the classical attack: swapping the encryption and the decryption, we obtain $k_{pre}^L \oplus k_{post}^L$ and $k_{pre}^R \oplus k_{post}^R \oplus k_0 \oplus k_2$, which allows to obtain $k_0 \oplus k_2$ and $k_1 \oplus k_3$.

Now, we can break the complete cipher by applying the Grover-meet-Simon attack on the FX construction. We only need to search for 2 of the inner keys, for a total cost of $n2^{n/2}$.

As this attack uses the sliding with a twist technique, it does not transpose well to modular additions.

# 6 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 [KLLN16a] were, expecting for instance exponential speedups. In this section we show that the speedup is much smaller than expected, as the same techniques cannot be applied, but we are able to propose some improved-over-classical quantum associated attacks, that gain in efficiency.

## 6.1 Definition of a Cycle Slide Attack

We suppose that $E_k = f_k^l$ 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_k^2(P), \dots$$

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_k^{m_1}(P) = P$. Then one has $m_2 = m_1/gcd(m_1, l)$. Moreover, suppose that $gcd(m_1, l) = 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_1m - d_2l = 1$. This gives:

$$ 
\begin{aligned}
f_k^{d_1m-d_2l+1}(P) &= P \\
f_k^{d_1m+1} &= f_k^{d_2l}(P) = E_k^{d_2}(P) \\
f_k(P) &= E_k^{d_2}(P)
\end{aligned}
$$

Hence $(P, E_k^{d_2}(P))$ is a slid pair. Moreover, $(E_k^t(P), E_k^{d_2+t}(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 $l$) is strictly smaller than one, exactly $\phi(l)/l$ where $\phi$ 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 $l$), the complexity can increase dramatically, since we would require all cycles to be good at the same time: it happens only with probability $(\phi(l)/l)^t$ if there are $t$ of them.

**Classical Examples and Applications.** The cycle slide attack is applied in [BOBDK18] against a palindromic Feistel scheme, where the keys are scheduled as:

$$k_0, k_1 \dots k_r, k_r, k_{r-1}, \dots k_0, k_0, k_1, \dots$$

The function $f_k$ is a Feistel scheme with $2r$ keys scheduled as $k_0, k_1 \dots k_r, k_r, k_{r-1}, \dots 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.

In [BOBDK18, section 5], the authors present attacks on GOST. First:

* 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_k^3$ 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_k^4$ 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.

## 6.2 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 \in \mathbb{Z} \mapsto E_k^d(P)$$

If the function $G(d) = E_k^d(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_k^d$ in superposition over $d$, which seems highly difficult. The encryption oracle $E_k$ is actually only accessed through queries $x \to E_k(x)$, in superposition over $x$. To compute $E_k^d$ 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(\sqrt{2^n/k})$ calls to a testing subprocedure $G$, implemented using a quantum algorithm, that computes: $G(P) = 1 \iff \exists u \le d, E_k^u(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 the Grover search for points of cycle length less than or equal to $d$ costs $O(\sqrt{2^n/d})$ calls to $G$, and $O(\sqrt{d2^n})$ queries to $E_k$.

**Property 1.** Using Grover's algorithm, one can find a superposition of points that lie on a cycle of length less than $d$ in $O(\sqrt{d2^n})$ calls to $E_k$.

Using Grover's algorithm, one can find a superposition of points that lie on a cycle of length precisely $d$ in $O(d\sqrt{2^n})$ calls to $E_k$, if such points exist.

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 + \sqrt{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_k^r$ satisfies the following properties:

* The cipher $E_k$ is not some weak Feistel construction (e.g, 2k-Feistel, 4k-Feistel), that is already broken using period-finding;

* The round function $f_k$ is weak: a small number of slide pairs suffice to get the subkey material (e.g either a constant number, or linear in the block size), but one slide pair is not enough;

* The block size $n$ is much smaller than the key size, so that Grover search on the key space becomes useless (even when combined with Simon's algorithm as in [LM17]).

**Example.** For example, this would speed up (but not much) the attack on 24-round GOST of [BOBDK18], 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 $c\sqrt{2^{36.5}2^{64}}$ where $c$ is some constant. This diminishes the amount of work towards around $2^{50}$ superposition queries instead of $2^{64}$ classical.

## 6.3 Cycle-based Slide Attacks against Weak SPN Constructions

We are inspired by [BOBDK18] and the attacks against the SA construction and weak variants of AES. We remark that in [BOBDK18], much computation time is required to find actually the slide pairs, whereas given access to quantum computing power and a quantum encryption oracle, finding some of these pairs costs much less.
<figure><img src="image_11.png" /><figcaption>Figure 10: Slide attack against a 2k-SPN</figcaption></figure>

**Attacking 2k-SPN.** The cipher we are attacking here consists only in xoring with the alternating keys $k_0, k_1$, and applying a fixed, public permutation $\Pi$ at each round. The number of rounds is $2r$, where, as in any slide attack, $r$ is not relevant.

This scheme resists to the basic slide attack, but we can write $E_k \circ \Pi = f_k^r(x)$ where $f_k(x) = \Pi(k_1 \oplus \Pi(k_0 \oplus 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 \circ \Pi$. Recall that $n$ is the block size here; the key length is $2n$. Therefore we obtain two equations:

$$ 
\begin{aligned}
y &= \Pi(k_1 \oplus \Pi(k_0 \oplus x)) \\
y' &= \Pi(k_1 \oplus \Pi(k_0 \oplus x'))
\end{aligned}
$$

Since $\Pi$ is public, we can invert it efficiently. We find:

$$ \Pi^{-1}(y) \oplus \Pi^{-1}(y') = \Pi(k_0 \oplus x) \oplus \Pi(k_0 \oplus x') $$

Solving this equation on $k_0$, if $\Pi$ has no specific property, can be done in $O(2^{n/2})$ time and queries using Grover's algorithm, the same complexity as the first stage (cycle finding). This improves a little on the Grover-meets-Simon technique of [LM17], which would perform in $O(n2^{n/2})$ time and queries. Note that an efficient classical slide attack on 2k-SPN and 3k-SPN (where the key is xored) is already given in [BOBDK18], applied to AES.

**Attacking 3k-SPN.** Cycle-finding can further be applied on a 3k-SPN construction. Still using $O(2^{n/2})$ quantum queries, we now write the slide equations as:

$$ 
\begin{aligned}
y &= \Pi(k_2 \oplus \Pi(k_1 \oplus \Pi(k_0 \oplus x))) \\
y' &= \Pi(k_2 \oplus \Pi(k_1 \oplus \Pi(k_0 \oplus x'))) \\
\Rightarrow \Pi^{-1}(y) \oplus \Pi^{-1}(y') &= \Pi(k_1 \oplus \Pi(k_0 \oplus x)) \oplus \Pi(k_1 \oplus \Pi(k_0 \oplus x'))
\end{aligned}
$$

To solve efficiently this equation in $k_0$ and $k_1$, we guess first $k_0$ using Grover's algorithm. Since we are studying an SPN, the permutation $\Pi$ rewrites $\Pi = A \circ S$ where $A$ is the linear layer and $S$ the non-linear layer of S-Boxes. Hence the equation on $k_1$ becomes:

$$ A^{-1}(\Pi^{-1}(y) \oplus \Pi^{-1}(y')) = S(k_1 \oplus \Pi(k_0 \oplus x)) \oplus S(k_1 \oplus \Pi(k_0 \oplus 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, to compare with $O(2^n)$ for the Grover-meets-Simon general technique, which would require to guess two subkeys (and does not use the specific structure of $\Pi$).
**Attacking 4k-AES.** In the case of AES, we can add one more round by remarking that a slide equation of the form:

$$A^{-1}(\Pi^{-1}(y) \oplus \Pi^{-1}(y')) = S(k_1 \oplus \Pi(k_0 \oplus x)) \oplus S(k_1 \oplus \Pi(k_0 \oplus x'))$$

can be solved more efficiently in $k_0$ and $k_1$. Indeed, we may guess simultaneously $k_0$ diagonal by diagonal and $k_1$ column by column. The cycle step will have complexity approximately $2^{64}$ time and queries, while the equation step will have complexity $4 \times 2^{64} \times 2^{32} = 2^{98}$ time.

**Further Variants.** More generally, we can Grover-guess all keys except two or three of them, depending whether we attack a general SPN construction or rk-AES. For rk-SPN, the attack has a complexity $O(2^{(r-2)n/2})$ instead of $O(2^{(r-1)n/2})$.

## 6.4 Cycle-based Slide Attacks against Weak Feistel Constructions

This attack can be used against some Feistel constructions where complementation slide and sliding with a twist don't help. Consider 3k-Feistel, with an internal mixing function $f$, three alternating keys $k_0, k_1, k_2$ and a subsequent round function $g$:

$$L, R \mapsto 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)))$$

If we can invert $f$, we can break the round function given two slide equations $g(P) = P'$:

* Write two equations $f(k_1 + L + f(k_0 + R)) = X \implies k_1 + L + f(k_0 + R) = f^{-1}(X)$ and sum to get an equation on $k_0$, solve this equation (using Grover it takes $O(2^{n/4})$ computations, this will be less if the equation can be solved more efficiently);

* Find $k_1$;

* Then find $k_2$ and check consistency.

The most costly part is finding a small cycle, which costs $2^{n/2}$ time and queries.

**Against 4k-Feistel.** Attacking 4k-Feistel in $O(2^{n/2})$ is as trivial as taking two guesses for $k_0, k_1$ and performing a Grover search, finding $k_2, k_3$ using the slide equations, to compare with $O(2^n)$ using Grover search over all the keys.

Contrarily to sliding with a twist, which requires decryption queries, this one uses only encryption queries. Besides, it works as well in the case of modular additions on the branches, where the twist does not work anymore.

**Against rk-Feistel.** For $r \ge 3$, rk-Feistel can be attacked in $O(2^{(r-2)n/2})$ instead of $O(2^{rn/2})$ with Grover search on keys.

## 7 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), while the classical cost does not depend on them. 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 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 [AR17] does not seem to counter the attacks, as already pointed out in [BNP18]. 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.

## References

[AR17] Gorjan Alagic and Alexander Russell. Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, *EUROCRYPT (3)*, volume 10212 of LNCS, pages 65–93, 2017.

[BNP18] Xavier Bonnetain and María Naya-Plasencia. Hidden shift quantum cryptanalysis and implications. Cryptology ePrint Archive, Report 2018/432, 2018. https://eprint.iacr.org/2018/432.

[BOBDK18] Achiya Bar-On, Eli Biham, Orr Dunkelman, and Nathan Keller. Efficient Slide Attacks. *Journal of Cryptology*, 31(3):641–670, Jul 2018.

[Bon18] Xavier Bonnetain. Quantum key-recovery on full AEZ. In *Selected Areas in Cryptography - SAC 2017 - 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers*, volume 10719 of *Lecture Notes in Computer Science*, pages 394–406. Springer, 2018.

[BW99] Alex Biryukov and David Wagner. Slide Attacks. In Lars R. Knudsen, editor, *Fast Software Encryption, 6th International Workshop, FSE '99, Rome, Italy, March 24-26, 1999, Proceedings*, volume 1636 of LNCS, pages 245–259. Springer, 1999.

[BW00] Alex Biryukov and David Wagner. Advanced Slide Attacks. In Bart Preneel, editor, *Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding*, volume 1807 of LNCS, pages 589–606. Springer, 2000.

[BZ13] Dan Boneh and Mark Zhandry. Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World. In *Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II*, pages 361–379, 2013.

[CNPS17] André Chailloux, María Naya-Plasencia, and André Schrottenloher. An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography. *Asiacrypt 2017*, 2017. to appear.
[DDKS15] Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir. Reflections on slide with a twist attacks. Des. Codes Cryptography, 77(2-3):633-651, 2015.

[DDW18] Xiaoyang Dong, Bingyou Dong, and Xiaoyun Wang. Quantum attacks on some feistel block ciphers. Cryptology ePrint Archive, Report 2018/504, 2018. https://eprint.iacr.org/2018/504.

[DFNS13] Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, and Louis Salvail. Superposition Attacks on Cryptographic Protocols. In Carles Padró, editor, *Information Theoretic Security - 7th International Conference, ICITS 2013, Singapore, November 28-30, 2013, Proceedings*, volume 8317 of LNCS, pages 142-161. Springer, 2013.

[DKS15] Orr Dunkelman, Nathan Keller, and Adi Shamir. Slidex attacks on the even-mansour encryption scheme. J. Cryptology, 28(1):1-28, 2015.

[DW17] Xiaoyang Dong and Xiaoyun Wang. Quantum key-recovery attack on feistel structures. Cryptology ePrint Archive, Report 2017/1199, 2017. https://eprint.iacr.org/2017/1199.

[Gag17] Tommaso Gagliardoni. *Quantum Security of Cryptographic Primitives*. PhD thesis, Darmstadt University of Technology, Germany, 2017.

[GHS16] Tommaso Gagliardoni, Andreas Hülsing, and Christian Schaffner. Semantic Security and Indistinguishability in the Quantum World. In Matthew Robshaw and Jonathan Katz, editors, *Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III*, volume 9816 of LNCS, pages 60-89. Springer, 2016.

[HS17] Akinori Hosoyamada and Yu Sasaki. Quantum meet-in-the-middle attacks: Applications to generic feistel constructions. Cryptology ePrint Archive, Report 2017/1229, 2017. https://eprint.iacr.org/2017/1229.

[HSX17] Akinori Hosoyamada, Yu Sasaki, and Keita Xagawa. Quantum Multicollision-Finding Algorithm. *Asiacrypt 2017*, 2017. to appear.

[Iwa18] Tetsu Iwata. QCCA on Feistel. In *Dagstuhl Symmetric Cryptography Seminar 18021*, January 2018.

[Kap14] Marc Kaplan. Quantum attacks against iterated block ciphers. CoRR, abs/1410.1434, 2014.

[KLLN16a] Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. Breaking Symmetric Cryptosystems Using Quantum Period Finding. In Matthew Robshaw and Jonathan Katz, editors, *Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II*, volume 9815 of LNCS, pages 207-237. Springer, 2016.

[KLLN16b] Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. Quantum Differential and Linear Cryptanalysis. *IACR Trans. Symmetric Cryptol.*, 2016(1):71-94, 2016.

[KM10] H. Kuwakado and M. Morii. Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In *Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on*, pages 2682-2685, June 2010.
[KM12] H. Kuwakado and M. Morii. Security on the quantum-type Even-Mansour cipher. In *Information Theory and its Applications (ISITA), 2012 International Symposium on*, pages 312–316, Oct 2012.

[Kup05] Greg Kuperberg. A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. *SIAM J. Comput.*, 35(1):170–188, 2005.

[Kup13] Greg Kuperberg. Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. In Simone Severini and Fernando G. S. L. Brandão, editors, *8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, May 21-23, 2013, Guelph, Canada*, volume 22 of *LIPIcs*, pages 20–34. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013.

[LM17] Gregor Leander and Alexander May. Grover Meets Simon - Quantumly Attacking the FX-construction. In Tsuyoshi Takagi and Thomas Peyrin, editors, *Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II*, volume 10625 of *Lecture Notes in Computer Science*, pages 161–178. Springer, 2017.

[Reg04] Oded Regev. A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space. *CoRR*, 2004.

[Sim94] Daniel R. Simon. On the Power of Quantum Computation. In *35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994*, pages 116–123. IEEE Computer Society, 1994.

[Zha12] Mark Zhandry. How to Construct Quantum Random Functions. In *53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012*, pages 679–687, 2012.

## A Summary of Classical Slide Attacks

We provide in Tables 3 and 4 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.
<table><caption>**Table 3:** Classical slide attacks on specific constructions</caption><thead><tr><th>Cipher<br>attacked</th><th>Attack details</th><th>Encryption<br>queries</th><th>Time</th><th>Decryption<br>queries</th><th>Memory</th><th>Source</th></tr></thead><tbody><tr><td rowspan="2">2K-DES (64-bit blocks)<br>TREYFER<br>(64-bit blocks)</td><td></td><td>2<sup>32</sup></td><td>2<sup>50</sup></td><td></td><td>2<sup>32</sup></td><td>[BW99], Section 4</td></tr><tr><td></td><td>2<sup>32</sup></td><td>2<sup>40</sup></td><td></td><td>2<sup>32</sup></td><td>[BW99], Section 5</td></tr><tr><td>DESX (64-bit<br>blocks)</td><td>Sliding with a<br>twist, known-<br>plaintext only</td><td>2<sup>32,5</sup></td><td>2<sup>87,5</sup></td><td></td><td>2<sup>32,5</sup></td><td>[BW00], Section 4</td></tr><tr><td>GOST (20<br>rounds)</td><td>Sliding with a<br>twist</td><td>2<sup>33</sup></td><td>2<sup>70</sup></td><td></td><td>2<sup>65</sup></td><td>[BW00], Section 5</td></tr><tr><td rowspan="4">2K-AES (128-bit blocks)<br>3K-AES (128-bit blocks)<br>24-round<br>GOST with<br>unknown<br>S-Boxes<br>Palindromic<br>GOST with<br>unknown<br>S-Boxes</td><td></td><td>2<sup>69</sup></td><td>2<sup>69</sup></td><td></td><td>2<sup>69</sup></td><td>[BOBDK18], Section 2.3</td></tr><tr><td></td><td>2<sup>81</sup></td><td>2<sup>81</sup></td><td></td><td>2<sup>81</sup></td><td>[BOBDK18], Section 2.3</td></tr><tr><td rowspan="2">Slide and truncated differential<br>on 8 rounds</td><td>2<sup>63</sup></td><td>2<sup>63</sup></td><td></td><td>2<sup>63</sup></td><td>[BOBDK18], Section 5.3</td></tr><tr><td>2<sup>40</sup></td><td>2<sup>40</sup></td><td></td><td>2<sup>40</sup></td><td>[BOBDK18], Section 5.4</td></tr></tbody></table>
<table><caption>**Table 4:** Classical slide attacks on generic constructions. We omit *O* notations.</caption><thead><tr><th>Cipher attacked</th><th>Remark</th><th>Encr. queries</th><th>Time</th><th>Dec. queries</th><th>Memory</th><th>Source</th></tr></thead><tbody><tr><td>One-round self-similar cipher with weak round function 1k-Feistel</td><td>Exhaustive search of slide pairs</td><td>2<sup>n/2</sup></td><td>2<sup>n</sup></td><td></td><td>2<sup>n/2</sup></td><td>[BW99], 2</td></tr><tr><td></td><td>Chosen-plaintext search of slide pairs</td><td>2<sup>n/4</sup></td><td>2<sup>n/2</sup></td><td></td><td>2<sup>n/4</sup></td><td>[BW99], 3</td></tr><tr><td>2k-Feistel</td><td>Complementation slide</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td></td><td>2<sup>n/2</sup></td><td>[BW00], 3.1</td></tr><tr><td>2k-Feistel</td><td>Sliding with a twist</td><td>2<sup>n/4</sup></td><td>2<sup>n/4</sup></td><td>2<sup>n/4</sup></td><td>2<sup>n/4</sup></td><td>[BW00], 3.2</td></tr><tr><td>4k-Feistel</td><td>Complementation and sliding with a twist</td><td>2<sup>n/4</sup></td><td>2<sup>n/4</sup></td><td>2<sup>n/4</sup></td><td>2<sup>n/4</sup></td><td>[BW00], 3.3</td></tr><tr><td>Even-Mansour construction</td><td>Known-plaintext only</td><td>2<sup>(n+1)/2</sup></td><td>2<sup>(n+1)/2</sup></td><td></td><td>2<sup>(n+1)/2</sup></td><td>[BW00], 4</td></tr><tr><td>1k-SPN</td><td></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td></td><td>2<sup>n/2</sup></td><td>[BOBDK18], 2.1</td></tr><tr><td>3k-Feistel</td><td></td><td>2<sup>5n/6</sup></td><td>2<sup>5n/6</sup></td><td></td><td>2<sup>2n/3</sup></td><td>[BOBDK18], 3</td></tr><tr><td>Palindromic-scheduled Feistel<sup>†</sup></td><td></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td></td><td></td><td>[BOBDK18], 4.2</td></tr><tr><td>Generic* E<sub>k</sub> = f<sub>k</sub><sup>l</sup></td><td>Cycle structure</td><td>2<sup>n-1</sup></td><td>t + 2<sup>n-1</sup></td><td></td><td>2<sup>n-1</sup></td><td>[BOBDK18], 4.1</td></tr><tr><td>2k-WFeistel</td><td>Mirror slidex and complementation slide</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>[DKS15], 7.3</td></tr><tr><td>4k-WFeistel with schedule (k<sub>a</sub>, k<sub>b</sub>, k<sub>c</sub>, k<sub>d</sub>)<sup>m</sup>k<sub>a</sub></td><td>Mirror slidex and complementation slide</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>[DKS15], 7.4</td></tr><tr><td>4k-Feistel</td><td>Enhanced reflection</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td></td><td>n</td><td>[DDKS15], 4</td></tr><tr><td>4k-WFeistel</td><td>Enhanced reflection</td><td>n2<sup>n/2</sup></td><td>n2<sup>n/2</sup></td><td></td><td>n2<sup>n/2</sup></td><td>[DDKS15], 4</td></tr></tbody></table>

<footnote>*t* is the time needed to attack *f*<sub>*k*</sub>.</footnote>

<footnote>† at best (depends in practice on attacking the palindromic round function)</footnote>