Paper 2024/1758

A comprehensive analysis of Regev's quantum algorithm

Abstract

Public key cryptography can be based on integer factorization and the discrete logarithm problem (DLP), applicable in multiplicative groups and elliptic curves. Regev’s recent quantum algorithm was initially designed for the factorization and was later extended to the DLP in the multiplicative group. In this article, we further extend the algorithm to address the DLP for elliptic curves. Notably, based on celebrated conjectures in Number Theory, Regev’s algorithm is asymptotically faster than Shor’s algorithm for elliptic curves. Our analysis covers all cases where Regev’s algorithm can be applied. We examine the general framework of Regev’s algorithm and offer a geometric description of its parameters. This preliminary analysis enables us to certify the success of the algorithm on a particular instance before running it. In the case of integer factorization, we demonstrate that there exists an in- finite family of RSA moduli for which the algorithm always fails. On the other hand, when the parameters align with the Gaussian heuristics, we prove that Regev’s algorithm succeeds. By noting that the algorithm naturally adapts to the multidimensional DLP, we proved that it succeeds for a certain range of parameters.