Abstract
In this paper we demonstrate that the overheads (ancillae qubits/time/number of gates) involved with implementing quantum oracles for a generic key-recovery attack against block-ciphers using quantum search techniques can be reduced. In particular, if we require r≥ 1 plaintext-ciphertext pairs to uniquely identify a user’s key, then using Grover’s quantum search algorithm for cryptanalysis of block-ciphers as in [2, 3, 9, 13, 18] would require a quantum circuit which requires effort (either Time × Space product or number of quantum gates) proportional to r. We demonstrate how we can reduce this by a fine-grained approach to quantum amplitude amplification [6, 17] and design of the required quantum oracles. We furthermore demonstrate that this effort can be reduced to < r with respect to cryptanalysis of AES-128/192/256 and provide full quantum resource estimations for AES-128/192/256 with our methods, and code in the Q# quantum programming language that extends the work of [13].
Original language | English |
---|---|
Title of host publication | Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers |
Editors | Orr Dunkelman, Michael J. Jacobson, Jr., Colin O’Flynn |
Place of Publication | Germany |
Publisher | Springer Science and Business Media Deutschland GmbH |
Pages | 360-384 |
Number of pages | 25 |
ISBN (Print) | 9783030816513 |
DOIs | |
Publication status | Published - 31 Dec 2021 |
Event | 27th International Conference on Selected Areas in Cryptography, SAC 2020 - Virtual, Online Duration: 21 Oct 2020 → 23 Oct 2020 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12804 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 27th International Conference on Selected Areas in Cryptography, SAC 2020 |
---|---|
City | Virtual, Online |
Period | 21/10/20 → 23/10/20 |
Bibliographical note
Funding Information:Acknowledgements. The authors kindly thank the reviewers for their constructive feedback and for pointing out the resource estimation bug in Q# (see Appendix A). Benjamin Pring was funded during the development of this research by EPRSC grant EP/M50645X/1, National Science Foundation grant 183980, NIST grant 60NANB17D184, a Seed grant of the Florida Center for Cybersecurity and a USF proposal enhancement grant. An early version of these results were first announced at the International Workshop on Coding and Cryptography 2019. The authors would like to thank Orr Dunkelman for providing a reference to [12].
Keywords
- AES
- Block ciphers
- Quantum cryptanalysis
- Quantum search
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science