Paper 2021/527

Practical solving of discrete logarithm problem over prime fields using quantum annealing

Michał Wroński

Abstract

This paper investigates how to reduce discrete logarithm problem over prime fields to the QUBO problem to obtain as few logical qubits as possible. We show different methods of reduction of discrete logarithm problem over prime fields to the QUBO problem. In the best case, if $n$ is the bitlength of a characteristic of the prime field $\mathbb F_p$, there are required approximately $2n^2$ logical qubits for such reduction. We present practical attacks on discrete logarithm problem over the $4$-bit prime field $\mathbb F_{11}$, over $5$-bit prime field $\mathbb F_{23}$ and over $6$-bit prime field $\mathbb F_{59}$. We solved these problems using D-Wave Advantage QPU. It is worth noting that, according to our knowledge, until now, no one has made a practical attack on discrete logarithm over the prime field using quantum methods.

Note: This paper is the upgraded and revised version of the previous version of the paper. We changed the title from "Solving discrete logarithm problem over prime fields using quantum annealing and $\frac{n^3}{2}$ logical qubits" to "Practical solving of discrete logarithm problem over prime fields using quantum annealing." The current version presents a better method of reducing the discrete logarithm problem to the QUBO problem than in the previous version of the paper. What's more, we did practical experiments, and we described these experiments in the current version of the paper.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problemD-Wave Advantagequantum annealing
Contact author(s)
michal wronski @ wat edu pl
History
2021-12-30: revised
2021-04-23: received
See all versions
Short URL
https://ia.cr/2021/527
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/527,
      author = {Michał Wroński},
      title = {Practical solving of discrete logarithm problem over prime fields using quantum annealing},
      howpublished = {Cryptology ePrint Archive, Paper 2021/527},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/527}},
      url = {https://eprint.iacr.org/2021/527}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.