nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Applying Grover’s Algorithm to AES: Quantum Resource Estimates

verfasst von : Markus Grassl, Brandon Langenberg, Martin Roetteler, Rainer Steinwandt

Erschienen in: Post-Quantum Cryptography

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present quantum circuits to implement an exhaustive key search for the Advanced Encryption Standard (AES) and analyze the quantum resources required to carry out such an attack. We consider the overall circuit size, the number of qubits, and the circuit depth as measures for the cost of the presented quantum algorithms. Throughout, we focus on Clifford\(+T\) gates as the underlying fault-tolerant logical quantum gate set. In particular, for all three variants of AES (key size 128, 192, and 256 bit) that are standardized in FIPS-PUB 197, we establish precise bounds for the number of qubits and the number of elementary logical quantum gates that are needed to implement Grover’s quantum algorithm to extract the key from a small number of AES plaintext-ciphertext pairs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel RankSynd a PRNG Based on Rank Metric

Nächstes Kapitel Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation

As is common, we do not distinguish between \(T=\left( \begin{array}{cc}1&{}0\\ 0&{}\exp (i\pi /4)\end{array}\right) \) and \(T^\dagger \)-gates.

Amento, B., Rötteler, M., Steinwandt, R.: Efficient quantum circuits for binary elliptic curve arithmetic: reducing \(T\)-gate complexity. Quantum Inf. Comput. 13, 631–644 (2013)MathSciNet

Amy, M., Maslov, D., Mosca, M.: Polynomial-time \(T\)-depth optimization of Clifford\(+T\) circuits via matroid partitioning. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 33(10), 1476–1489 (2014). arXiv:1303.2042 CrossRef

Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 32(6), 818–830 (2013). For a preprint version see [4]CrossRef

Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits (2013). arXiv:quant-ph/1206.0758v3, arxiv.org/abs/1206.0758v3

Augot, D., Batina, L., Bernstein, D.J., Bos, J., Buchmann, J., Castryck, W., Dunkelmann, O., Güneysu, T., Gueron, S., Hülsing, A., Lange, T., Mohamed, M.S.E., Rechberger, C., Schwabe, P., Sendrier, N., Vercauteren, F., Yang, B.-Y.: Initial recommendations of long-term secure post-quantum systems (2015). http://pqcrypto.eu.org/docs/initial-recommendations.pdf

Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P.W., Sleator, T., Smolin, J., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995)CrossRef

Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. the user language. J. Symbolic Comput. 24, 235–265 (1997)CrossRefMathSciNetMATH

Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik 46, 493–506 (1998). arxiv:quant-ph/9605034 CrossRef

Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. AMS Contemp. Math. 305, 53–74 (2002). arxiv:quant-ph/0005055 CrossRef

10.

Brassard, G., Høyer, P., Tapp, A.: Quantum counting. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 820–831. Springer, Heidelberg (1998)CrossRef

11.

Dawson, E., Gustafson, H., Pettitt, A.N.: Strict key avalanche criterion. Australas. J. Comb. 6, 147–153 (1992)MATH

12.

Egner, S., Püschel, M.: Solving puzzles related to permutations groups. In: Proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC 1998), pp. 186–193 (1998)

13.

Fowler, A.G., Mariantoni, M., Martinis, J.M., Cleland, A.N.: Surface codes: towards practical large-scale quantum computation. Phys. Rev. A 86, 032324 (2012). arXiv:1208.0928

14.

Fowler, A.G., Stephens, A.M., Groszkowski, P.: High threshold universal quantum computation on the surface code. Phys. Rev. A 80, 052312 (2009)CrossRef

15.

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (ed.) Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), pp. 212–219. ACM (1996)

16.

Jones, N.C.: Novel constructions for the fault-tolerant Toffoli gate. Phys. Rev. A 87, 022328 (2013)CrossRef

17.

Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. arXiv:1510.05836

18.

Kepley, S., Steinwandt, R.: Quantum circuits for \({\mathbb{F}}_{2^n}\) -multiplication with subquadratic gate count. Quantum Inf. Process. 14(7), 2373–2386 (2015)CrossRefMathSciNet

19.

Konheim, A.G.: Crypt. A Primer. Wiley, Hoboken (1981)

20.

Maslov, D.: On the advantages of using relative phase Toffolis with an application tomultiple control Toffoli optimization. arXiv:1508.03273

21.

Maslov, D., Falconer, S.M., Mosca, M.: Quantum circuit placement: optimizing qubit-to-qubit interactions through mapping quantum circuits into a physical experiment. In: Proceedings of the 44th Design Automation Conference – DAC 2007, pp. 962–965. ACM (2007)

22.

Maslov, D., Mathew, J., Cheung, D., Pradhan, D.K.: On the design and optimization of a quantum polynomial-time attack on elliptic curve cryptography (2009). arXiv:0710.1093v2, arxiv.org/abs/0710.1093v2

23.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH

24.

NIST: Specification for the Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197 (2001)

25.

Reichardt, B.W.: Quantum universality by state distillation. Quantum Inf. Comput. 9, 1030–1052 (2009)MathSciNetMATH

26.

Roetteler, M., Steinwandt, R.: A note on quantum related-key attacks. Inf. Process. Lett. 115(1), 40–44 (2015)CrossRefMATH

27.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)CrossRefMathSciNetMATH

28.

Steane, A.M.: Overhead and noise threshold of fault-tolerant quantum error correction. Phys. Rev. A 68, 042322 (2003). arXiv:quant-ph/0207119

29.

Wiebe, N., Roetteler, M.: Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits. arXiv:1406.2040

30.

Yoder, T.J., Low, G.H., Chuang, I.L.: Fixed-point quantum search with an optimal number of queries. Phys. Rev. Lett. 113, 210501 (2014)CrossRef

Titel: Applying Grover’s Algorithm to AES: Quantum Resource Estimates
verfasst von: Markus Grassl
Brandon Langenberg
Martin Roetteler
Rainer Steinwandt
Verlag: Springer International Publishing
Buch: Post-Quantum Cryptography
Print ISBN: 978-3-319-29359-2

Electronic ISBN: 978-3-319-29360-8

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-29360-8_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"