Cryptology ePrint Archive: Report 2020/919

Tight Bounds for Simon's Algorithm

Xavier Bonnetain

Abstract: Simon's algorithm is the first example of a quantum algorithm exponentially faster than any classical algorithm, and has many applications in cryptanalysis. While these quantum attacks are often extremely efficient, they are generally missing some precise cost estimate. This article aims at resolving this issue by presenting precise query estimates for the different use cases of Simon's algorithm in cryptanalysis, and shows that Simon's algorithm requires in most cases little more than $n$ queries to succeed.

Category / Keywords: foundations / Simon's algorithm, quantum cryptanalysis, complexity analysis

Date: received 23 Jul 2020, last revised 25 Jul 2020

Contact author: xbonnetain at uwaterloo ca

Available format(s): PDF | BibTeX Citation

Version: 20200726:062423 (All versions of this report)

Short URL: ia.cr/2020/919