Paper 2017/745

A Quantum ``Magic Box'' for the Discrete Logarithm Problem

Burton S. Kaliski Jr.

Abstract

In their foundational paper on pseudorandom bit generation, Blum and Micali showed that the discrete logarithm problem could be solved efficiently given a ``magic box'' oracle that computes the most significant bit of the discrete logarithm with a slight advantage over guessing. This magic box can be realized on a quantum computer with a new, simplified variant of Shor's algorithm. The resulting combination of Blum and Micali's reduction and this new quantum magic box offers an intriguing hybrid approach to solving the discrete logarithm problem with a quantum computer. Because the only requirement on the quantum portion of the algorithm is that it provide an approximate estimate of a single bit of the discrete logarithm, the new algorithm may be easier to implement, more resilient to errors, and more amenable to optimization than previous approaches. Further analysis is needed to quantify the extent of these benefits in practice. The result applies to the discrete logarithm problem over both finite fields and elliptic curves. (The views expressed are my own and do not necessarily reflect those of my employer.)

Note: Added disclaimer to end of abstract, no other changes

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
discrete logarithm problemelliptic curve cryptosystemquantum cryptanalysis
Contact author(s)
bkaliski @ alum mit edu
History
2017-08-07: received
Short URL
https://ia.cr/2017/745
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/745,
      author = {Burton S.  Kaliski Jr.},
      title = {A Quantum ``Magic Box'' for the Discrete Logarithm Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2017/745},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/745}},
      url = {https://eprint.iacr.org/2017/745}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.