Quantum Attacks without Superposition Queries: the Offline Simon’s Algorithm

Abstract

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

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

Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover’s algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure. We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.

Keywords: Simon’s algorithm, classical queries, symmetric cryptography, quantum cryptanalysis, Even-Mansour construction, FX construction.

1. Introduction

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

In symmetric cryptography, the impact of quantum computing seems, at first sight, much more limited. This is because the security of most symmetric-key schemes is not predicated on structured problems. Grover’s quantum search algorithm [GL96] speeds up by a quadratic factor exhaustive search procedures. This has led to the common saying that “doubling the key sizes” should ensure a similar level of post-quantum security.

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

The Q2 model is particularly interesting as it yields some attacks with a very low cost. Kuwakado and Morii [29, 30] showed that the Even-Mansour cipher and the three-round Feistel networks, classically proven secure if their underlying building blocks are ideal, were broken in polynomial time. This exponential speedup was obtained thanks to Simon’s algorithm [SD94] for recovering a Boolean hidden shift.

Our Main Contribution. The breakthrough we present in this paper is the first application of Simon’s algorithm [SD94] in the Q1 model, which requires significantly less than O(2^{n/2}) classical queries and offline quantum computations, only with \mathrm{poly}(n) qubits, and no qRAM access. Namely, we remove the superposition queries in previous attacks.

The first application is the key recovery on the Even-Mansour construction. Our attack in the Q1 model only uses polynomially many qubits, yet only requires O(2^{n/3}) classical queries, O(n^3 \cdot 2^{n/3}) quantum computations and \mathrm{poly}(n) classical memory.

The second application is the key recovery on the FX-construction \mathrm{FX}_{k,k_{\mathrm{in}},k_{\mathrm{out}}}, which computes a ciphertext c from a plaintext p by c \leftarrow E_k(p \oplus k_{\mathrm{in}}) \oplus k_{\mathrm{out}}, where E is a block cipher, k is an m-bit key and k_{\mathrm{in}}, k_{\mathrm{out}} are two n-bit keys.

Our New Observation. Our core observation is that we can judge whether a function f \oplus g has a period (i.e., we can apply Simon’s algorithm) without any quantum query to g, if we have the quantum state |\psi_g\rangle := (\sum_x |x\rangle |g(x)\rangle)^{\otimes cn}. This enables us to separate the online phase (preparing |\psi_g\rangle) from offline computations (the Grover search), achieving exponential improvements in query complexity.

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

2. Preliminaries

This section introduces some quantum computing notions and reviews Simon’s and Grover’s algorithms.

2.1 The Quantum Circuit Model

It has become standard in the cryptographic literature to write quantum algorithms in the circuit model, which is universal for quantum computing. We only consider the logical level of quantum circuits, with logical qubits, not their implementation level. Although it is difficult to estimate the cost of a physical implementation which does not yet exist, we can compare security levels as quantum operation counts in this model.

Qubits and Operations. A quantum circuit represents a sequence of quantum operations, denoted as quantum gates, applied to a set of qubits. An individual qubit is a quantum object whose state is an element of a two-dimensional Hilbert space, with basis |0\rangle, |1\rangle. Hence, the state is described as a linear combination \alpha|0\rangle + \beta|1\rangle with |\alpha|^2 + |\beta|^2 = 1.

Quantum RAM. Many algorithms require quantum random-access memory (qRAM). Our algorithm has no such requirement, which puts it on the same level of practicality as Grover’s algorithm for attacking symmetric primitives.

2.2 Simon’s Algorithm

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

Solving this problem with classical oracle access to f requires \Omega(2^{n/2}) queries, as we need to find a collision. Simon [SD94] gives an algorithm which only requires O(n) superposition queries. We fix c \geq 1 a small constant to ensure a good success probability and repeat cn times the quantum subroutine.

