Quantum Attacks Without Superposition Queries: The Offline Simon’s Algorithm

Abstract

In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon’s period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive.

In this paper, we introduce a new quantum algorithm which uses Simon’s subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search with Grover’s algorithm. In particular, we are able to break the Even-Mansour construction in quantum time $\tilde{O}(2^{n/3})$, with $O(2^{n/3})$ classical queries and $O(n^2)$ qubits only. In addition, we improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity.

Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover’s algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure.

We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.

1 Introduction

Ever since Shor [39] introduced his celebrated quantum polynomial-time algorithm for solving factorization and Discrete Logarithms, both problems believed to be classically intractable, post-quantum cryptography has become a subject of wide interest. Indeed, the security of classical cryptosystems relies on computational assumptions, which until recently, were made with respect to classical adversaries; if quantum adversaries are to be taken into account, the landscape of security is bound to change dramatically.

While it is difficult to assert the precise power of quantum computers, which are yet to come, it is still possible to study quantum algorithms for cryptographic problems, and to estimate the computational cost of solving these problems for a quantum adversary. The ongoing project by NIST [35] for post-quantum asymmetric schemes aims to replace the current mostly used ones by new standards.

In symmetric cryptography, the impact of quantum computing seems, at first sight, much more limited. This is because the security of most of symmetric-key schemes is not predicated on structured problems. Symmetric-key schemes are required to be computed extremely efficiently, and designers must avoid such computationally expensive operations. Grover’s quantum search algorithm [22], another cornerstone of quantum computing, speeds up by a quadratic factor exhaustive search procedures. This has led to the common saying that “doubling the key sizes” should ensure a similar level of post-quantum security.

However, the actual post-quantum security of symmetric-key schemes requires more delicate treatment. Recovering the secret key via exhaustive search is only one of all the possible approaches. The report of the National Academy of Sciences on the advent of quantum computing [34] also states that “it is possible that there is some currently unknown clever quantum attack” that would perform much better than Grover’s algorithm. Indeed, cryptographers are making significant progress on quantum attackers with superposition queries, which break many symmetric-key schemes in polynomial time.

Quantum Generic Attacks in Q1 and Q2 Models. Quantum attacks can be mainly classified into two types [20, 23, 25], Q1 model and Q2 model, assuming different abilities for the attacker. In the Q1 model, attackers have an access to a quantum computer to perform any offline computation, while they are only allowed to make online queries in a classical manner. In the Q2 model, besides the offline quantum computation, attackers are allowed to make superposition queries to a quantum cryptographic oracle. Here, we briefly review previous results in these models to introduce the context of our results.

The Q2 model is particularly interesting as it yields some attacks with a very low cost. Kuwakado and Morii [29, 30] showed that the Even-Mansour cipher and the three-round Feistel networks, classically proven secure if their underlying building blocks are ideal, were broken in polynomial time. This exponential speedup, the first concerning symmetric cryptography, was obtained thanks to Simon’s algorithm [40] for recovering a Boolean hidden shift. Later on, more results have been obtained in this setting, with more generic constructions broken [24, 31], and an exponential acceleration of slide attacks, which target ciphers with a self-similar structure. Versions of these attacks [6] for constructions with modular additions use Kuperberg’s algorithm [27], allowing a better than quadratic speed-up. All these attacks, however, run in the model of superposition queries, which models a quantum adversary having some inherently quantum access to the primitives attacked. As such, they do not give any improvement when the adversary only has classical access.

Stated differently, the attacks in the Q1 model are particularly relevant due to their impact on current data communication technology. However, the quantum algorithms that have been exploited for building attacks in the Q1 model are very limited and have not allowed more than a quadratic speed-up. The most used algorithm is the simple quantum exhaustive search with Grover’s algorithm. A possible direction is the collision finding algorithm that is often said to achieve “$2^{n/3}$ complexity” versus $2^{n/2}$ classically. However, even in this direction, there are several debatable points; basic quantum algorithms for finding collisions have massive quantum hardware requirements [9]. There is a quantum-hardware-friendly variant [12], but then the time complexity becomes suboptimal.

In summary, attacks using Simon’s algorithm could achieve a very low complexity but could only be applied in the Q2 model, a very strong model. In contrast, attacks in the Q1 model are practically more relevant, but for now the obtained speed-ups were not surprising.

Another model to consider when designing quantum attacks is whether the attacker has or not a big amount of quantum memory available. Small quantum computers seem like the most plausible scenario, and therefore attacks needing a polynomial amount of qubits are more practically relevant. Therefore, the most realistic scenario is Q1 with small quantum memory.

Our Main Contribution. The breakthrough we present in this paper is the first application of Simon’s algorithm [40] in the Q1 model, which requires significantly less than $\mathcal {O}\left( 2^{n/2} \right)$ classical queries and offline quantum computations, only with $\mathsf {poly}(n)$ qubits, and no qRAM access (where n is the size of the secret). Namely, we remove the superposition queries in previous attacks. The new idea can be applied to a long list of ciphers and modes of operation. Let us illustrate the impact of our attacks by focusing on two applications:

The first application is the key recovery on the Even-Mansour construction, which is one of the simplest attacks using Simon’s algorithm. Besides the polynomial time attacks in the Q2 model, Kuwakado and Morii also developed an attack in the Q1 model with $\mathcal {O}\left( 2^{n/3} \right)$ classical queries, quantum computations, qubits, and classical memory [30]. The extension of this Q1 attack by Hosoyamada and Sasaki [23] recovers the key with $\mathcal {O}\left( 2^{3n/7} \right)$ classical queries, $\mathcal {O}\left( 2^{3n/7} \right)$ quantum computations, polynomially many qubits and $\mathcal {O}\left( 2^{n/7} \right)$ classical memory (to balance classical queries and quantum computations). Our attack in the Q1 model only uses polynomially many qubits, yet only requires $\mathcal {O}\left( 2^{n/3} \right)$ classical queries, $\mathcal {O}\left( n^3 2^{n/3} \right)$ quantum computations and $\mathsf {poly}(n)$ classical memory.

The second application is the key recovery on the FX-construction $\mathrm {FX}_{k,k_{in},k_{out}}$, which computes a ciphertext c from a plaintext p by $c \leftarrow E_{k}(p \oplus k_{in}) \oplus k_{out}$, where E is a block cipher, k is an m-bit key and $k_{in},k_{out}$ are two n-bit keys. Leander and May proposed an attack in the Q2 model with $\mathcal {O}\left( n 2^{m/2} \right)$ superposition queries, $\mathcal {O}\left( n^3 2^{m/2} \right)$ quantum computations, $\mathsf {poly}(n)$ qubits and $\mathsf {poly}(n)$ classical memory [31].¹ They combined Simon’s algorithm and Grover’s algorithm in a clever way, while it became inevitable to make queries in an adaptive manner. For the Q1 model, the meet-in-the-middle attack [23] can recover the key with $\mathcal {O}\left( 2^{3(m+n)/7} \right)$ complexities. Our results can improve the previous attacks in two directions. One is to reduce the amount of superposition queries in the Q2 model to the polynomial order and convert the adaptive attack to a non-adaptive one. The other is to completely remove the superposition queries. The comparison of previous quantum attacks and our attacks on Even-Mansour and the FX construction is shown in Table 1. Other interesting complexity trade-offs are possible, as shown in detail in Sects. 4 and 5.

Table 1. Previous and new quantum attacks on Even-Mansour and FX, assuming that $m = \mathcal {O}\left( n \right)$.

Our New Observation. Here we describe our new algorithm used in the Q1 model with the Even-Mansour construction as an example. Recall that the encryption $E_{k_1,k_2}$ of the Even-Mansour construction is defined as $E_{k_1,k_2}(x) = P(x \oplus k_1) \oplus k_2$, where P is a public permutation and $k_1,k_2 \in \{0,1\}^n$ are the secret keys. Roughly speaking, our attack guesses (2n/3)-bit of $k_1$ (denoted by $k^{(2)}_1$ in Fig. 1) by using the Grover search, and checks if the guess is correct by applying Simon’s algorithm to the remaining (n/3)-bit of $k_1$ (denoted by $k^{(1)}_1$ in Fig. 1). If we were in the Q2 model, we could recover $k_1$ using the technique by Leander and May [31] in time $\tilde{\mathcal {O}}(2^{n/3})$. However, their technique is not applicable in the Q1 setting since quantum queries are required.

Our core observation that realizes the above idea in the Q1 model is that, we can judge whether a function $f \oplus g$ has a period (i.e., we can apply Simon’s algorithm) without any quantum query to g, if we have the quantum state ${\left| {\psi _g}\right\rangle } := \left( \sum _{x} {\left| {x}\right\rangle }{\left| {g(x)}\right\rangle } \right) ^{\otimes cn}$ (c is a small constant): If we have the quantum state ${\left| {\psi _g}\right\rangle }$, then we can make the quantum state ${\left| {\psi _{f\oplus g}}\right\rangle } := \left( \sum _{x} {\left| {x}\right\rangle }{\left| {(f \oplus g)(x)}\right\rangle } \right) ^{\otimes cn}$ by making $\mathcal {O}\left( n \right)$ quantum queries to f. Once we obtain ${\left| {\psi _{f \oplus g}}\right\rangle }$, by applying the Hadamard operation $H^{\otimes n}$ to each ${\left| {x}\right\rangle }$ register, we obtain the quantum state

$$\left( \sum _{x_1,u_1} (-1)^{u_1 \cdot x_1} {\left| {u_{1}}\right\rangle }{\left| {(f \oplus g)(x_{1})}\right\rangle } \right) \otimes \cdots \otimes \left( \sum _{x_{cn},u_{cn}} (-1)^{u_{cn} \cdot x_{cn}} {\left| {u_{cn}}\right\rangle }{\left| {(f \oplus g)(x_{cn})}\right\rangle } \right) $$

