Skip to main content

2020 | OriginalPaper | Buchkapitel

Implementing Grover Oracles for Quantum Key Search on AES and LowMC

verfasst von : Samuel Jaques, Michael Naehrig, Martin Roetteler, Fernando Virdia

Erschienen in: Advances in Cryptology – EUROCRYPT 2020

Verlag: Springer International Publishing

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

search-config
loading …

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.

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!

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!

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!

Fußnoten
2
We thank Mathias Soeken for providing the implementation of the AND gate circuit.
 
4
E.g. see [10, 12, 27, 38, 4043, 52, 53].
 
Literatur
2.
Zurück zum Zitat Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. Cryptology ePrint Archive, Report 2016/687 (2016) Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. Cryptology ePrint Archive, Report 2016/687 (2016)
4.
Zurück zum Zitat Amento, B., Steinwandt, R., Roetteler, M.: Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity. arXiv:1209.6348 (2012) Amento, B., Steinwandt, R., Roetteler, M.: Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity. arXiv:​1209.​6348 (2012)
5.
Zurück zum Zitat Babbush, R., et al.: Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X 8(4), 041015 (2018) Babbush, R., et al.: Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X 8(4), 041015 (2018)
7.
Zurück zum Zitat Banik, S., Funabiki, Y., Isobe, T.: More results on shortest linear programs. Cryptology ePrint Archive, Report 2019/856 (2019) Banik, S., Funabiki, Y., Isobe, T.: More results on shortest linear programs. Cryptology ePrint Archive, Report 2019/856 (2019)
8.
Zurück zum Zitat Beals, R., et al.: Efficient distributed quantum computing. Proc. Roy. Soc. A Math. Phys. Eng. Sci. 469, 20120686 (2013)MathSciNetMATH Beals, R., et al.: Efficient distributed quantum computing. Proc. Roy. Soc. A Math. Phys. Eng. Sci. 469, 20120686 (2013)MathSciNetMATH
9.
Zurück zum Zitat Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: Quantum security analysis of AES. IACR Trans. Symmetric Cryptol. 2019(2), 55–93 (2019)CrossRef Bonnetain, X., Naya-Plasencia, M., Schrottenloher, A.: Quantum security analysis of AES. IACR Trans. Symmetric Cryptol. 2019(2), 55–93 (2019)CrossRef
13.
Zurück zum Zitat Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46(4–5), 493–505 (1998)CrossRef Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschr. Phys. 46(4–5), 493–505 (1998)CrossRef
14.
Zurück zum Zitat Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: ACM CCS 2017. ACM (2017) Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: ACM CCS 2017. ACM (2017)
15.
Zurück zum Zitat Daemen, J., Rijmen, V.: AES proposal: Rijndael (1999) Daemen, J., Rijmen, V.: AES proposal: Rijndael (1999)
16.
Zurück zum Zitat Daemen, J., Rijmen, V.: Specification for the advanced encryption standard (AES). Federal Information Processing Standards Publication 197 (2001) Daemen, J., Rijmen, V.: Specification for the advanced encryption standard (AES). Federal Information Processing Standards Publication 197 (2001)
18.
Zurück zum Zitat Ekdahl, P., Johansson, T., Maximov, A., Yang, J.: A new SNOW stream cipher called SNOW-V. Cryptology ePrint Archive, Report 2018/1143 (2018) Ekdahl, P., Johansson, T., Maximov, A., Yang, J.: A new SNOW stream cipher called SNOW-V. Cryptology ePrint Archive, Report 2018/1143 (2018)
19.
Zurück zum Zitat 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 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
22.
Zurück zum Zitat Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC 1996. ACM (1996) Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC 1996. ACM (1996)
23.
Zurück zum Zitat Grover, L.K., Rudolph, T.: How significant are the known collision and element distinctness quantum algorithms? QIC 4(3), 201–206 (2004)MathSciNetMATH Grover, L.K., Rudolph, T.: How significant are the known collision and element distinctness quantum algorithms? QIC 4(3), 201–206 (2004)MathSciNetMATH
24.
Zurück zum Zitat 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 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
27.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Jones, C.: Low-overhead constructions for the fault-tolerant Toffoli gate. Phys. Rev. A 87(2), 022328 (2013)CrossRef Jones, C.: Low-overhead constructions for the fault-tolerant Toffoli gate. Phys. Rev. A 87(2), 022328 (2013)CrossRef
30.
Zurück zum Zitat 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 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.
Zurück zum Zitat Langenberg, B., Pham, H., Steinwandt, R.: Reducing the cost of implementing AES as a quantum circuit. Cryptology ePrint Archive, Report 2019/854 (2019) Langenberg, B., Pham, H., Steinwandt, R.: Reducing the cost of implementing AES as a quantum circuit. Cryptology ePrint Archive, Report 2019/854 (2019)
32.
Zurück zum Zitat 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) 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)
34.
Zurück zum Zitat Maximov, A.: AES MixColumn with 92 XOR gates. Cryptology ePrint Archive, Report 2019/833 (2019) Maximov, A.: AES MixColumn with 92 XOR gates. Cryptology ePrint Archive, Report 2019/833 (2019)
37.
Zurück zum Zitat NIST: Submission requirements and evaluation criteria for the Post-Quantum Cryptography standardization process (2016) NIST: Submission requirements and evaluation criteria for the Post-Quantum Cryptography standardization process (2016)
38.
40.
Zurück zum Zitat Reyhani-Masoleh, A., Taha, M., Ashmawy, D.: New area record for the AES combined S-box/inverse S-box. In: ARITH. IEEE (2018) Reyhani-Masoleh, A., Taha, M., Ashmawy, D.: New area record for the AES combined S-box/inverse S-box. In: ARITH. IEEE (2018)
41.
Zurück zum Zitat Reyhani-Masoleh, A., Taha, M., Ashmawy, D.: Smashing the implementation records of AES S-box. TCHES 2018, 298–336 (2018)CrossRef Reyhani-Masoleh, A., Taha, M., Ashmawy, D.: Smashing the implementation records of AES S-box. TCHES 2018, 298–336 (2018)CrossRef
42.
Zurück zum Zitat Rijmen, V.: Efficient implementation of the Rijndael S-box. Katholieke Universiteit Leuven, Dept. ESAT, Belgium (2000) Rijmen, V.: Efficient implementation of the Rijndael S-box. Katholieke Universiteit Leuven, Dept. ESAT, Belgium (2000)
44.
Zurück zum Zitat Selinger, P.: Quantum circuits of \(T\)-depth one. Phys. Rev. A 87, 042302 (2013)CrossRef Selinger, P.: Quantum circuits of \(T\)-depth one. Phys. Rev. A 87, 042302 (2013)CrossRef
45.
Zurück zum Zitat Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: FOCS 1994, pp. 124–134. IEEE Computer Society (1994) Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: FOCS 1994, pp. 124–134. IEEE Computer Society (1994)
46.
Zurück zum Zitat 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 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.
Zurück zum Zitat Steiger, D.S., Häner, T., Troyer, M.: ProjectQ: an open source software framework for quantum computing. Quantum 2(49), 10–22331 (2018) Steiger, D.S., Häner, T., Troyer, M.: ProjectQ: an open source software framework for quantum computing. Quantum 2(49), 10–22331 (2018)
48.
Zurück zum Zitat Stein, W., et al.: Sage Mathematics Software Version 8.1 (2017) Stein, W., et al.: Sage Mathematics Software Version 8.1 (2017)
49.
Zurück zum Zitat Svore, K.M., et al.: Q#: enabling scalable quantum computing and development with a high-level DSL. In: RWDSL@CGO 2018 (2018) Svore, K.M., et al.: Q#: enabling scalable quantum computing and development with a high-level DSL. In: RWDSL@CGO 2018 (2018)
50.
Zurück zum Zitat Tan, Q.Q., Peyrin, T.: Improved heuristics for short linear programs. Cryptology ePrint Archive, Report 2019/847 (2019) Tan, Q.Q., Peyrin, T.: Improved heuristics for short linear programs. Cryptology ePrint Archive, Report 2019/847 (2019)
51.
Zurück zum Zitat Trefethen, L., Bau, D.: Numerical Linear Algebra. Other Titles in Applied Mathematics. SIAM, Philadelphia (1997)CrossRef Trefethen, L., Bau, D.: Numerical Linear Algebra. Other Titles in Applied Mathematics. SIAM, Philadelphia (1997)CrossRef
52.
53.
Zurück zum Zitat 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) 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)
55.
Zurück zum Zitat Zalka, C.: Grover’s quantum searching algorithm is optimal. Phys. Rev. A 60(4), 2746 (1999)CrossRef Zalka, C.: Grover’s quantum searching algorithm is optimal. Phys. Rev. A 60(4), 2746 (1999)CrossRef
56.
Zurück zum Zitat Zaverucha, G., et al.: Picnic. Technical report, NIST (2017) Zaverucha, G., et al.: Picnic. Technical report, NIST (2017)
Metadaten
Titel
Implementing Grover Oracles for Quantum Key Search on AES and LowMC
verfasst von
Samuel Jaques
Michael Naehrig
Martin Roetteler
Fernando Virdia
Copyright-Jahr
2020
DOI
https://doi.org/10.1007/978-3-030-45724-2_10