Cryptology ePrint Archive: Report 2021/527

Solving discrete logarithm problem over prime fields using quantum annealing and $\frac{n^3}{2}$ logical qubits

Michał Wroński

Abstract: Shor's quantum algorithm for integer factorization and discrete logarithm is one of the fundamental approaches in modern cryptology. The application of Shor's algorithm requires a general-purpose quantum computer. On the other hand, there are known methods of transformation of factorization problem to the QUBO problem and then solving it using quantum annealing computing with approximately $\frac{n^2}{4}$ logical qubits, for example, using D-Wave computer. It is believed that this approach also may be helpful, primarily until large general-purpose quantum computers will exist. Until now algorithm of similar efficiency for computing discrete logarithm over prime fields was unknown. In this paper, we present a method of reducing discrete logarithm problem to the QUBO problem, which requires approximately $\frac{n^3}{2}$ logical qubits. We also show how to apply quantum annealing to compute discrete logarithm modulo composite numbers, where a quantum annealing factorization algorithm may be used to reduce discrete logarithm modulo composite to several discrete logarithm problems modulo prime number.

Category / Keywords: public-key cryptography / discrete logarithm problem, D-Wave, quantum annealing, cryptanalysis

Date: received 21 Apr 2021

Contact author: michal wronski at wat edu pl

Available format(s): PDF | BibTeX Citation

Version: 20210423:122550 (All versions of this report)

Short URL: ia.cr/2021/527


[ Cryptology ePrint archive ]