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

James H. Davenport, Benjamin Pring

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 statusE-pub ahead of print - 21 Jul 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

Keywords

  • AES
  • Block ciphers
  • Quantum cryptanalysis
  • Quantum search

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this