Paper 2019/1146

Implementing Grover oracles for quantum key search on AES and LowMC

Samuel Jaques
Michael Naehrig
Martin Roetteler
Fernando Virdia
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. This is a revised version that corrects the estimates for AES to account for some issues in Q# that made the original estimates inaccurate. We did not revise the estimates for LowMC, so the resource counts are likely lower than possible.

Note: Corrected errors in estimates due to Q# bugs.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
DOI
10.1007/978-3-030-45724-2_10
Keywords
Quantum cryptanalysisGrover's algorithmAESLowMCpost-quantum cryptographyQ# implementation
Contact author(s)
sam @ samueljaques com
mnaehrig @ microsoft com
martinro @ microsoft com
f virdia @ gmx com
History
2023-06-07: last of 4 revisions
2019-10-03: received
See all versions
Short URL
https://ia.cr/2019/1146
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1146,
      author = {Samuel Jaques and Michael Naehrig and Martin Roetteler and Fernando Virdia},
      title = {Implementing Grover oracles for quantum key search on AES and LowMC},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1146},
      year = {2019},
      doi = {10.1007/978-3-030-45724-2_10},
      note = {\url{https://eprint.iacr.org/2019/1146}},
      url = {https://eprint.iacr.org/2019/1146}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.