Then, roughly speaking, $\mathrm {dim}(\mathrm {Span}(u_1,\dots ,u_{cn})) < n$ always holds if $f \oplus g$ has a secret period s, while $\mathrm {dim}(\mathrm {Span}(u_1,\dots ,u_{cn})) = n$ holds with a high probability if $f \oplus g$ does not have any period. Since the dimension of the vector space can be computed in time $\mathcal {O}\left( n^3 \right)$, we can judge if $f \oplus g$ has a period in time $\mathcal {O}\left( n^3 \right)$. Note that we can reconstruct the quantum data ${\left| {\psi _g}\right\rangle }$ after judging whether $(f \oplus g)$ has a period (with some errors) by appropriately performing uncomputations, which help us use these procedures as a subroutine without measurement in other quantum algorithms.

For the Even-Mansour construction, we set $g : \{0,1\}^{n/3} \rightarrow \{0,1\}^n$ by $g(x) := E_{k_1,k_2}(x \Vert 0^{2n/3})$. Then we can make the quantum state ${\left| {\psi _g}\right\rangle }$ by classically querying x to g for all $x \in \{0,1\}^{n/3}$, which requires $2^{n/3}$ classical queries. After obtaining the state ${\left| {\psi _g}\right\rangle }$, we guess $k^{(2)}_1$. Suppose that here our guess is $k' \in \{0,1\}^{2n/3}$. We define $f_{k'} : \{0,1\}^{n/3} \rightarrow \{0,1\}^n$ by $f_{k'}(x) := P(x \Vert k')$. Then, roughly speaking, our guess is correct if and only if the function $f_{k'} \oplus g$ has a period $k^{(1)}_1$. Thus we can judge whether the guess is correct without quantum queries to g, by using our technique described above. Since $k^{(2)}_1$ can be guessed in time $\tilde{\mathcal {O}}(2^{n/3})$ by using the Grover search, we can recover the keys by making $\mathcal {O}(2^{n/3})$ classical queries and $\tilde{\mathcal {O}}(2^{n/3})$ offline quantum computations.

Fig. 1.

Idea of our Q1 attack on the Even-Mansour construction.

We will show how we can similarly attack the FX construction in the Q1 model, by guessing additional key bits (see Fig. 2).

Fig. 2.

Idea of our Q1 attack on the FX construction.

Moreover, our attack idea in the Q1 model can also be used to reduce the number of quantum queries of attacks in the Q2 model. The Leander and May’s attack on the FX construction in the Q2 model [31] guesses the m-bit key k of the FX construction $\mathrm {FX}_{k,k_{in},k_{out}}$ and checks whether the guess is correct by using Simon’s algorithm, which requires $\mathcal {O}(2^{m/2})$ online quantum queries and $\tilde{\mathcal {O}}(2^{m/2})$ offline quantum computations. Roughly speaking, the guess $k'$ for the key k is correct if and only if $(f_{k'} \oplus g)(x)$ has the secret period $k_{in}$, where $f_{k'}(x) = E_{k'}(x)$ and $g(x) = \mathrm {FX}_{k,k_{in},k_{out}}(x)$. In the Q2 model, we can make the quantum state ${\left| {\psi _g}\right\rangle } = \left( \sum _x {\left| {x}\right\rangle }{\left| {g(x)}\right\rangle }\right) ^{\otimes cn}$ by making $\mathcal {O}\left( n \right)$ quantum queries to g. Thus, by our new attack idea described above, we can break the FX construction with $\mathcal {O}\left( n \right)$ online quantum queries and $\tilde{\mathcal {O}}(2^{m/2})$ offline quantum computations, which exponentially improves the attack by Leander and May from the viewpoint of quantum query complexity.

This exponential improvement on the quantum query complexity is due to the separation of offline queries and online computations: In the previous attack on the FX construction in the Q2 model by Leander and May, we have to do online queries and offline computations alternately in each iteration of the Grover search. Thus the number of online quantum queries becomes exponential in the previous attack. On the other hand, in our new attack, the online queries (i.e., the procedures to make the quantum state ${\left| {\psi _g}\right\rangle }$) are completely separated from offline computations. This enables us to decrease the number of quantum queries exponentially, while we still need exponentially many offline computations.

Paper Organization. Section 2 gives preliminaries. Section 3 describes our main algorithms. Section 4 shows applications of our algorithms in the Q2 model. Section 5 shows applications of our algorithms in the Q1 model. Section 6 discusses further applications of our algorithm. Section 7 concludes the paper.

2 Preliminaries

In this section, we introduce some quantum computing notions and review Simon’s and Grover’s algorithms. We refer to [36] for a broader presentation.

2.1 The Quantum Circuit Model

It has become standard in the cryptographic literature to write quantum algorithms in the circuit model, which is universal for quantum computing. We only consider the logical level of quantum circuits, with logical qubits, not their implementation level (which requires physical qubits, quantum error-correction, etc). Although it is difficult to estimate the cost of a physical implementation which does not yet exist, we can compare security levels as quantum operation counts in this model. For example, Grover search of the secret key for AES-128 is known to require approximately $2^{64}$ quantum evaluations of the cipher, and $2^{84}$ quantum operations [21].

Qubits and Operations. A quantum circuit represents a sequence of quantum operations, denoted as quantum gates, applied to a set of qubits. An individual qubit is a quantum object whose state is an element of a two-dimensional Hilbert space, with basis ${\left| {0}\right\rangle }, {\left| {1}\right\rangle }$ (analogs of the classical logical 0 and 1). Hence, the state is described as a linear combination of ${\left| {0}\right\rangle }, {\left| {1}\right\rangle }$ with complex coefficients (a superposition). We add to this a normalization condition: $\alpha {\left| {0}\right\rangle } + \beta {\left| {1}\right\rangle }$ is such that $|\alpha |^2 + |\beta |^2 = 1$. When it is clear from context, we dismiss common normalization factors.

When n qubits are given, the computational basis has $2^n$ vectors, which are all n-bit strings. The qubits start in a state ${\left| {0}\right\rangle }$, for example a fixed spin or polarization. The sequence of quantum gates that is applied modifies the superposition, thanks to constructive and destructive interferences. In the end, we measure the system, and obtain some n-bit vector in the computational basis, which we expect to hold a meaningful result.

All computations are (linear) unitary operators of the Hilbert space, and as such, are reversible (this holds for the individual gates, but also for the whole circuit). In general, any classical computation can be made reversible (and so, implemented as a quantum circuit) provided that one uses sufficiently many ancilla qubits (which start in the state ${\left| {0}\right\rangle }$ and are brought back to ${\left| {0}\right\rangle }$ after the computation). Generally, on input ${\left| {x}\right\rangle }$, we can perform some computation, copy the result to an output register using CNOT gates, and uncompute (perform backwards the same operations) to restore the initial state of the ancilla qubits. Uncomputing a unitary U corresponds to applying its adjoint operator $U^*$.

By the principle of deferred measurements, any measure that occurs inside the quantum circuit can be deferred to the end of the computation.

Quantum Oracles. Many quantum algorithms require an oracle access. The difference they make with classical algorithms with this respect is that classical oracles (e.g. cryptographic oracles such as a cipher with unknown key) are queried “classically”, with a single value, while quantum oracles are unitary operators. We consider oracle calls of the type:

which XOR their output value to an output register (ensuring reversibility). If we consider that ${\left| {y}\right\rangle }$ starts in the state ${\left| {0}\right\rangle }$, then f(x) is simply written here. If the function f can be accessed through $O_f$, we say it has superposition oracle access.

Quantum RAM. Additionally to the use of “plain” quantum circuits with universal quantum computation, many algorithms require quantum random-access, or being able to access at runtime a superposition of memory cells. This is a strong requirement, since this requires an extensive quantum hardware (the qRAM) and a huge architecture that is harder to build than a quantum circuit with a limited number of qubits. Shor’s algorithm, Simon’s algorithm, Grover’s algorithm do not require qRAM, if their oracle calls do not either, contrary to, e.g., the algorithm for quantum collision search of [9], whose optimal speedup can be realized only by using massive qRAM.

Our algorithm has no such requirement, which puts it on the same level of practicality as Grover’s algorithm for attacking symmetric primitives.

2.2 Simon’s Algorithm

Simon’s algorithm [40] gives an exponential speedup on the following problem.

Problem 1 (Simon’s problem)

Suppose given access to a function $f~: \{0,1\}^n \rightarrow \{0,1\}^n$ that is either injective, or such that there exists $s \in \{0,1\}^n$ with:

$$ \forall x, f(x) = f(y) \iff y = x \text { or } y = x \oplus s, $$

then find $\alpha$.

In other words, the function f has a hidden Boolean period. It is also easy to extend this algorithm to a hidden Boolean shift, when we want to decide whether two functions f and g are such that $g(x) = f(x \oplus s)$ for all x. In practice, f can fall in any set X provided that it can be represented efficiently, but in our examples, we will consider functions producing bit strings.

Solving this problem with classical oracle access to f requires $\varOmega \left( 2^{n/2} \right)$ queries, as we need to find a collision of f (or none, if there is no hidden period). Simon [40] gives an algorithm which only requires $\mathcal {O}\left( n \right)$ superposition queries. We fix $c \ge 1$ a small constant to ensure a good success probability and repeat cn times Algorithm 1.

We obtain either:

• a list of cn random values of y;

• a list of cn random values of y in the hyperplane $y \cdot s = 0$.

