Advertisement
Published in:
2021 | OriginalPaper | Chapter
Index Calculus Method for Solving Elliptic Curve Discrete Logarithm Problem Using Quantum Annealing
Author : Michał Wroński
Published in: Computational Science – ICCS 2021
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
This paper presents an index calculus method for elliptic curves over prime fields using quantum annealing. The relation searching step is transformed into the QUBO (Quadratic Unconstrained Boolean Optimization) problem, which may be efficiently solved using quantum annealing, for example, on a D-Wave computer. Unfortunately, it is hard to estimate the complexity of solving the given QUBO problem using quantum annealing. Using Leap hybrid sampler on the D-Wave Leap cloud, we could break ECDLP for the 8-bit prime field. The most powerful general-purpose quantum computers nowadays would break ECDLP at most for a 6-bit prime using Shor’s algorithm. In presented approach, the Semaev method of construction of decomposition base is used, where the decomposition base has a form \(\mathcal {B}=\left\{ x: 0 \le x \le p^{\frac{1}{m}} \right\} \), with m being a fixed integer.