**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.

**Category / Keywords: **public-key cryptography / cryptanalysis, discrete logarithm problem, factoring, RSA, quantum, Shor's algorithms

**Date: **received 20 Nov 2017, last revised 20 Nov 2017

**Contact author: **ekera at kth se

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20171124:065156 (All versions of this report)

**Short URL: **ia.cr/2017/1122

[ Cryptology ePrint archive ]