It becomes now easy to test whether s exists or not. If it doesn’t, the system of equations obtained has full rank. If it does exist, we can find it by solving the system. Judging whether there exists such an s and actually finding it (if it exists) can be done in time $\mathcal {O}\left( n^3 \right)$ by Gaussian elimination.

Simon’s Algorithm in Cryptography. This algorithm has been used in many attacks on modes of operation and constructions where recovering a secret requires to find a hidden shift between two functions having bit-string inputs. Generally, the functions to which Simon’s algorithm is applied are not injective, and random collisions can occur. But a quick analysis (as done e.g. in [24]) shows that even in this case, a mild increase of the constant c will increase the success probability to a sufficient level. To be precise, the following proposition holds.

Proposition 1

(Theorem 2 in [24]). Suppose that $f : \{0,1\}^n \rightarrow X$ has a period $s \ne 0^n$, i.e., $f(x\oplus s) = f(x)$ for all $x \in \{0,1\}^n$, and satisfies

$$\begin{aligned} \max _{t \ne \{s,0^n\}} \mathop {\Pr }\limits _x\left[ f(x \oplus t) = f(x) \right] \le \frac{1}{2}. \end{aligned}$$

(1)

When we apply Simon’s algorithm to f, it returns s with a probability at least $1 - 2^n \cdot (3/4)^{cn}$.

2.3 Grover’s Algorithm

Grover’s algorithm [22] allows a quadratic speedup on classical exhaustive search. Precisely, it solves the following problem:

Problem 2 (Grover’s problem)

Consider a set X (the “search space”) whose elements are represented on $\lceil \log _2(|X|) \rceil$ qubits, such that the uniform superposition $\sum _{x \in X} {\left| {x}\right\rangle }$ is computable in $\mathcal {O}\left( 1 \right)$ time. Given oracle access to a function $f~: X \rightarrow \{0,1\}$ (the “test”), find $x \in X$ such that $f(x) = 1$.

Classically, if there are $2^t$ preimages of 1, we expect one to be found in time (and oracle accesses to f) $\mathcal {O}\left( |X|/2^t \right)$. Quantumly, Grover’s algorithm finds one in time (and oracle accesses to $O_f$) $\widetilde{\mathcal {O}}\left( \sqrt{|X| / 2^t} \right)$. In particular, if there is one preimage of 1, the running time is $\widetilde{\mathcal {O}}\left( \sqrt{|X|} \right)$. If the superposition oracle for f uses a ancilla qubits, then Grover’s algorithm requires $a + \lceil \log _2(|X|) \rceil$ qubits only.

Grover’s algorithm works first by producing the superposition $\sum _{x \in |X|} {\left| {x}\right\rangle }$. It applies $\widetilde{\mathcal {O}}\left( \sqrt{|X| / 2^t} \right)$ times an operator which, by querying $O_f$ “moves” some amplitude towards the preimages of 1.

3 Simon’s Algorithm with Asymmetric Queries

In this section, we introduce a problem that can be seen as a general combination of Simon’s and Grover’s problems, and that will be solved by an according combination of algorithmic ideas. The problem has many cryptographic applications, and it will be at the core of our improved Q2 and Q1 time-memory-data tradeoffs.

Problem 3 (Asymmetric Search of a Period)

Let $F~: \{0,1\}^m \times \{0,1\}^n \rightarrow \{0,1\}^\ell$ and $g~:\{0,1\}^n \rightarrow \{0,1\}^\ell$ be two functions. We consider F as a family of functions indexed by $\{0,1\}^m$ and write $F(i,\cdot ) = f_i(\cdot )$. Assume that we are given quantum oracle access to F, and classical or quantum oracle access to g. (In the Q1 setting, g will be a classical oracle. In the Q2 setting, g will be a quantum oracle.)

Assume that there exists exactly one $i \in \{0,1\}^m$ such that $f_{i} \oplus g$ has a hidden period, i.e.: $\forall x \in \{0,1\}^n, f_{i_0}(x) \oplus g(x) = f_{i_0}(x \oplus s) \oplus g(x \oplus s)$ for some s. Furthermore, assume that:

$$\begin{aligned} \max _{ \begin{array}{c} i \in \{0,1\}^m \setminus \{i_0\} \\ t \in \{0,1\}^{n} \setminus \{0^{n}\} \end{array}} \mathop {\Pr }\limits _{ x \leftarrow \{0,1\}^{n}}\left[ (f_i \oplus g)(x \oplus t)= (f_i \oplus g)(x) \right] \le \frac{1}{2} \end{aligned}$$

(2)

Then find $i_0$ and s.

In our cryptographic applications, g will be a keyed function such that adversaries have to make online queries to evaluate it, while F will be a function such that adversaries can evaluate it offline. For example, the problem of recovering keys of the FX construction $\mathrm {FX}_{k,k_{in},k_{out}}(x) = E_k(x \oplus k_{in}) \oplus k_{out}$ can be regarded as a simple cryptographic instantiation of Problem 3: Set $g(x) := \mathrm {FX}_{k,k_{in},k_{out}}(x)$ and $F(i,x) := E_{i}(x)$. Then, roughly speaking, the function $f_i \oplus g$ has a period $k_{in}$ if $k=i$, whereas it does not have any period if $i \ne k$ and Condition (2) holds. Thus we can know whether $i=k$ by checking whether $f_i \oplus g$ has a period.

Justification of Condition (2). We added Condition (2) in Problem 3 because the problem would be much harder to solve if we do not suppose any condition on $f_i$. Such assumptions are standard in the litterature of quantum attacks using Simon’s algorithm (see for example [24, Sections 2.2 and 4] or [4, Section 3]). This is reasonable for cryptographic applications, as a block cipher is expected to behave like a random permutation, which makes the functions we construct in our applications behave like random functions. This assumption is made in [24, 31], and such functions satisfy Condition (2) with an overwhelming probability. Moreover, as remarked in [24], a cryptographic construction that fails to satisfy Condition (2) would exhibit some poor differential properties which could be used for cryptanalysis.

3.1 Existing Techniques to Solve the Problem

Here we explain existing algorithms to solve Problem 3 in both the Q1 model and the Q2 model, with the algorithms to recover keys of the FX construction as an example. Note that we consider the situation in which exponentially many qubits are not available.

The Model Q1. In the Q1 model, when we are allowed to make only classical queries to $g := \mathrm {FX}_{k,k_{in},k_{out}}$, there exists a Q1 algorithm to attack the FX construction that uses a kind of meet-in-the-middle technique [23]. However, it does not make use of the exponential speed-up of Simon’s algorithm, and its time complexity and query complexity is $\mathcal {O}\left( 2^{3(n+m)/7} \right)$ (for $m \le 4n/3$).

The Model Q2. Problem 3 can be solved with $\mathcal {O}\left( n 2^{m/2} \right)$ superposition queries to $F(i,x)=E_i(x)$ and $g(x)=\mathrm {FX}_{k,k_{in},k_{out}}(x)$, and in time $\mathcal {O}\left( n^3 2^{m/2} \right)$, using the Grover-meet-Simon algorithm of [31]. Indeed, we make a Grover search on index $i \in \{0,1\}^m$. When testing whether a guess i for the key k is correct, we perform $\mathcal {O}\left( n \right)$ queries to F and $\mathcal {O}\left( n \right)$ queries to g, to check whether $f_i \oplus g$ has a hidden period, hence whether the guess i is correct. Moreover, since superposition access to F and g is allowed, we can test i in superposition as well.

3.2 An Algorithm for Asymmetric Search of a Shift

Here we describe our new algorithms to solve Problem 3. We begin with explaining two observations on the Grover-meets-Simon algorithm in the Q2 model described in Sect. 3.1, and how to improve it. Then we describe how to use the idea to make a good algorithm to solve Problem 3 in the Q1 model.

Two Observations. Our first observation is that, when doing the Grover search over i for Problem 3, each time a new i is tested, a new function $f_i$ is queried. But, in contrast, the function g is always the same. We would like to take this asymmetry into account, namely, to make less queries to g since it does not change. This in turn has many advantages: queries to g can become more costly than queries to $f_i$.

Our second observation is that, for each $i \in I$, once we have a superposition ${\left| {\psi _g}\right\rangle } = \bigotimes ^{cn} \left( \sum _{x \in \{0,1\}^n} {\left| {x}\right\rangle } {\left| {g(x)}\right\rangle } \right)$ and given a quantum oracle access to $f_i$, we can obtain the information if $f_i \oplus g$ has a period or not without making queries to g.

From ${\left| {\psi _g}\right\rangle }$, we can make the state ${\left| {\psi _{f_i \oplus g}}\right\rangle } = \bigotimes ^{cn} \left( \sum _{x \in \{0,1\}^n} {\left| {x}\right\rangle }\right. \left. {\left| {f_i(x) \oplus g(x)}\right\rangle } \right)$ by making queries to $f_i$. By applying usual Simon’s procedures on ${\left| {\psi _{f_i \oplus g}}\right\rangle }$, we can judge if $f_i \oplus g$ has a period. Moreover, by appropriately performing uncomputations, we can recover ${\left| {\psi _g}\right\rangle }$ (with some errors) and reuse it in other procedures.

With these observations in mind, below we give an intuitive description of our algorithm $\mathsf{Alg\text {-}PolyQ2}$ to solve Problem 3 in the Q2 model (we name our algorithm $\mathsf{Alg\text {-}PolyQ2}$ because it will be applied to make Q2 attacks with polynomially many online queries in later sections). The main ideas of $\mathsf{Alg\text {-}PolyQ2}$ are separating an online phase and offline computations, and iteratively reusing the quantum data ${\left| {\psi _g}\right\rangle }$ obtained by the online phase.

