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
-
CC BY
BibTeX
@misc{cryptoeprint:2017/811,
author = {Scott Fluhrer},
title = {Reassessing Grover's Algorithm},
howpublished = {Cryptology {ePrint} Archive, Paper 2017/811},
year = {2017},
url = {https://eprint.iacr.org/2017/811}
}
