### 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 computing precise query costs for the different use cases of Simon's algorithm in cryptanalysis. We propose an extensive analysis of Simon's algorithm, and we show that it requires little more than $n$ queries to succeed in most cases. We performed the first concrete cost analysis for the exact variant of Simon's algorithm and the offline Simon's algorithm, and show that they require respectively at most $3n$ queries and little more than $n+k$ queries. We also found that for parameter sizes of cryptographic relevance, it is possible to truncate the output of the periodic function to a dozen of bits without any impact on the number of queries, which saves qubits in reversible implementations of Simon's algorithm.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Simon's algorithmquantum cryptanalysisquery complexity
Contact author(s)
xbonnetain @ uwaterloo ca
History
2020-10-25: revised
See all versions
Short URL
https://ia.cr/2020/919

CC BY

BibTeX

@misc{cryptoeprint:2020/919,
author = {Xavier Bonnetain},
title = {Tight Bounds for Simon's Algorithm},
howpublished = {Cryptology ePrint Archive, Paper 2020/919},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/919}},
url = {https://eprint.iacr.org/2020/919}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.