AlgorithmAlg-PolyQ2(informal)

• 1. Online phase: Make cn quantum queries to g to prepare ${\left| {\psi _g}\right\rangle }$.

• 2. Offline computations: Run the Grover search over $i \in \{0,1\}^m$. For each fixed i, run a testing procedure $\mathsf{test}$ such that: (a) $\mathsf{test}$ checks if i is a good element (i.e., $f_i \oplus g$ has a period) by using ${\left| {\psi _g}\right\rangle }$ and making queries to $f_i$, and (b) after checking if i is good, appropriately performs uncomputations to recover the quantum data ${\left| {\psi _g}\right\rangle }$.

A formal description of $\mathsf{Alg\text {-}PolyQ2}$ is given in Algorithm 2. We fix a constant $c \ge 1$, to be set later depending on the probability of error wanted.

We show how to implement the testing procedure $\mathsf {test}$ in Algorithm 3 without any new query to g, using only exactly 2cn superposition queries to F. To write this procedure clearly, we consider a single function f in input, but remark that it works as well if f is a superposition of $f_i$ (as will be the case when $\mathsf {test}$ is called as the oracle of a Grover search).

In practice, Algorithm 3 works up to some error (see Remark 1), which is amplified at each iteration of Algorithm 2. The complexity and success probability (including the errors) of $\mathsf{Alg\text {-}PolyQ2}$ can be analyzed as below.

Proposition 2

Suppose that m is in $\mathcal {O}\left( n \right)$. Let c be a sufficiently large constant.² Consider the setting of Problem 3: let $i_0 \in \{0,1\}^m$ be the good element such that $g \oplus f_{i_0}$ is periodic and assume that (2) holds. Then $\mathsf{Alg\text {-}PolyQ2}$ finds $i_0$ with a probability in $\varTheta (1)$ by making $\mathcal {O}\left( n \right)$ quantum queries to g and $\mathcal {O}\left( n2^{m/2} \right)$ quantum queries to F.³ The offline computation (the procedures excluding the ones to prepare the state ${\left| {\psi _g}\right\rangle }$) of $\mathsf{Alg\text {-}PolyQ2}$ is done in time $\mathcal {O}\left( (n^3+nT_F)2^{m/2} \right)$, where $T_F$ is the time required to evaluate F once.

See Section A in the full version of the paper [5] for a proof.

Remark 1

Intuitively, the error produced in each iteration of Algorithm 3 is bounded by the maximum, on i, of: $p^{(i)}:= \Pr \left[ \dim (\mathrm{Span}(u_1,\dots ,u_{cn})) < n\right] ,$ when $u_1,\dots ,u_{cn}$ are produced with Simon’s algorithm, i.e. the probability that Simon’s algorithm returns the incorrect answer “$f_i \oplus g$ is periodic” even though $f_i \oplus g$ is not periodic. From condition (2), we can show that $p^{(i)} \le 2^{(n+1)/2} ((1 + \frac{1}{2}) / 2)^{cn/2}$ holds (see Lemma 1 in the full version of the paper [5]).

Remark 2

$\mathsf{Alg\text {-}PolyQ2}$ finds the index i such that $f_i \oplus g$ has a period, but does not return the actual period of $f_i \oplus g$. However, we can find the actual period of $f_i \oplus g$ (after finding i with $\mathsf{Alg\text {-}PolyQ2}$) by applying Simon’s algorithm to $f_i \oplus g$.

Summary. With $\mathsf{Alg\text {-}PolyQ2}$, we realize an “asymmetric” variant of Simon’s algorithm, in which we store a “compressed” database for a single function g, which is not modified (up to some errors) while we test whether another function f has a hidden shift with g, or not. An immediate application of this algorithm will be to achieve an exponential improvement of the query complexity of some Q2 attacks on symmetric schemes. Indeed, in the context where Simon’s algorithm and Grover’s algorithm are combined, it may be possible to perform the queries to the secret-key cryptographic oracle only once, and so, to lower the query complexity to $\mathcal {O}\left( n \right)$.

3.3 Asymmetric Search with Q1 Queries

In $\mathsf{Alg\text {-}PolyQ2}$, (online) queries to g and (offline) queries to F are separated, and only cn superposition queries to g are made. Hence another tradeoff is at our reach, which was not possible when g was queried in each Grover iteration: removing superposition queries to g completely.

This requires now to query the whole codebook for g to prepare the quantum state ${\left| {\psi _g}\right\rangle }$. Once ${\left| {\psi _g}\right\rangle }$ is built, the second offline phase runs in exactly the same way. Building ${\left| {\psi _g}\right\rangle }$ costs roughly $2^n$ time (and classical queries), while going through the search space for f takes $2^{m/2}$ iterations (and quantum queries to F). We call our new algorithm in the Q1 model $\mathsf{Alg\text {-}ExpQ1}$ because it will be applied to make Q1 attacks with exponentially many online queries in later sections. The optimal point arrives when $m = 2n$.

Below we give an intuitive description of our algorithm $\mathsf{Alg\text {-}ExpQ1}$ to solve Problem 3 in the Q1 model. As described above, the difference between $\mathsf{Alg\text {-}ExpQ1}$ and $\mathsf{Alg\text {-}PolyQ2}$ is the online phase to prepare ${\left| {\psi _g}\right\rangle }$.

AlgorithmAlg-ExpQ1(informal)

• 1. Online phase: Make $2^n$ classical queries to g and prepare the state ${\left| {\psi _g}\right\rangle }$.

• 2. Offline computations: Run the Grover search over $i \in \{0,1\}^m$. For each fixed i, run a testing procedure $\mathsf{test}$ such that: (a) $\mathsf{test}$ checks if i is a good element (i.e., $f_i \oplus g$ has a period) by using ${\left| {\psi _g}\right\rangle }$ and making queries $f_i$, and (b) after checking if i is good, appropriately perform uncomputations to recover the quantum data ${\left| {\psi _g}\right\rangle }$.

A formal description of $\mathsf{Alg\text {-}ExpQ1}$ is the same as that of $\mathsf{Alg\text {-}PolyQ2}$ (Algorithm 2) except that we make $2^n$ classical queries to g to prepare the quantum state ${\left| {\psi _g}\right\rangle }$. See Algorithm 4 for formal description of the online phase.

The complexity and success probability (including the errors) of $\mathsf{Alg\text {-}ExpQ1}$ can be analyzed as below.

Proposition 3

Suppose that m is in $\mathcal {O}\left( n \right)$. Let c be a sufficiently large constant.⁴ Consider the setting of Problem 3: let $i_0 \in \{0,1\}^m$ be the good element such that $g \oplus f_{i_0}$ is periodic and assume that (2) holds. Then $\mathsf{Alg\text {-}ExpQ1}$ finds $i_0$ with a probability in $\varTheta (1)$ by making $\mathcal {O}\left( 2^n \right)$ classical queries to g and $\mathcal {O}\left( n2^{m/2} \right)$ quantum queries to F.⁵ The offline computation (the procedures excluding the ones to prepare the state ${\left| {\psi _g}\right\rangle }$) of $\mathsf{Alg\text {-}ExpQ1}$ is done in time $\mathcal {O}\left( (n^3+nT_F)2^{m/2} \right)$, where $T_F$ is the time required to evaluate F once.

A proof is given in Section A in the full version of the paper [5].

Finding Actual Periods. The above algorithm $\mathsf{Alg\text {-}ExpQ1}$ returns the index $i_0$ such that $f_{i_0} \oplus g$ has a period, but does not return the actual period. Therefore, if we want to find the actual period of $f_{i_0} \oplus g$ after finding $i_0$, we have to apply Simon’s algorithm to $f_{i_0} \oplus g$ again. Now we can make only classical queries to g, though, we can use the same idea with $\mathsf{Alg\text {-}ExpQ1}$ to make an algorithm $\mathsf{SimQ1}$ that finds the period of $f_{i_0} \oplus g$. Again, let c be a positive integer constant.

Algorithm $\mathsf{SimQ1}$

• 1. Make $2^n$ classical queries to g and prepare the quantum state ${\left| {\psi _g}\right\rangle }$.

• 2. Make cn quantum queries to $f_{i_0}$ to obtain the quantum state ${\left| {\psi _{f_{i_0} \oplus g}}\right\rangle } = \bigotimes ^{cn} \left( \sum _x {\left| {x}\right\rangle } {\left| {f_{i_0}(x) \oplus g (x)}\right\rangle } \right)$.

• 3. Apply $H^{\otimes n}$ to each ${\left| {x}\right\rangle }$ register to obtain the state

  $$\bigotimes ^{cn} \left( \sum _{x,u} (-1)^{x \cdot u}{\left| {u}\right\rangle } {\left| {f_{i_0}(x) \oplus g (x)}\right\rangle } \right) .$$

• 4. Measure all ${\left| {u}\right\rangle }$ registers to obtain cn vectors $u_1,\dots ,u_{cn}$.

• 5. Compute the dimension d of the vector space V spanned by $u_1,\dots ,u_{cn}$. If $d \ne n-1$, return $\perp$. If $d = n-1$, compute the vector $v \ne 0^n \in \{0,1\}^n$ that is orthogonal to V.

Obviously the probability that the above algorithm $\mathsf{SimQ1}$ returns the period of $f_{i_0} \oplus g$ is the same as the probability that the original Simon’s algorithm returns the period, under the condition that cn quantum queries can be made to the function $f_{i_0} \oplus g$. Thus, from Proposition 1, the following proposition holds.

Proposition 4

Suppose that $f_{i_0} \oplus g$ has a period $s \ne 0^n$ and satisfies