Algorithm 1 (Quantum subroutine of Simon’s algorithm): Start in the all-zero state |0\rangle|0\rangle. Apply Hadamard gates to obtain \sum_{x \in \{0,1\}^n} |x\rangle|0\rangle. Query O^f to obtain \sum_x |x\rangle|f(x)\rangle. Apply Hadamard gates and measure y. If f hides a period s, then measuring gives a random y such that y \cdot s = 0.

2.3 Grover’s Algorithm

Grover’s algorithm [GL96] allows a quadratic speedup on classical exhaustive search.

Classically, if there are 2^t preimages of 1, we expect one to be found in time O(|X|/2^t). Quantumly, Grover’s algorithm finds one in time \tilde{O}(\sqrt{|X|/2^t}). If the superposition oracle for f uses a ancilla qubits, then Grover’s algorithm requires a + \lceil \log_2(|X|) \rceil qubits only.

3. Simon’s Algorithm with Asymmetric Queries

In this section, we introduce a problem that can be seen as a general combination of Simon’s and Grover’s problems, and that will be solved by an according combination of algorithmic ideas. The problem has many cryptographic applications.

In our cryptographic applications, g will be a keyed function such that adversaries have to make online queries to evaluate it, while F will be a function such that adversaries can evaluate it offline. For example, the problem of recovering keys of the FX construction can be regarded as a simple cryptographic instantiation of Problem 3.

3.1 Existing Techniques to Solve the Problem

The model Q1. In the Q1 model, when we are allowed to make only classical queries, there exists a Q1 algorithm using a kind of meet-in-the-middle technique [HS18]. However, it does not make use of the exponential speed-up of Simon’s algorithm, and its time/query complexity is O(2^{3(n+m)/7}).

The model Q2. Problem 3 can be solved with O(n \cdot 2^{m/2}) superposition queries and in time O(n^3 \cdot 2^{m/2}), using the Grover-meet-Simon algorithm of [LM17].

3.2 An Algorithm for Asymmetric Search of a Shift

Two observations. Our first observation is that, when doing the Grover search over i for Problem 3, each time a new i is tested, a new function f_i is queried. But, in contrast, the function g is always the same. We would like to take this asymmetry into account.

Our second observation is that, for each i \in I, once we have a superposition |\psi_g\rangle = \bigotimes^{cn} \sum_{x \in \{0,1\}^n} |x\rangle|g(x)\rangle and given quantum oracle access to f_i, we can determine if f_i \oplus g has a period without making queries to g.

Algorithm Alg-PolyQ2 (informal). (1) Online phase: Make cn quantum queries to g to prepare |\psi_g\rangle. (2) Offline computations: Run the Grover search over i \in \{0,1\}^m. For each fixed i, run a testing procedure test that checks if f_i \oplus g has a period using |\psi_g\rangle and queries to f_i, then recovers |\psi_g\rangle.

Algorithm 3 (the procedure test): Starting with the g-database |\psi_g\rangle, use cn superposition queries to f to build |\psi_{f \oplus g}\rangle. Apply (H^{\otimes n} \otimes I_m)^{cn} \otimes I_1 and compute d := \dim(\mathrm{Span}(u_1, \ldots, u_{cn})). Set r := 0 if d = n and r := 1 if d < n. Then uncompute and revert |\psi_{f \oplus g}\rangle to |\psi_g\rangle using cn new queries to f.

3.3 Asymmetric Search with Q1 Queries

In Alg-PolyQ2, (online) queries to g and (offline) queries to F are separated, and only cn superposition queries to g are made. Hence another tradeoff is at our reach: removing superposition queries to g completely, by querying the whole codebook classically.

Algorithm Alg-ExpQ1 (informal). (1) Online phase: Make 2^n classical queries to g and prepare the state |\psi_g\rangle. (2) Offline computations: Run the Grover search over i \in \{0,1\}^m, using the same testing procedure as Alg-PolyQ2.

Finding actual periods. The algorithm Alg-ExpQ1 returns the index i_0 but not the actual period. A separate algorithm SimQ1 can find the period of f_{i_0} \oplus g using O(2^n) classical queries and cn quantum queries to f_{i_0}.

