Paper 2023/1054

Quantum Complexity for Discrete Logarithms and Related Problems

Minki Hhan, Korea Institute for Advanced Study
Takashi Yamakawa, NTT Social Informatics Laboratories
Aaram Yun, Ewha Womans University
Abstract

This paper studies the quantum computational complexity of the discrete logarithm (DL) and related group-theoretic problems in the context of ``generic algorithms''---that is, algorithms that do not exploit any properties of the group encoding. We establish the quantum generic group model and hybrid classical-quantum generic group model as quantum and hybrid analogs of their classical counterpart. This model counts the number of group operations of the underlying cyclic group $G$ as a complexity measure. Shor's algorithm for the discrete logarithm problem and related algorithms can be described in this model and make $O(\log |G|)$ group operations in their basic form. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in these models. * We prove that any quantum DL algorithm in the quantum generic group model must make $\Omega(\log |G|)$ depth of group operation queries. This shows that Shor's algorithm that makes $O(\log |G|)$ group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms. * We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We show that these variants are optimal among generic hybrid algorithms up to constant multiplicative factors: Any generic hybrid quantum-classical DL algorithm with a total number of (classical or quantum) group operations $Q$ must make $\Omega(\log |G|/\log Q)$ quantum group operations of depth $\Omega(\log\log |G| - \log\log Q)$. * When the quantum memory can only store $t$ group elements and use quantum random access classical memory (QRACM) of $r$ group elements, any generic hybrid quantum-classical algorithm must make either $\Omega(\sqrt{|G|})$ group operation queries in total or $\Omega(\log |G|/\log (tr))$ quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond $\Omega(\log |G|/\log (tr))$. As a side contribution, we show a multiple discrete logarithm problem admits a better algorithm than solving each instance one by one, refuting a strong form of the quantum annoying property suggested in the context of password-authenticated key exchange protocol.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Keywords
Quantum lower boundsShor's algorithmGeneric group model
Contact author(s)
minkihhan @ kias re kr
takashi yamakawa @ ntt com
aaramyun @ g ewha ac kr
History
2024-07-05: last of 2 revisions
2023-07-05: received
See all versions
Short URL
https://ia.cr/2023/1054
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1054,
      author = {Minki Hhan and Takashi Yamakawa and Aaram Yun},
      title = {Quantum Complexity for Discrete Logarithms and Related Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1054},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1054}},
      url = {https://eprint.iacr.org/2023/1054}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.