$$\begin{aligned} \max _{t \ne \{s,0^n\}} \mathop {\Pr }\limits _x\left[ (f_{i_0} \oplus g)(x \oplus t) = (f_{i_0} \oplus g)(x) \right] \le \frac{1}{2}. \end{aligned}$$

(5)

Then $\mathsf{SimQ1}$ returns s with a probability at least $1 - 2^n \cdot (3/4)^{cn}$ by making $\mathcal {O}\left( 2^n \right)$ classical queries to g and cn quantum queries to $f_{i_0}$. The offline computation of $\mathsf{SimQ1}$ (the procedures excluding the ones to prepare the state ${\left| {\psi _g}\right\rangle }$) runs in time $\mathcal {O}\left( n^3 + nT_f \right)$, where $T_f$ is the time required to evaluate $f_{i_0}$ once.

Proposition 5

(Concrete cost estimates). In practice, for Propositions 2 and 3, $c\simeq m/\left( n\log _2(4/3)\right)$ is sufficient.

Proof

We need to have $4\lfloor \pi / \left( 4\arcsin \left( 2^{-m/2}\right) \right) \rfloor 2^{(n+1)/2}(3/4)^{cn/2}< 1/2$.

In practice, $\arcsin (x) \simeq x$ and the rounding has a negligible impact. Hence, we need that $m/2+(n+1)/2+\log _2(\pi ) + \log _2(3/4)cn/2 < -1$.

This reduces to $c > \log _2(4/3)^{-1}\left( m+3+2\log _2(\pi )\right) /n \simeq m/\left( n\log _2(4/3)n\right)$.

Remark 3

If $m = n$, this means $c\simeq 2.5$, and if $m = 2n$, $c \simeq 5$.

4 Q2 Attacks on Symmetric Schemes with Reduced Query Complexity

This section shows that our new algorithm $\mathsf{Alg\text {-}PolyQ2}$ can be used to construct Q2 attacks on various symmetric schemes. By using $\mathsf{Alg\text {-}PolyQ2}$ we can exponentially reduce the number of quantum queries to the keyed oracle compared to previous Q2 attacks, with the same time cost.

In each application, we consider that one evaluation of each primitive (e.g., a block cipher) can be done in time $\mathcal {O}\left( 1 \right)$, for simplicity. For our practical estimates, we use the cost of the primitive as our unit, and consider that it is greater than the cost of solving the linear equation system. In addition, we assume that key lengths of n-bit block ciphers are in $\mathcal {O}\left( n \right)$, which is the case for usual block ciphers.

4.1 An Attack on the FX Construction

Here we show a Q2 attack on the FX construction. As described in Sect. 3, the FX construction builds an n-bit block cipher $\mathrm {FX}_{k,k_{in},k_{out}}$ with $(2n+m)$-bit keys ($k_{in},k_{out} \in \{0,1\}^n$ and $k \in \{0,1\}^m$) from another n-bit block cipher $E_{k}$ with m-bit keys as

$$\begin{aligned} \mathrm {FX}_{k,k_{in},k_{out}} (x) := E_k(x \oplus k_{in}) \oplus k_{out}. \end{aligned}$$

(6)

This construction is used to obtain a block cipher with long ($(2n+m)$-bit) keys from another block cipher with short (m-bit) keys. Roughly speaking, in the classical setting, the construction is proven to be secure up to $\mathcal {O}\left( 2^{(n+m)/2} \right)$ queries and computations if the underlying block cipher is secure [26].

Concrete block ciphers such as DESX, proposed by Rivest in 1984 and analyzed in [26], PRINCE [8], and PRIDE [1] are designed based on the FX construction. To estimate security of these block ciphers against quantum computers, it is important to study quantum attacks on the FX construction.

As briefly explained in Sect. 3, the previous Q2 attack by Leander and May [31] breaks the FX construction by making $\mathcal {O}\left( n2^{m/2} \right)$ quantum queries, and its time complexity is $\mathcal {O}\left( n^32^{m/2} \right)$.

Application of Our Algorithm Alg-PolyQ2. Below we show that, by applying our algorithm $\mathsf{Alg\text {-}PolyQ2}$, we can recover keys of the FX construction with only $\mathcal {O}\left( n \right)$ quantum queries. The time complexity of our attack remains $\mathcal {O}\left( n^32^{m/2} \right)$, which is the same as Leander and May’s.

Attack Idea. As explained in Sect. 3, the problem of recovering the keys k and $k_{in}$ of the FX construction $F_{k,k_{in},k_{out}}$ can be reduced to Problem 3: Define $F : \{0,1\}^m \times \{0,1\}^n \rightarrow \{0,1\}^n$ and $g : \{0,1\}^n \rightarrow \{0,1\}^n$ by

$$ \begin{matrix} F(i,x) &{}=&{} E_i(x) \oplus E_i(x\oplus 1)\\ g(x) &{}=&{} \mathrm {FX}_{k,k_{in}, k_{out}}(x)\oplus \mathrm {FX}_{k,k_{in}, k_{out}}(x\oplus 1).\end{matrix} $$

Then

$$\begin{aligned} f_k(x) \oplus g(x) = f_k(x \oplus k_{in}) \oplus g(x \oplus k_{in}) \end{aligned}$$

(7)

holds, i.e., $f_k \oplus g(x)$ has a period $k_{in}$ (note that $f_k(x) = F(k,x)$). If E is a secure block cipher and $E_i$ is a random permutation for each i, intuitively, $f_{i} \oplus g$ does not have any period for $i \ne k$. Thus the problem of recovering k and $k_{in}$ is reduced to Problem 3 and we can apply our algorithm $\mathsf{Alg\text {-}PolyQ2}$. Formally, the attack procedure is as follows.

Attack Description

• 1. Run $\mathsf{Alg\text {-}PolyQ2}$ for the above F and g to recover k.

• 2. Apply Simon’s algorithm to $f_k \oplus g$ to recover $k_{in}$.

• 3. Compute $k_{out} = E_k(0^n) \oplus \mathrm {FX}_{k,k_{in}, k_{out}}(0^n)$.

Next we give a complexity analysis of the above attack.

Analysis. We assume that $m = \mathcal {O}\left( n \right)$, which is the case for usual block ciphers. If E is a secure block cipher and $E_i$ is a random permutation for each $i \in \{0,1\}^m$, we can assume that $f_k \oplus g = E_k \oplus E_k(\cdot \oplus 1) \oplus \mathrm {FX}_{k,k_{in}, k_{out}} \oplus \mathrm {FX}_{k,k_{in}, k_{out}}(\cdot \oplus 1)$ is far from periodic for all $i \ne k$, and that assumption (2) in Problem 3 holds.

Hence, by Proposition 2, $\mathsf{Alg\text {-}PolyQ2}$ recovers k with a high probability by making $\mathcal {O}\left( n \right)$ quantum queries to g and $\mathcal {O}\left( n2^{m/2} \right)$ quantum queries to F, which implies that k is recovered only with $\mathcal {O}\left( n \right)$ quantum queries made to $\mathrm {FX}_{k,k_{in},k_{out}}$, and in time $\mathcal {O}\left( n^3 2^{m/2} \right)$. (Note that one evaluation of g (resp., F) can be done by $\mathcal {O}\left( 1 \right)$ evaluations of $\mathrm {FX}_{k,k_{in},k_{out}}$ (resp., E)).

From Proposition 1, the second step can be done with $\mathcal {O}\left( n \right)$ quantum queries in time $\mathcal {O}\left( n^3 \right)$. It is obvious that the third step can be done efficiently.

In summary, our attack recovers the keys of the FX construction with a high probability by making $\mathcal {O}\left( n \right)$ quantum queries to the (keyed) online oracle, and it runs in time $\mathcal {O}\left( n^32^{m/2} \right)$.

Applications to DESX, PRINCE and PRIDE. DESX [26] has a 64-bit state, two 64-bit whitening key and one 56-bit inner key. From Propositions 2 and 5, we can estimate that our attack needs roughly 135 quantum queries and $2^{29}$ quantum computations of the cipher circuit.

PRINCE [8], and PRIDE [1] are two ciphers using the FX construction with a 64-bit state, a 64-bit inner key and two 64-bit whitening keys. Hence, from Propositions 2 and 5, we can estimate that our attack needs roughly 155 quantum queries and $2^{33}$ quantum computations of the cipher circuit.

5 Q1 Attacks on Symmetric Schemes

This section shows that our new algorithm $\mathsf{Alg\text {-}ExpQ1}$ can be used to construct Q1 attacks on various symmetric schemes, with a tradeoff between online classical queries, denoted below by D, and offline quantum computations, denoted below by T.

All the algorithms that we consider run with a single processor, but they can use quantum or classical memories, whose amount is respectively denoted by Q (number of qubits) and M. Again, we consider that one evaluation of each primitive (e.g. a block cipher) can be done in time $\mathcal {O}\left( 1 \right)$, for simplicity, and we assume that key lengths of n-bit block ciphers are in $\mathcal {O}\left( n \right)$.

5.1 Tradeoffs for the Even-Mansour Construction

The Even-Mansour construction [19] is a simple construction to make an n-bit block cipher $E_{k_1,k_2}$ from an n-bit public permutation P and two n-bit keys $k_1,k_2$ (see Fig. 3). The encryption $E_{k_1,k_2}$ is defined as $E_{k_1,k_2}(x) := P(x \oplus k_1) \oplus k_2$, and the decryption is defined accordingly.

In the classical setting, roughly speaking, the Even-Mansour construction is proven secure up to $\mathcal {O}\left( 2^{n/2} \right)$ online queries and offline computations [19]. In fact there exists a classical attack with tradeoff $TD=2^n$, which balances at $T=D=2^{n/2}$ [15].

