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)
- 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
-
CC BY