You are looking at a specific version 20171124:065156 of this paper. See the latest version.

Paper 2017/1122

On post-processing in the quantum algorithm for computing short discrete logarithms

Martin Ekerå

Abstract

Ekerå and Håstad recently introduced a quantum algorithm for computing short discrete logarithms. To compute an m bit logarithm d this algorithm exponentiates group elements in superposition to m+2m/s bit exponents for s >= 1 an integer. Given a set of s good outputs, a classical post-processing algorithm then recovers d by enumerating an s+1-dimensional lattice. Increasing s trades work in the quantum algorithm for classical work. However, as good outputs cannot be trivially distinguished, the quantum algorithm needs to be run s/p times and all subsets of s outputs exhaustively post-processed, where p is the probability of observing a good output. In this paper, we introduce an improved post-processing algorithm that removes the need to exhaustively enumerate exponential in s many s+1-dimensional lattices, at the expense of reducing a single n+1 dimensional lattice and applying Babai's algorithm. The new algorithm is practical for much greater values of s and in general requires fewer runs than the original algorithm. As a concrete example, for m = 1024, s = 30 and n = 40, the algorithm recovers d within a few seconds with approximately 99% success probability.

Note: The approximately equal to sign in the abstract was not properly rendered.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
cryptanalysisdiscrete logarithm problemfactoringRSAquantumShor's algorithms
Contact author(s)
ekera @ kth se
History
2019-02-10: revised
2017-11-24: received
See all versions
Short URL
https://ia.cr/2017/1122
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.