Improvements to Quantum Search Techniques for Block-Ciphers, with Applications to AES

James H. Davenport, Benjamin Pring

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

7 Citations (SciVal)
88 Downloads (Pure)

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 languageEnglish
Title of host publicationSelected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers
EditorsOrr Dunkelman, Michael J. Jacobson, Jr., Colin O’Flynn
Place of PublicationGermany
PublisherSpringer Science and Business Media Deutschland GmbH
Pages360-384
Number of pages25
ISBN (Print)9783030816513
DOIs
Publication statusPublished - 31 Dec 2021
Event27th International Conference on Selected Areas in Cryptography, SAC 2020 - Virtual, Online
Duration: 21 Oct 202023 Oct 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12804 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on Selected Areas in Cryptography, SAC 2020
CityVirtual, Online
Period21/10/2023/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

Fingerprint

Dive into the research topics of 'Improvements to Quantum Search Techniques for Block-Ciphers, with Applications to AES'. Together they form a unique fingerprint.

Cite this