SpringerLink
Log in

Applying Grover’s Algorithm to AES: Quantum Resource Estimates

  • Conference paper
  • First Online:
Post-Quantum Cryptography (PQCrypto 2016)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 9606))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    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.

References

  1. 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  Google Scholar 

  2. 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). ar**v:1303.2042

    Article  Google Scholar 

  3. 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]

    Article  Google Scholar 

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

  5. 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

  6. 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)

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  8. 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

    Article  Google Scholar 

  9. 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

    Article  Google Scholar 

  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)

    Chapter  Google Scholar 

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

    MATH  Google Scholar 

  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)

    Google Scholar 

  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). ar**v: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)

    Article  Google Scholar 

  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)

    Google Scholar 

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

    Article  Google Scholar 

  17. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. ar**v: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)

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

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

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

    Google Scholar 

  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). ar**v: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  Google Scholar 

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

    Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

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

  29. Wiebe, N., Roetteler, M.: Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits. ar**v: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)

    Article  Google Scholar 

Download references

Acknowledgments

BL and RS were supported by AFRL/RIKF Award No. FA8750-15-2-0047. RS was also supported by NATO’s Public Diplomacy Division in the framework of “Science for Peace”, Project MD.SFPP 984520. The authors thank Schloss Dagstuhl for hosting Seminar 15371, during which part of this work was done.

Author information

Authors and Affiliations

  1. Universität Erlangen-Nürnberg, Erlangen, Germany

    Markus Grassl

  2. Max Planck Institute for the Science of Light, Günther-Scharowsky-Straße 1, Bau 24, 91058, Erlangen, Germany

    Markus Grassl

  3. Florida Atlantic University, 777 Glades Road, Boca Raton, FL, 33431, USA

    Brandon Langenberg & Rainer Steinwandt

  4. Microsoft Research, One Microsoft Way, Redmond, WA, 98052, USA

    Martin Roetteler

Authors
  1. Markus Grassl
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Brandon Langenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Martin Roetteler
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rainer Steinwandt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Roetteler .

Editor information

Editors and Affiliations

  1. Kyushu University, Fukuoka, Japan

    Tsuyoshi Takagi

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R. (2016). Applying Grover’s Algorithm to AES: Quantum Resource Estimates. In: Takagi, T. (eds) Post-Quantum Cryptography. PQCrypto 2016. Lecture Notes in Computer Science(), vol 9606. Springer, Cham. https://doi.org/10.1007/978-3-319-29360-8_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-29360-8_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-29359-2

  • Online ISBN: 978-3-319-29360-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation