Paper 2017/811

Reassessing Grover's Algorithm

Scott Fluhrer

Abstract

We note that Grover's algorithm (and any other quantum algorithm that does a search using an oracle) does not parallelize well. Accordingly, we propose a modified security assumption, that the attacker has bounded time to perform the attack in addition to an overall computational budget. We show that, under this security assumption, the size of the problems that Grover's algorithm can attack is less than commonly assumed. For example, we show that for symmetric keys, we don't need to double their size, adding a fixed number of bits is sufficient. This reduction in strength can be used to make postquantum cryptography to be of lesser cost, without sacrificing security.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
quantum computation
Contact author(s)
sfluhrer @ cisco com
History
2017-08-29: received
Short URL
https://ia.cr/2017/811
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/811,
      author = {Scott Fluhrer},
      title = {Reassessing Grover's Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2017/811},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/811}},
      url = {https://eprint.iacr.org/2017/811}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.