Cryptology ePrint Archive: Report 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.

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

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]