Solving Elliptic Curve Discrete Logarithm Problem on Twisted Edwards Curves Using Quantum Annealing and Index Calculus Method

This paper presents an approach to solving the elliptic curve discrete logarithm problem on alternative curve models over prime fields using a quantum annealing and index calculus method. Part of the algorithm, relation searching, is transformed into the Quadratic Unconstrained Boolean Optimization (QUBO) problem and then is efficiently solved using the D-Wave computer by quantum annealing. As Faugère et al. showed, twisted Edwards curves, because of their symmetric shape, allow us to obtain solutions of relations searching step using Groebner basis faster than in the case of Weierstrass curves. Because of symmetries, a system of equations of relations searching step for twisted Edwards curves has many symmetric solutions. Using the Groebner basis and having many system solutions makes it easier to find any of them. The same is true using quantum annealing - it is easier to find any solution to the QUBO problem if many are correct. In this paper, we used this observation to find out that a properly constructed QUBO problem for the relations searching step for twisted Edwards curves allows us to find a solution faster for the same size of the base field than in the case of Weierstrass curves. Using the presented approach, we solved the discrete logarithm problem using quantum annealing and index calculus method for elliptic curve discrete logarithm problem defined on twisted Edwards curve over a field 𝔽₁₀₂₁ with order equal to 4 · 241. It is now the biggest field and size of the group, where the elliptic curve discrete logarithm problem was solved using quantum methods.