Fig. 3.

The Even-Mansour construction.

Previous Q1 Attacks on the Even-Mansour Construction. Kuwakado and Morii gave a Q1 attack that recovers keys of the Even-Mansour construction with $\mathcal {O}\left( 2^{n/3} \right)$ classical queries and qubits, and $\mathcal {O}\left( 2^{n/3} \right)$ offline quantum computations [30]. Their attack is based on a claw-finding algorithm by Brassard et al. [9], and gives the tradeoff $T^2 D=2^n$, with additional $Q=D$ qubits. The balanced point $2^{n/3}$ is significantly smaller than the classical balanced point $2^{n/2}$. However, if we want to recover keys with this attack in time $T \ll 2^{n/2}$, we need an exponential amount of qubits.

Main Previous Attacks with Polynomial Qubits. The best classical attacks allow a trade-off of $D \cdot T= 2^n$ (see [18] for other trade-offs involving memory). With Grover we could recover the keys with a complexity of $2^{n/2}$ and 2 plaintexts-ciphertext pairs, $(P_1,C_1)$ and $(P_2,C_2)$, by performing an exhaustive search over the value of $k_1$ that would verify $P(P_1\oplus k_1)\oplus P(P_2\oplus k_1)= C_1\oplus C_2$. In [23], Hosoyamada and Sasaki also gave a tradeoff $D \cdot T^6=2^{3n}$ for $D \le 2^{3n/7}$ under the condition that only polynomially many qubits are available, by using the multi-target preimage search by Chailloux et al. [12]. D and T are balanced at $D=T=2^{3n/7}$, which is smaller than the classical balanced point $2^{n/2}$. The attack uses only polynomially many qubits, but requires $M=D^{1/3} = 2^{n/7}$ classical memory. At the balanced point, this still represents an exponentially large storage. Note that this is the only previous work that recover keys in time $T \ll 2^{n/2}$ with polynomially many qubits.

Table 2. Tradeoffs for Q1 attacks on the Even-Mansour construction. In this table we omit to write order notations, and ignore polynomial factors in the first and last rows.

Application of Alg-ExpQ1. We explain how to use our algorithm $\mathsf{Alg\text {-}ExpQ1}$ to attack the Even-Mansour construction. The tradeoff that we obtain is $T^2 \cdot D = 2^{n}$, the same as the attack by Kuwakado and Morii above. It balances at $T=D=2^{n/3}$, but we use only $\mathsf {poly}(n)$ qubits and $\mathsf {poly}(n)$ classical memory. See Table 2 for comparison of attack complexities under the condition that $\mathsf {poly}(n)$ many qubits are available.

Attack Idea. The core observation of Kuwakado and Morii’s polynomial-time attack in the Q2 model [30] is that the n-bit secret key $k_1$ is the period of the function $E_{k_1,k_2}(x) \oplus P(x)$, and thus Simon’s algorithm can be applied if quantum queries to $E_{k_1,k_2}$ are allowed. The key to this exponential speed up (compared to the classical attack) is to exploit the algebraic structure of $E_{k_1,k_2}$ (the hidden period of the function) with Simon’s algorithm.

On the other hand, the previous Q1 (classical query) attacks described above use only generic multi-target preimage search algorithms that do not exploit any algebraic structures. Hence being able to exploit the algebraic structure in the Q1 model should give us some advantage.

Our algorithm $\mathsf{Alg\text {-}ExpQ1}$ realizes this idea. It first makes classical online queries to emulate the quantum queries required by Simon’s algorithm (the g-database above) and then runs a combination of Simon’s and Grover’s algorithms offline (Grover search is used to find the additional m-bit secret information). A naive way to attack in the Q1 model would be to immediately combine Kuwakado and Morii’s Q2 attack with $\mathsf{Alg\text {-}ExpQ1}$. However, we would have to query the whole classical codebook to emulate quantum queries, which is too costly (and there is no Grover search step).

Our new attack is as follows: We divide the n-bit key $k_1$ in $k^{(1)}_1$ of u bits and $k^{(2)}_1$ of ${n-u}$ bits and apply Simon’s algorithm to recover $k^{(1)}_1$, while we guess $k^{(2)}_1$ by the Grover search (see Fig. 4). Then, roughly speaking, $\mathsf{Alg\text {-}ExpQ1}$ recovers the key by making $D=2^u$ classical queries and $T=2^{(n-u)/2}$ offline Grover search iterations (note that the offline computation cost for Simon’s algorithm is $\mathsf {poly}(n)$ and we ignore polynomial factors here for simplicity), which yields the tradeoff $D \cdot T^2 = 2^n$, only with $\mathsf {poly}(n)$ qubits and $\mathsf {poly}(n)$ classical space.

Fig. 4.

Idea of our Q1 attack on the Even-Mansour construction.

Attack Description. Here we give the description of our Q1 attack. Let u be an integer such that $0 \le u \le n$. Define $F : \{0,1\}^{n-u} \times \{0,1\}^u \rightarrow \{0,1\}^n$ by

$$\begin{aligned} F(i,x) = P(x\Vert i), \end{aligned}$$

(8)

and define $g : \{0,1\}^u \rightarrow \{0,1\}^n$ by $g(x) = E_{k_1,k_2}(x\Vert 0^{n-u}).$

Note that $F(k^{(2)}_1,x) \oplus g(x)$ has the period $k^{(1)}_1$ since $F(k^{(2)}_1,x) \oplus g(x) = P(x\Vert k^{(2)}_1) \oplus P((x\oplus k^{(1)}_1) \Vert k^{(2)}_1) \oplus k_2$. Our attack is described as the following procedure:

• 1. Run $\mathsf{Alg\text {-}ExpQ1}$ for the above F and g to recover $k^{(2)}_1$.

• 2. Recover $k^{(1)}_1$ by applying $\mathsf{SimQ1}$ to $f_{k^{(2)}_1}$ and g.

• 3. Compute $k_2 = E_{k_1,k_2}(0^n) \oplus P(k_1)$.

Analysis. Below we assume that u is not too small, e.g., $u \ge n / \log _2 n$. This assumption is not an essential restriction since, if u is too small, then the complexity of the first step becomes almost the same as the Grover search on $k_1$, which is not of interest.

If P is a random permutation, we can assume that $f_i \oplus g = P( \cdot || i) \oplus E_{k_1,k_2}(\cdot || 0^{n-u})$ is far from periodic for all $i \ne k^{(2)}_1$, and that assumption (2) in Problem 3 holds.

Hence, by Proposition 3, $\mathsf{Alg\text {-}ExpQ1}$ in Step 1 recovers $k^{(2)}_1$ with a high probability by making $\mathcal {O}\left( 2^u \right)$ classical queries to g and the offline computation of $\mathsf{Alg\text {-}ExpQ1}$ runs in time $\mathcal {O}\left( n^32^{(n-u)/2} \right)$. Here, notice that one evaluation of g (resp. F) can be done in $\mathcal {O}\left( 1 \right)$ evaluations of $E_{k_1,k_2}$ (resp. P). In addition, from Proposition 4, $\mathsf{SimQ1}$ in Step 2 recovers $k^{(1)}_1$ with a high probability by making $\mathcal {O}\left( 2^u \right)$ classical queries to g and the offline computation of $\mathsf{Alg\text {-}ExpQ1}$ runs in time $\mathcal {O}\left( n^3 \right)$. Step 3 requires $\mathcal {O}\left( 1 \right)$ queries to $E_{k_1,k_2}$ and $\mathcal {O}\left( 1 \right)$ offline computations.

In summary, our attack recovers keys of the Even-Mansour construction with a high probability by making $D=\mathcal {O}\left( 2^u \right)$ classical queries to $E_{k_1,k_2}$ and doing $T=\mathcal {O}\left( n^3 2^{(n-u)/2} \right)$ offline computations, which balances at $T = D = \tilde{\mathcal {O}}(2^{n/3})$. By construction of $\mathsf{Alg\text {-}ExpQ1}$ and $\mathsf{SimQ1}$, our attack uses $\mathsf {poly}(n)$ qubits and $\mathsf {poly}(n)$ classical memory.

Applications to Concrete Instances. The Even-Mansour construction is a commonly used cryptographic construction. The masks used in Even-Mansour are often derived from a smaller key, which can make a direct key-recovery using Grover’s algorithm more efficient. This is for example the case in the CAESAR candidate Minalpher [38]. In general, we need to have a secret key of at least two thirds of the state size for our attack to beat the exhaustive search.

The Farfalle construction [2] degenerates to an Even-Mansour construction if the input message is only 1 block long (Fig. 5). Instances of this construction use variable states and key sizes. The Kravatte instance [2] has a state size of 1600 bits, and a key size between 256 and 320 bits, which leads to an attack at a whopping cost of $2^{533}$ data and time, while the direct key exhaustive seach would cost at most $2^{160}$. Xoofff [16] has a state size of 384 bits and a key size between 192 and 384 bits. Our attack needs $2^{128}$ data, which is exactly the data limit of Xoofff. Hence, it is relevant if the key size is greater than 256.

Fig. 5.

One-block Farfalle.

5.2 Tradeoffs for the FX Construction

The FX construction [26] $\mathrm {FX}_{k,k_{in},k_{out}}$, computes a ciphertext c from a plaintext p by $c \leftarrow E_{k}(p \oplus k_{in}) \oplus k_{out}$, where E is a block cipher, k is an m-bit key and $k_{in},k_{out}$ are two n-bit keys. In the classical setting, there exists a classical attack with tradeoff $TD=2^{n+m}$, which balances at $T=D=2^{(n+m)/2}$ (see, for example, [17] for more details and memory trade-offs).

