Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / quantum computation

Date: received 27 Aug 2017

Contact author: sfluhrer at cisco com

Available format(s): PDF | BibTeX Citation

Version: 20170829:224225 (All versions of this report)

Short URL: ia.cr/2017/811

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]