4. Q2 Attacks on Symmetric Schemes with Reduced Query Complexity

This section shows that Alg-PolyQ2 can be used to construct Q2 attacks on various symmetric schemes. By using Alg-PolyQ2 we can exponentially reduce the number of quantum queries to the keyed oracle compared to previous Q2 attacks, with the same time cost. We assume that one evaluation of each primitive can be done in time O(1).

4.1 An Attack on the FX Construction

The FX construction builds an n-bit block cipher \mathrm{FX}_{k,k_{\mathrm{in}},k_{\mathrm{out}}} with (2n+m)-bit keys from another n-bit block cipher E_k with m-bit keys as

Attack idea. The key recovery reduces to Problem 3 by defining F(i,x) = E_i(x) \oplus E_i(x \oplus 1) and g(x) = \mathrm{FX}_{k,k_{\mathrm{in}},k_{\mathrm{out}}}(x) \oplus \mathrm{FX}_{k,k_{\mathrm{in}},k_{\mathrm{out}}}(x \oplus 1). Then f_k \oplus g has period k_{\mathrm{in}}.

Our attack recovers the keys of the FX construction with O(n) quantum queries to the (keyed) online oracle, and runs in time O(n^3 \cdot 2^{m/2}). Applications include DESX (needing roughly 135 quantum queries and 2^{29} quantum computations), PRINCE, and PRIDE.

5. Q1 Attacks on Symmetric Schemes

This section shows that Alg-ExpQ1 can be used to construct Q1 attacks on various symmetric schemes, with a tradeoff between online classical queries, denoted D, and offline quantum computations, denoted T.

5.1 Tradeoffs for the Even-Mansour Construction

The Even-Mansour construction [EM97] is a simple construction to make an n-bit block cipher E_{k_1,k_2} from an n-bit public permutation P and two n-bit keys k_1, k_2. The encryption is defined as E_{k_1,k_2}(x) := P(x \oplus k_1) \oplus k_2. In the classical setting, it is proven secure up to O(2^{n/2}) online queries and offline computations [EM97].

Application of Alg-ExpQ1. The tradeoff we obtain is T^2 \cdot D = 2^n, which balances at T = D = \tilde{O}(2^{n/3}), using only \mathrm{poly}(n) qubits and \mathrm{poly}(n) classical memory.

Attack description. Let u be an integer with 0 \leq u \leq n. We divide k_1 into k_1^{(1)} of u bits and k_1^{(2)} of n - u bits. Define F(i,x) = P(x \| i) and g(x) = E_{k_1,k_2}(x \| 0^{n-u}). Note that F(k_1^{(2)}, x) \oplus g(x) has the period k_1^{(1)}. Our attack proceeds:

1. Run Alg-ExpQ1 for the above F and g to recover k_1^{(2)}.
2. Recover k_1^{(1)} by applying SimQ1 to f_{k_1^{(2)}} and g.
3. Compute k_2 = E_{k_1,k_2}(0^n) \oplus P(k_1).

In summary, our attack recovers keys with D = O(2^u) classical queries and T = O(n^3 \cdot 2^{(n-u)/2}) offline computations, which balances at T = D = \tilde{O}(2^{n/3}).

5.2 Tradeoffs for the FX Construction

For the FX construction \mathrm{FX}_{k,k_{\mathrm{in}},k_{\mathrm{out}}}, we divide the n-bit key k_{\mathrm{in}} into k_{\mathrm{in}}^{(1)} of u bits and k_{\mathrm{in}}^{(2)} of (n-u) bits. We apply Simon’s algorithm to recover k_{\mathrm{in}}^{(1)} while performing Grover search on k in addition to k_{\mathrm{in}}^{(2)}.

Attack description. Define F(i \| j, x) = E_i(x \| j) and g(x) = \mathrm{FX}_{k,k_{\mathrm{in}},k_{\mathrm{out}}}(x \| 0^{n-u}). Our new tradeoff is T^2 \cdot D = 2^{n+m} for D \leq 2^n, which balances at T = D = \tilde{O}(2^{(n+m)/3}) (for m \leq 2n), using only \mathrm{poly}(n) qubits.

Applications include DESX (roughly 2^{42} classical queries and 2^{40} quantum computations), PRINCE and PRIDE (roughly 2^{45} queries and 2^{43} computations), and encryption modes such as XTS and Adiantum.

5.3 Other Applications

Chaskey. The lightweight MAC Chaskey [MMV+14] is very close to an Even-Mansour construction. With a data limit of 2^{48}, the attack requires roughly 2^{59} quantum gates.

Sponges. The attack can be used on sponges if there is an input injected on a fixed state. The cost is at least 2^{c/2} with c the capacity. This applies to the Beetle mode of lightweight authenticated encryption [CDN+18]. In Beetle[Light+], with rate r = 64 bits and capacity c = 80 bits, we can recover the secret key with 2^{48} classical queries and 2^{48} Grover iterations. In Beetle[Secure+] with r = c = 128, key recovery takes 2^{85} messages and Grover iterations.

6. Discussion

This section discusses the application of the attack idea to related-key attacks, to some slide attacks, and to an extension of Problem 3.

6.1 Related Keys

Consider a block cipher E_k with a key and block size of n bits. In the related-key setting [WRH+87], we can query E_{k \oplus \ell}(m) for any n-bit difference \ell and message m. Rötteler and Steinwandt [RS15] noticed that a quantum adversary with superposition access can mount a key-recovery in polynomial time using Simon’s algorithm on the function f(x) = E_{k \oplus x}(m) \oplus E_x(m), which has k as hidden period.

With Alg-ExpQ1, we translate this into an attack where the related-key oracle is queried only classically: write k = k_1 \| k_2 where k_1 has n/3 bits and k_2 has 2n/3 bits. The classical related-key security level of 2^{n/2} is reduced quantumly to 2^{n/3}. For Saturnin (256-bit blocks), the Q1 related-key security level is at least 2^{256/3} = 2^{85}.

6.2 Slide Attacks

Some quantum slide attacks use a partial exhaustive search. This is the case of the slide attack against 2-round self-similar ciphers of [LM17] and the slide attacks against whitened Feistels of [BNS20]. The authors show how a 2-round self-similar cipher can be seen as an iterated FX cipher, and the attack can recover k_1 and k_2 using O(|k_1|) queries and O(|k_1|^3 \cdot 2^{|k_2|/2}) time.

This problem generalizes Problem 3. The transformation from the graph of g to the graph of f_i can be seen as a generalization of the CCZ equivalence [CCZ98].

7. Conclusion

In this paper, we have introduced a new quantum algorithm, in which we make use of Simon’s algorithm in an offline way. The idea of making \mathrm{poly}(n) superposition queries to the oracle, storing them as some compressed database on n^2 qubits, and reusing them during the iterations of a Grover search, yielded surprising results. This idea, initially targeting the query complexity of some Q2 attacks, enabled us to find new quantum-time / classical-data tradeoffs.

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

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

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

Appendix A: Proofs for Propositions 2 and 3

The appendix provides error and complexity analyses for Alg-ExpQ1 and Alg-PolyQ2, requiring two kinds of analyses: (1) analyses on the error of the procedure test, and (2) analyses on how much the error of test affects the success probability of the entire Grover search.

A.1 Error Analyses for the Testing Procedure test

A.2 Error Propagation Analyses for QAA

The appendix analyzes the quantum amplitude amplification (QAA) technique by Brassard et al. [BHM+02] with uncertain checking procedures. The key result is the following:

A.3 Finishing the Proofs

Appendix B: Adaptive Attacks and Non-Adaptive Attacks

The attack on the FX construction in the Q2 model is non-adaptive since the online queries required to make the state |\psi_g\rangle are just the uniform superposition of plaintexts. On the other hand, the previous Q2 attack on the construction by Leander and May is adaptive since quantum queries made to keyed online oracles are changed depending on the results for previous quantum queries. For Q1 attacks, both existing quantum attacks and the authors’ attacks are non-adaptive.

Acknowledgements

The authors thank Léo Perrin for proofreading this article and Elena Kirshanova for helpful remarks. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement n° 714294 – acronym QUASYModo).

References

• [AMD+14] Albrecht, M.R., Driessen, B., Kavun, E.B., Leander, G., Paar, C., Yalçin, T.: Block ciphers – focus on the linear layer (feat. PRIDE). In: CRYPTO 2014. LNCS, vol. 8616, pp. 57–76. Springer (2014).
• [BDH+17] Bertoni, G., Daemen, J., Hoffert, S., Peeters, M., Van Assche, G., Van Keer, R.: Farfalle: parallel permutation-based cryptography. IACR Trans. Symmetric Cryptol. 2017(4), 1–38 (2017).
• [BWD99] Biryukov, A., Wagner, D.A.: Slide attacks. In: FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer (1999).
• [Bon18] Bonnetain, X.: Quantum key-recovery on full AEZ. In: SAC 2017. LNCS, vol. 10719, pp. 394–406. Springer (2018).
• [BN18] Bonnetain, X., Naya-Plasencia, M.: Hidden shift quantum cryptanalysis and implications. In: ASIACRYPT 2018. LNCS, vol. 11272, pp. 560–592. Springer (2018).
• [BNS20] Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: On quantum slide attacks. In: SAC 2019. LNCS. Springer (2020).
• [BCG+12] Borghoff, J., Canteaut, A., Güneysu, T., Kavun, E.B., Knezevic, M., Knudsen, L.R., Leander, G., Nikov, V., Paar, C., Rechberger, C., Rombouts, P., Thomsen, S.S., Yalçin, T.: PRINCE – A low-latency block cipher for pervasive computing applications. In: ASIACRYPT 2012. LNCS, vol. 7658, pp. 208–225. Springer (2012).
• [BHM+02] Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemporary Mathematics 305, 53–74 (2002).
• [BHT98] Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: LATIN 1998. LNCS, vol. 1380, pp. 163–169. Springer (1998). doi: 10.1007/BFb0054319.
• [CDL+19] Canteaut, A., Duval, S., Leurent, G., Naya-Plasencia, M., Perrin, L., Pornin, T., Schrottenloher, A.: Saturnin: a suite of lightweight symmetric algorithms for post-quantum security (2019).
• [CCZ98] Carlet, C., Charpin, P., Zinoviev, V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography 15(2), 125–156 (1998).
• [CNS17] Chailloux, A., Naya-Plasencia, M., Schrottenloher, A.: An efficient quantum collision search algorithm and implications on symmetric cryptography. In: ASIACRYPT 2017. LNCS, vol. 10625, pp. 211–240. Springer (2017).
• [CDN+18] Chakraborti, A., Datta, N., Nandi, M., Yasuda, K.: Beetle family of lightweight and secure authenticated encryption ciphers. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(2), 218–241 (2018). doi: 10.13154/tches.v2018.i2.218-241.
• [CB18] Crowley, P., Biggers, E.: Adiantum: length-preserving encryption for entry-level processors. IACR Trans. Symmetric Cryptol. 2018(4), 39–61 (2018). doi: 10.13154/tosc.v2018.i4.39-61.
• [Dae91] Daemen, J.: Limitations of the Even-Mansour construction. In: ASIACRYPT 1991. LNCS, vol. 739, pp. 495–498. Springer (1991).
• [DHV+18] Daemen, J., Hoffert, S., Van Assche, G., Van Keer, R.: The design of Xoodoo and Xoofff. IACR Trans. Symmetric Cryptol. 2018(4), 1–38 (2018). doi: 10.13154/tosc.v2018.i4.1-38.
• [Din15] Dinur, I.: Cryptanalytic time-memory-data tradeoffs for FX-constructions with applications to PRINCE and PRIDE. In: EUROCRYPT 2015. LNCS, vol. 9056, pp. 231–253. Springer (2015).
• [DDK+14] Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Cryptanalysis of iterated Even-Mansour schemes with two keys. In: ASIACRYPT 2014. LNCS, vol. 8873, pp. 439–457. Springer (2014).
• [EM97] Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptology 10(3), 151–162 (1997). doi: 10.1007/s001459900025.
• [Gag17] Gagliardoni, T.: Quantum Security of Cryptographic Primitives. Ph.D. thesis, Darmstadt University of Technology, Germany (2017).
• [GLR+16] Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying Grover’s algorithm to AES: quantum resource estimates. In: PQCrypto 2016. LNCS, vol. 9606, pp. 29–43. Springer (2016).
• [GL96] Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC 1996. pp. 212–219. ACM (1996). doi: 10.1145/237814.237866.
• [HS18] Hosoyamada, A., Sasaki, Y.: Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. In: CT-RSA 2018. LNCS, vol. 10808, pp. 198–218. Springer (2018).
• [KLL+16] Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: CRYPTO 2016. LNCS, vol. 9815, pp. 207–237. Springer (2016).
• [KLL+16b] Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. IACR Trans. Symmetric Cryptol. 2016(1), 71–94 (2016).
• [KR96] Kilian, J., Rogaway, P.: How to protect DES against exhaustive key search. In: CRYPTO 1996. LNCS, vol. 1109, pp. 252–267. Springer (1996).
• [Kup05] Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170–188 (2005). doi: 10.1137/S0097539703436345.
• [Kup13] Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: TQC 2013. LIPIcs, vol. 22, pp. 20–34. Schloss Dagstuhl (2013).
• [KM10] Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: ISIT 2010. pp. 2682–2685. IEEE (2010).
• [KM12] Kuwakado, H., Morii, M.: Security on the quantum-type Even-Mansour cipher. In: ISITA 2012. pp. 312–316. IEEE (2012).
• [LM17] Leander, G., May, A.: Grover meets Simon – quantumly attacking the FX-construction. In: ASIACRYPT 2017. LNCS, vol. 10625, pp. 161–178. Springer (2017).
• [Mar10] Martin, L.: XTS: A mode of AES for encrypting hard disks. IEEE Security & Privacy 8(3), 68–69 (2010). doi: 10.1109/MSP.2010.111.
• [MMV+14] Mouha, N., Mennink, B., Van Herrewege, A., Watanabe, D., Preneel, B., Verbauwhede, I.: Chaskey: An efficient MAC algorithm for 32-bit microcontrollers. In: SAC 2014. LNCS, vol. 8781, pp. 306–323. Springer (2014).
• [NEM18] National Academies of Sciences, Engineering, and Medicine: Quantum Computing: Progress and Prospects. The National Academies Press, Washington, DC (2018).
• [Nat16] National Institute of Standards and Technology: Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2016).
• [NMC02] Nielsen, M.A., Chuang, I.: Quantum computation and quantum information. AAPT (2002).
• [RS15] Rötteler, M., Steinwandt, R.: A note on quantum related-key attacks. Inf. Process. Lett. 115(1), 40–44 (2015). doi: 10.1016/j.ipl.2014.08.009.
• [STA+15] Sasaki, Y., Todo, Y., Aoki, K., Naito, Y., Sugawara, T., Murakami, Y., Matsui, M., Hirose, S.: Minalpher v1.1. CAESAR competition (2015).
• [SP94] Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science. pp. 124–134. IEEE Computer Society (1994).
• [SD94] Simon, D.R.: On the power of quantum computation. In: 35th Annual Symposium on Foundations of Computer Science. pp. 116–123 (1994).
• [WRH+87] Winternitz, R.S., Hellman, M.E.: Chosen-key attacks on a block cipher. Cryptologia 11(1), 16–20 (1987). doi: 10.1080/0161-118791861749.