[Resource Topic] 2017/811: Reassessing Grover's Algorithm

Welcome to the resource topic for 2017/811

Reassessing Grover’s Algorithm

Authors: Scott Fluhrer


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.

ePrint: https://eprint.iacr.org/2017/811

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .