|
Base of exponent representation matters -- more efficient reduction of discrete logarithm problem and elliptic curve discrete logarithm problem to the QUBO problem
(pp0541-0564)
Michal Wronski and Lukasz Dzierzkowski
doi:
https://doi.org/10.26421/QIC24.7-8-1
Abstracts:
This paper presents further improvements in the transformation of the
Discrete Logarithm Problem (DLP)
and Elliptic Curve Discrete Logarithm Problem (ECDLP)
over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO)
problem. This is significant from a
cryptanalysis
standpoint, as
QUBO
problems may be solved using quantum
annealers,
and the fewer variables the resulting
QUBO
problem has, the less time is expected to obtain a solution.The main
idea presented in the paper is allowing the representation of the
exponent in different bases than the typically used base 2 (binary
representation). It is shown that in such cases, the reduction of the
discrete logarithm problem over the prime field
\(\mathbb{F}_p\)
to the
QUBO problem may be obtained using
approximately \(1.89n^2\)
logical variables for \(n\)
being the
bitlength
of prime \(p\),
instead of the \(2n^2\)
which was previously the best-known reduction method. The paper provides
a practical example using the given method to solve the discrete
logarithm problem over the prime field
\(\mathbb{F}_{47}\).
Similarly, for the elliptic curve discrete logarithm problem over the
prime field \(\mathbb{F}_p\),
allowing the representation of the exponent in different bases than
typically used base two results in a lower number of required logical
variables for \(n\)
being the
bitlength
of prime \(p\),
from \(3n^3\)
to \(\frac{6n^3}{\log_{2}\left(\frac{3}{4}n\right)}\)
logical variables, in the case of Edwards curves.
Key Words:
elliptic curve discrete
logarithm problem, D-Wave, quantum annealing,
cryptanalysis |
