Top

Published in:

2020 | OriginalPaper | Chapter

Implementing Grover Oracles for Quantum Key Search on AES and LowMC

Authors : Samuel Jaques, Michael Naehrig, Martin Roetteler, Fernando Virdia

Published in: Advances in Cryptology – EUROCRYPT 2020

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Grover’s search algorithm gives a quantum attack against block ciphers by searching for a key that matches a small number of plaintext-ciphertext pairs. This attack uses \(O(\sqrt{N})\) calls to the cipher to search a key space of size N. Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits.

In contrast, we study the cost of quantum key search attacks under a depth restriction and introduce techniques that reduce the oracle depth, even if it requires more qubits. As cases in point, we design quantum circuits for the block ciphers AES and LowMC. Our circuits give a lower overall attack cost in both the gate count and depth-times-width cost models. In NIST’s post-quantum cryptography standardization process, security categories are defined based on the concrete cost of quantum key search against AES. We present new, lower cost estimates for each category, so our work has immediate implications for the security assessment of post-quantum cryptography.

As part of this work, we release Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce our quantum resource estimates. To the best of our knowledge, these are the first two such full implementations and automatic resource estimations.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound

next chapter Optimal Merging in Quantum -xor and k-sum Algorithms

https://github.com/microsoft/grover-blocks.

We thank Mathias Soeken for providing the implementation of the AND gate circuit.

https://github.com/microsoft/qsharp-runtime/issues/30, visited 2019-08-24.

E.g. see [10, 12, 27, 38, 40‐43, 52, 53].

https://github.com/microsoft/qsharp-runtime/issues/31, visited 2019-09-03.

Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_17CrossRef

Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. Cryptology ePrint Archive, Report 2016/687 (2016)

Almazrooie, M., Samsudin, A., Abdullah, R., Mutter, K.N.: Quantum reversible circuit of AES-128. Quantum Inf. Process. 17(5), 1–30 (2018). https://doi.org/10.1007/s11128-018-1864-3MathSciNetCrossRefMATH

Amento, B., Steinwandt, R., Roetteler, M.: Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity. arXiv:1209.6348 (2012)

Babbush, R., et al.: Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X 8(4), 041015 (2018)

Banegas, G., Bernstein, D.J.: Low-communication parallel quantum multi-target preimage search. In: Adams, C., Camenisch, J. (eds.) SAC 2017. LNCS, vol. 10719, pp. 325–335. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72565-9_16CrossRef

Banik, S., Funabiki, Y., Isobe, T.: More results on shortest linear programs. Cryptology ePrint Archive, Report 2019/856 (2019)

Beals, R., et al.: Efficient distributed quantum computing. Proc. Roy. Soc. A Math. Phys. Eng. Sci. 469, 20120686 (2013)MathSciNetMATH

Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: Quantum security analysis of AES. IACR Trans. Symmetric Cryptol. 2019(2), 55–93 (2019)CrossRef

10.

Boyar, J., Peralta, R.: A new combinational logic minimization technique with applications to cryptology. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 178–189. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13193-6_16CrossRef

11.

Boyar, J., Peralta, R.: A small depth-16 circuit for the AES S-Box. In: Gritzalis, D., Furnell, S., Theoharidou, M. (eds.) SEC 2012. IAICT, vol. 376, pp. 287–298. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30436-1_24CrossRef

12.

Boyar, J., Find, M.G., Peralta, R.: Small low-depth circuits for cryptographic applications. Crypt. Commun. 11(1), 109–127 (2018). https://doi.org/10.1007/s12095-018-0296-3MathSciNetCrossRefMATH

13.

Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46(4–5), 493–505 (1998)CrossRef

14.

Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: ACM CCS 2017. ACM (2017)

15.

Daemen, J., Rijmen, V.: AES proposal: Rijndael (1999)

16.

Daemen, J., Rijmen, V.: Specification for the advanced encryption standard (AES). Federal Information Processing Standards Publication 197 (2001)

17.

Dinur, I., Kales, D., Promitzer, A., Ramacher, S., Rechberger, C.: Linear equivalence of block ciphers with partial non-linear layers: application to LowMC. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 343–372. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_12CrossRef

18.

Ekdahl, P., Johansson, T., Maximov, A., Yang, J.: A new SNOW stream cipher called SNOW-V. Cryptology ePrint Archive, Report 2018/1143 (2018)

19.

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)CrossRef

20.

Gidney, C.: Windowed quantum arithmetic. arXiv preprint arXiv:1905.07682 (2019)

21.

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). https://doi.org/10.1007/978-3-319-29360-8_3CrossRefMATH

22.

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC 1996. ACM (1996)

23.

Grover, L.K., Rudolph, T.: How significant are the known collision and element distinctness quantum algorithms? QIC 4(3), 201–206 (2004)MathSciNetMATH

24.

Itoh, T., Tsujii, S.: A fast algorithm for computing multiplicative inverses in GF(2\(^m\)) using normal bases. Inf. Comput. 78(3), 171–177 (1988)MathSciNetCrossRef

25.

Jaques, S., Schanck, J.M.: Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 32–61. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_2CrossRefMATH

26.

Jean, J., Moradi, A., Peyrin, T., Sasdrich, P.: Bit-sliding: a generic technique for bit-serial implementations of SPN-based primitives. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 687–707. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_33CrossRefMATH

27.

Jeon, Y.-S., Kim, Y.-J., Lee, D.-H.: A compact memory-free architecture for the AES algorithm using resource sharing methods. JCSC 19, 1109–1130 (2010)

28.

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

29.

Kim, P., Han, D., Jeong, K.C.: Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2. Quantum Inf. Process. 17(12), 1–39 (2018). https://doi.org/10.1007/s11128-018-2107-3MathSciNetCrossRefMATH

30.

Kranz, T., Leander, G., Stoffelen, K., Wiemer, F.: Shorter linear straight-line programs for MDS matrices. IACR Trans. Symm. Cryptol. 2017(4), 188–211 (2017)CrossRef

31.

Langenberg, B., Pham, H., Steinwandt, R.: Reducing the cost of implementing AES as a quantum circuit. Cryptology ePrint Archive, Report 2019/854 (2019)

32.

Low, G.H., Kliuchnikov, V., Schaeffer, L.: Trading T-gates for dirty qubits in state preparation and unitary synthesis. arXiv preprint arXiv:1812.00954 (2018)

33.

LowMC: LowMC/lowmc at e847fb160ad8ca1f373efd91a55b6d67f7deb425 (2019). https://github.com/LowMC/lowmc/tree/e847fb160ad8ca1f373efd91a55b6d67f7deb425

34.

Maximov, A.: AES MixColumn with 92 XOR gates. Cryptology ePrint Archive, Report 2019/833 (2019)

35.

Microsoft: Getting started with Python and Q# | Microsoft Docs (2019). https://docs.microsoft.com/en-us/quantum/install-guide/python

36.

Microsoft: microsoft/iqsharp: Microsoft’s IQ# server (2019). https://github.com/microsoft/iqsharp

37.

NIST: Submission requirements and evaluation criteria for the Post-Quantum Cryptography standardization process (2016)

38.

Nogami, Y., Nekado, K., Toyota, T., Hongo, N., Morikawa, Y.: Mixed bases for efficient inversion in \({{\mathbb{F}}{((2^2)^2)}{2}}\) and conversion matrices of SubBytes of AES. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 234–247. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15031-9_16CrossRefMATH

39.

PyCryptodome: Welcome to PyCryptodome’s documentation - PyCryptodome 3.8.2 documentation (2019). https://pycryptodome.readthedocs.io/en/stable/index.html

40.

Reyhani-Masoleh, A., Taha, M., Ashmawy, D.: New area record for the AES combined S-box/inverse S-box. In: ARITH. IEEE (2018)

41.

Reyhani-Masoleh, A., Taha, M., Ashmawy, D.: Smashing the implementation records of AES S-box. TCHES 2018, 298–336 (2018)CrossRef

42.

Rijmen, V.: Efficient implementation of the Rijndael S-box. Katholieke Universiteit Leuven, Dept. ESAT, Belgium (2000)

43.

Satoh, A., Morioka, S., Takano, K., Munetoh, S.: A compact rijndael hardware architecture with S-Box optimization. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 239–254. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_15CrossRef

44.

Selinger, P.: Quantum circuits of \(T\)-depth one. Phys. Rev. A 87, 042302 (2013)CrossRef

45.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: FOCS 1994, pp. 124–134. IEEE Computer Society (1994)

46.

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

47.

Steiger, D.S., Häner, T., Troyer, M.: ProjectQ: an open source software framework for quantum computing. Quantum 2(49), 10–22331 (2018)

48.

Stein, W., et al.: Sage Mathematics Software Version 8.1 (2017)

49.

Svore, K.M., et al.: Q#: enabling scalable quantum computing and development with a high-level DSL. In: RWDSL@CGO 2018 (2018)

50.

Tan, Q.Q., Peyrin, T.: Improved heuristics for short linear programs. Cryptology ePrint Archive, Report 2019/847 (2019)

51.

Trefethen, L., Bau, D.: Numerical Linear Algebra. Other Titles in Applied Mathematics. SIAM, Philadelphia (1997)CrossRef

52.

Ueno, R., Homma, N., Sugawara, Y., Nogami, Y., Aoki, T.: Highly efficient \(GF(2^8)\) inversion circuit based on redundant GF arithmetic and its application to AES design. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 63–80. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48324-4_4CrossRefMATH

53.

Wei, Z., Sun, S., Hu, L., Wei, M., Boyar, J., Peralta, R.: Scrutinizing the tower field implementation of the \(\mathbb{F}_{2^8}\) inverter - with applications to AES, Camellia, and SM4. Cryptology ePrint Archive, Report 2019/738 (2019)

54.

Yamamura, A., Ishizuka, H.: Quantum cryptanalysis of block ciphers (algebraic systems, formal languages and computations), vol. 1166, pp. 235–243 (2000). https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/64334/1/1166-29.pdf

55.

Zalka, C.: Grover’s quantum searching algorithm is optimal. Phys. Rev. A 60(4), 2746 (1999)CrossRef

56.

Zaverucha, G., et al.: Picnic. Technical report, NIST (2017)

Title: Implementing Grover Oracles for Quantum Key Search on AES and LowMC
Authors: Samuel Jaques
Michael Naehrig
Martin Roetteler
Fernando Virdia
Publisher: Springer International Publishing
Book: Advances in Cryptology – EUROCRYPT 2020
Print ISBN: 978-3-030-45723-5

Electronic ISBN: 978-3-030-45724-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-45724-2_10

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner