Paper 2017/1122 Original: eprint.iacr.org/2017/1122 ↗
On post-processing in the quantum algorithm for computing short discrete logarithms
Abstract
We revisit the quantum algorithm for computing short discrete logarithms that was recently introduced by Ekerå and Håstad. By carefully analyzing the probability distribution induced by the algorithm, we show its success probability to be higher than previously reported. Inspired by our improved understanding of the distribution, we propose an improved post-processing algorithm that is practical, enables better tradeoffs to be achieved, and requires fewer runs, than the original post-processing algorithm. To prove these claims, we construct a classical simulator for the quantum algorithm by sampling the probability distribution it induces for given logarithms. This simulator is in itself a key contribution. We use it to demonstrate that our quantum algorithm achieves an advantage over Shor's algorithms, not only in each individual run, but also overall, when targeting cryptographically relevant instances of RSA and Diffie-Hellman with short exponents.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2019-02-10: last updated
- 2017-11-24: published
- Short URL
- https://ia.cr/2017/1122
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2017/1122,
author = {Martin Ekerå},
title = {On post-processing in the quantum algorithm for computing short discrete logarithms},
howpublished = {Cryptology {ePrint} Archive, Paper 2017/1122},
year = {2017},
url = {https://eprint.iacr.org/2017/1122}
}