Previous Q1 Attacks on the FX Construction. Applying Grover as we did before on Even-Mansour on the keys $k_{in}$ and k, we can recover the keys with only two pairs of plaintext-ciphertext and a time complexity of $2^{(n+m)/2}$, while only needing a polynomial number of qubits.

In [23], Hosoyamada and Sasaki proposed a tradeoff $D \cdot T^6=2^{3(n+m)}$ for $D \le \min \{2^n,2^{3(n+m)/7}\}$ with a polynomial amount of qubits, by using the multi-target preimage search by Chailloux et al. [12]. The balance occurs at $D=T=2^{3(n+m)/7}$ (if $m \le 4n/3$), which is smaller than the classical balanced point $2^{(n+m)/2}$. The attack requires $M=D^{1/3}$ classical memory, thus the attack still requires exponentially large space at the balanced point. This was the only Q1 attack with time $T \ll 2^{(n+m)/2}$ and a polynomial amount of qubits.

Application of Alg-ExpQ1. We explain how to apply our algorithm $\mathsf{Alg\text {-}ExpQ1}$ to the FX construction. Our new tradoff is $T^2 \cdot D = 2^{n+m}$ for $D \le 2^n$, which balances at $T=D=2^{(n+m)/3}$ (for $m \le 2n$), using only $\mathsf {poly}(n)$ qubits and $\mathsf {poly}(n)$ classical memory. See Table 3 for comparison of attack complexities under the condition that only $\mathsf {poly}(n)$ qubits are available.

Table 3. Tradeoffs for Q1 attacks on the FX construction. In this table we omit to write order notations, and ignore polynomial factors in the first and last rows.

Attack Idea. Recall that, in the Q1 attack on the Even-Mansour construction in Sect. 5.1, we divided the first key $k_1$ to two parts $k^{(1)}_1$ and $k^{(2)}_1$ and applied Simon’s algorithm to $k^{(1)}_1$ while we performed Grover search on $k^{(2)}_1$.

In a similar manner, for the FX construction $\mathrm {FX}_{k,k_{in},k_{out}}$ we divide the n-bit key $k_{in}$ in $k^{(1)}_{in}$ of u bits and $k^{(2)}_{in}$ of $(n-u)$ bits. We apply Simon’s algorithm to recover $k^{(1)}_{in}$ while we perform Grover search on k in addition to $k^{(2)}_{in}$ (see Fig. 6).

Fig. 6.

Idea of our Q1 attack on the FX construction.

Then, roughly speaking, by applying $\mathsf{Alg\text {-}ExpQ1}$ we can recover the key by making $D=2^u$ classical queries and $T=2^{(n-u)/2}$ offline Grover iterations (note that the offline computation cost for the Simon’s algorithm is $\mathsf {poly}(n)$ and we ignore polynomial factors here for simplicity), which yields the tradeoff $D \cdot T^2 = 2^{(n+m)}$ for $D \le 2^n$, with only $\mathsf {poly}(n)$ qubits and $\mathsf {poly}(n)$ classical memories.

Attack Description. Here we give the description of our Q1 attack. Let u be an integer such that $0 \le u \le n$. Define $F : \{0,1\}^{m+(n-u)} \times \{0,1\}^u \rightarrow \{0,1\}^n$ by

$$\begin{aligned} F(i\Vert j,x) = E_i(x\Vert j) (i \in \{0,1\}^{m}, j \in \{0,1\}^{n-u}), \end{aligned}$$

(9)

and define $g : \{0,1\}^u \rightarrow \{0,1\}^n$ by $g(x) = \mathrm {FX}_{k,k_{in},k_{out}}(x\Vert 0^{n-u}).$

Note that $F(k \Vert k^{(2)}_{in},x) \oplus g(x)$ has the period $k^{(1)}_{in}$ since $F(k \Vert k^{(2)}_{in},x) \oplus g(x) = E_k(x\Vert k^{(2)}_{in}) \oplus E_k((x\oplus k^{(1)}_{in}) \Vert k^{(2)}_{in}) \oplus k_{out}$. Our attack procedure runs as follows:

• 1. Run $\mathsf{Alg\text {-}ExpQ1}$ for the above F and g to recover k and $k^{(2)}_{in}$.

• 2. Recover $k^{(1)}_{in}$ by applying $\mathsf{SimQ1}$ to $f_{k \Vert k^{(2)}_{in}}$ and g.

• 3. Compute $k_{out} = \mathrm {FX}_{k,k_{in},k_{out}}(0^n) \oplus E_k(k_{in})$.

Analysis. We assume that $m = \mathcal {O}\left( n \right)$, which is the case for usual block ciphers. In the same way as in the analysis for the attack on the Even-Mansour construction in Sect. 5.1, if E is a (pseudo) random permutation family and u is not too small (e.g. $u \ge n / \log _2 n$), we observe that the assumption (2), rephrased as:

$$\begin{aligned}&\max _{t \in \{0,1\}^n \setminus \{0^n\}} \mathop {\Pr }\limits _{x \in \{0,1\}^n} \left[ E_i\left( x||j\right) \oplus E_i\left( x \oplus t || j \right) \oplus E_k\left( x \oplus k^{(1)}_{in} || k^{(2)}_{in} \right) \right. \nonumber \\&\qquad \qquad \qquad \qquad \quad \quad \left. \oplus E_k\left( x \oplus t \oplus k^{(1)}_{in} || k^{(2)}_{in} \right) = 0 \right] \le 1/2 \end{aligned}$$

(10)

holds for all $(i,j) \ne (k,k^{(2)}_1)$ with overwhelming probability.

This again implies that the claims of Propositions 3 and 4 hold for $\mathsf{Alg\text {-}ExpQ1}$ in Step 1 and $\mathsf{SimQ1}$ in Step 2, respectively.

Thus our attack recovers keys of the FX construction with a high probability by making $D=\mathcal {O}\left( 2^u \right)$ classical queries to $\mathrm {FX}_{k,k_{in},k_{out}}$ and doing $T=\mathcal {O}\left( n^32^{(m+n-u)/2} \right)$ offline computations for $D \le 2^n$, which balances at $T = D = \tilde{\mathcal {O}}(2^{(n+m)/3})$ if $m \le 2n$. Our attack uses only $\mathsf {poly}(n)$ qubits and $\mathsf {poly}(n)$ classical memory by construction of $\mathsf{Alg\text {-}ExpQ1}$ and $\mathsf{SimQ1}$.

Application to Concrete Instances. DESX [26] has a 64-bit state, two 64-bit whitening key and one 56-bit inner key. From Propositions 2 and 5, we can estimate that our attack needs roughly $2^{42}$ classical queries and $2^{40}$ quantum computations of the cipher circuit.

PRINCE [8], and PRIDE [1] are two ciphers using the FX construction with a 64-bit state, a 64-bit inner key and two 64-bit whitening keys. Hence, from Propositions 2 and 5, we can estimate that our attack needs roughly $2^{45}$ quantum queries and $2^{43}$ quantum computations of the cipher circuit.

We can also see some encryption modes as an instance of the FX construction. This is for example the case of the XTS mode [32], popular for disk encryption. It is generally used with AES-256 and two whitening keys that depend on the block number and another 256-bit key. Hence, with the full codebook of one block, we can obtain the first key and the value of the whitening keys of the corresponding block. Once the first key is known, the second can easily be brute-forced from a few known plaintext-ciphertext couples in other blocks.

Adiantum [14] is another mode for disk encryption that uses a variant of the FX construction with AES-256 and Chacha. There is however one slight difference: the FX masking keys are added with a modular addition instead of a xor. The FX construction is still vulnerable [6], but we will need to use Kuperberg’s algorithm [28] instead of Simon’s algorthm. As before, with the full codebook on one block, we can recover the AES and Chacha keys in a time slightly larger than $2^{256}$.

5.3 Other Applications

Chaskey. The lightweight MAC Chaskey [33] is very close to an Even-Mansour construction (see Fig. 7). Since the last message block ($m_2$ in Fig. 7) is XORed to the key $K_1$, we can immediately apply our Q1 attack and recover $K_1$ and the value of the state before the xoring of the last message block. As $\pi$ is a permutation easy to invert, this allows to retrieve K. The Chaskey round function applies on 128 bits. It contains 16 rounds with 4 modular additions on 32 bits, 4 XORs on 32 bits and some rotations. With a data limit of $2^{48}$, as advocated in the specification, our attack would require roughly $2^{(128 - 48)/2} \times 2^{19} = 2^{59}$ quantum gates, where the dominant cost is solving the 80-dimensional linear system inside each iteration of Grover’s algorithm.

Fig. 7.

Two-block Chaskey example.

Sponges. Our attack can be used on sponges if there is an input injected on a fixed state. In general, it has two drawbacks: the nonce has to be fixed, and the cost of the attack is at least $2^{c/2}$ with c the capacity of the sponge, which is often the classical security parameter. However, there are some cases where our attack is of interest.

In particular, our attack needs a set of values that contains an affine space. If a nonce was injected the same way the messages are, then we only need to know the encryptions of identical messages, with a set of nonces that fills an affine space. Nonce-respecting adversaries are generally allowed to choose the nonce, but here, the mere assumption that the nonce is incremented for each message (which is the standard way nonces are processed in practice) is sufficient: A set of $2^k$ consecutive values contains an affine space of $(\mathbb {Z}/(2))^{k-1}$.

This is the case in the Beetle mode of lightweight authenticated encryption [13], whose initialization phase is described as $(K_1 \oplus N) \Vert K_2 \mapsto f((K_1 \oplus N) \Vert K_2)$, where $K_1, N \in \{0,1\}^r$, $K_2 \in \{0,1\}^c$, and f is a $(r+c)$-bit permutation (Fig. 8).

Here, the nonce is directly added to the key $K_1$, but as the key has the same length as the state, the attack would still work if the nonce was added after the first permutation. In Beetle[Light+], the rate is $r = 64$ bits and the capacity $c = 80$ bits. The rate is sufficiently large to embed 48 varying bits for the nonce; in that case, by making $2^{48}$ classical queries and $2^{48}$ Grover iterations, we can recover the secret $K_1 || K_2$. In Beetle[Secure+], $r = c = 128$ bits. We can recover $K_1 || K_2$ with $2^{85}$ messages and Grover iterations.

Fig. 8.

Beetle state initialization.

6 Discussion

In this section, we discuss on the application of our attack idea to related-key attacks, to some slide attacks, and to an extension of Problem 3. See also Section B in the full version of the paper [5] for discussions on adaptive attacks and non-adaptive attacks.

6.1 Related Keys

Consider a block cipher $E_k$ with a key and block size of n bits. In the related-key setting, as introduced in [41], we are not only allowed to make chosen plaintext or ciphertext queries to a secret-key oracle hiding k, but also to query $E_{k \oplus \ell } (m)$ for any n-bit difference $\ell$ and message m. Classically, this is a very powerful model, but it becomes especially meaningful when the block cipher is used inside a mode of operation (e.g. a hash function) in which key differences can be controlled by the attacker. It is shown in [41] that a secret key recovery in this model can be performed in $2^{n/2}$ operations, as it amounts to find a collision between some query $E_{k\oplus \ell } (m)$ and some offline computation $E_{\ell '}(m)$ (we can use more than a single plaintext m to ensure an overwhelming success probability).

Rötteler and Steinwandt [37] noticed that, if a quantum adversary has superposition access to the oracle that maps $\ell$ to $E_{k \oplus \ell } (m)$, it can mount a key-recovery in polynomial time using Simon’s algorithm. Indeed, one can define a function:

$$ f(x) = E_{k \oplus x}(m) \oplus E_x(m) $$

which has k as hidden period, apply Simon’s algorithm and recover k. This attack works for any block cipher, even ideal. In contrast, in the Q2 quantum attacker model, we know that some constructions are broken, but it does not seem to be the case for all of them.

With our algorithm $\mathsf{Alg\text {-}ExpQ1}$, we are able to translate this related-key superposition attack into an attack where the related-key oracle is queried only classically, but the attacker has quantum computing power. We write $k = k_1 || k_2$ where $k_1$ has n/3 bits and $k_2$ has 2n/3 bits. We query $E_{(k_1 || k_2) \oplus (\ell _1 || 0)} (m)$ for a fixed m and all n/3-bit differences $\ell _1$. Then we perform a Grover search on $k_2$. The classical security level in presence of a related-key oracle of this form, which is $2^{n/2}$, is reduced quantumly to $2^{n/3}$. This shows that the transition to a quantum setting has an impact on the related-key security even if the oracle remains classical.

As a consequence, we could complete the security claims of the 16-round version of the block cipher Saturnin [10], a submission to the ongoing NIST lightweight cryptography competition⁶. The authors of Saturnin gave security claims against quantum attackers meeting the best generic attacks. No claims were given regarding the $Q_1$ model for related-key attacks. Our result gives the best generic quantum related-key attack on ideal block ciphers without superposition queries, and sets the level of security that should be expected from a block cipher in this setting: the key can be recovered in quantum time $\widetilde{\mathcal {O}}\left( 2^{n/3} \right)$ for a block cipher of n bits (and using $2^{n/3}$ classical related-key queries). The corresponding security level for Saturnin$_{16}$, which has blocks of 256 bits, lies at $2^{256/3} = 2^{85}$: we can say that in the $Q_1$ related-key setting, Saturnin$_{16}$ should have no attack with time complexity lower than $2^{85}$.

Fig. 9.

Iterated-FX cipher.

6.2 Slide Attacks

Quantum slide attacks are a very efficient quantum counterpart of the classical slide attacks [3]. They have been introduced in [24], with a polynomial-time attack on 1-round self-similar ciphers. In many cases, our algorithm does not improve these attacks, because they are already too efficient and do not rely on a partial exhaustive search. Still, some of them use a partial exhaustive search. This is the case of the slide attack against 2 round self-similar ciphers of [31] and the slide attacks against whitened Feistels of [7].

For example, we can see a 2 round self-similar cipher as an example of iterated FX cipher, as in Fig. 9. Define functions $p_i$, $F_i$, and g as

$$ p_i((b,x))=\left\{ \begin{matrix} (0,E_i(x)) &{}\text {if b = 0} \\ (1,x) &{} \text {if b = 1}\end{matrix}\right. ,\quad F_i((b,x), y) = \left\{ \begin{matrix} y\oplus x &{}\text {if b = 0} \\ E_i(y) \oplus x &{} \text {if b = 1}\end{matrix}\right. , $$

and $g((b,x)) = \text {iFX}(x)$. We have the property that $\text {iFX}(E_{k_2}(x\oplus k_1))\oplus (x\oplus k_1) = E_{k_2}(\text {iFX}(x))\oplus x$. Hence, we have the hidden period $(1,k_1)$ in the function $f_{k_2}((b,x)) = F_{k_2}\left( (b,x),g(p_{k_2}(b,x))\right)$. To apply our attack, we need to compute $\sum _{x,b}{\left| {x}\right\rangle }{\left| {b}\right\rangle }{\left| {f_i((b,x))}\right\rangle }$ from the state $\sum _x{\left| {x}\right\rangle }{\left| {\text {iFX}(x)}\right\rangle }$. We first need to add one qubit to obtain $\sum _x{\left| {x}\right\rangle }({\left| {0}\right\rangle }+{\left| {1}\right\rangle }){\left| {\text {iFX}(x)}\right\rangle }$. Then, conditioned on the second register to be 0, we transform x into $E_i^{-1}(x)$. Next, conditioned on the second register to be 1, we transform $\text {iFX}(x)$ into $E_i(\text {iFX}(x))$. Finally, we add the first register to the third. Hence, we can apply our attack, and retrieve $k_1$ and $k_2$ using $\mathcal {O}\left( |k_1| \right)$ queries and $\mathcal {O}\left( |k_1|^32^{|k_2|/2} \right)$ time, assuming $|k_1| = \varOmega (|k_2|)$.

The above problem of recovering keys can be generalized as the following problem, which can be solved by the same strategy as above.

Problem 4 (Constructing and Finding a Hidden Period)

Let $g~:\{0,1\}^n \rightarrow \{0,1\}^\ell$ be a function, $i\in I$, $p_i : \{0,1\}^n \rightarrow \{0,1\}^n$ be a permutation and $F_i : \{0,1\}^n \times \{0,1\}^\ell \rightarrow \{0,1\}^\ell$ be a function such that $F_i(x,\cdot )$ is a permutation. Assume that there exists $i_0 \in I$ such that $f_{i_0}(x) = F_{i_0}\left( x,g(p_{i_0}(x))\right)$ has a period, i.e.: $\forall x \in \{0,1\}^n, f_{i_0}(x) = f_{i_0}(x\oplus s)$ for some s. Assume that we are given quantum oracle access to $F_i$ and $p_i$ and classical or quantum oracle access to g. (In the Q1 setting, g will be a classical oracle. In the Q2 setting, g will be a quantum oracle.) Then find $i_0$ and s.

This problem assumes that g is a keyed function, and that we can reversibly transform (x, g(x)) into a couple $(y,f_i(y))$, with $f_i$ a periodic function if $i = i_0$. We can see this transformation as a generalization of the CCZ equivalence [11], where the function mapping the graph of g and the graph of $f_i$ do not need to be an affine function. There may also be more than one solution (in which case we just want to find one), or there may be none, just as Grover’s algorithm can handle cases with many expected solutions, or distinguish whether there is a solution or not. Note that Problem 3 is a special case of the above problem, in the case where $p_i$ is the identity, and $F_i$ is only the xoring of g and another function.

7 Conclusion

In this paper, we have introduced a new quantum algorithm, in which we make use of Simon’s algorithm in an offline way. The idea of making $\mathsf {poly}(n)$ superposition queries to the oracle (with, as input, a uniform superposition), storing them as some compressed database on $n^2$ qubits, and reusing them during the iterations of a Grover search, yielded surprising results. This idea, initially targeting the query complexity of some Q2 attacks on cryptographic schemes, enabled us to find new quantum-time/classical-data tradeoffs. Our result has three consequences, each of which answers a long-standing question in post-quantum cryptography.

Simon’s Algorithm Can Be Used in an Offline Setting. We provided the first example of use of Simon’s algorithm (or more precisely, its core idea) in an offline setting, without quantum oracle queries.

Improving More Than the Time Complexity. Consider the example of our attack on the Even-Mansour construction in quantum time $\widetilde{\mathcal {O}}\left( 2^{n/3} \right)$ and classical queries $\mathcal {O}\left( 2^{n/3} \right)$. With the same number of queries, the classical attack requires $\mathcal {O}\left( 2^{2n/3} \right)$ time and $\mathcal {O}\left( 2^{n/3} \right)$ classical memory to store the queries. In our attack, we do not need this storage. To the best of our knowledge, this is the first time that a quantum Q1 attack provides a quadratic speedup while the needs of hardware are also reduced.

Q2 Attacks Make a Difference. Schemes which do not have an attack in the superposition model cannot be attacked by our algorithm. We showed that their algebraic structure, which makes the superposition attack possible, indeed made a practical difference when it came to Q1 attacks. We believe that this question needs further investigation.