Paper 2023/1054
Quantum Complexity for Discrete Logarithms and Related Problems
Abstract
This paper studies the quantum computational complexity of the discrete logarithm and related grouptheoretic problems in the context of ``generic algorithms''that is, algorithms that do not exploit any properties of the group encoding. We establish a generic model of quantum computation for grouptheoretic problems, which we call the quantum generic group model, as a quantum analog of its classical counterpart. Shor's algorithm for the discrete logarithm problem and related algorithms can be described in this model. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in this model. More precisely, we prove the following results for a cyclic group $\mathcal G$ of prime order. (1) Any generic quantum discrete logarithm algorithm must make $\Omega(\log \mathcal G)$ depth of group operation queries. This shows that Shor's algorithm that makes $O(\log \mathcal G)$ group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms. (2) 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 introduce a model for generic hybrid quantumclassical algorithm that captures these variants, and show that these algorithms are almost optimal in this model. Any generic hybrid quantumclassical algorithm for the discrete logarithm problem with a total number of (classical or quantum) group operations $Q$ must make $\Omega(\log \mathcal G/\log Q)$ quantum group operations of depth $\Omega(\log\log \mathcal G  \log\log Q)$. In particular, if $Q={\rm poly}\log \mathcal G$, classical group operations can only save the number of quantum queries by a factor of $O(\log\log \mathcal G)$ and the quantum depth remains as $\Omega(\log\log \mathcal G)$. (3) When the quantum memory can only store $t$ group elements and use quantum random access memory (qRAM) of $r$ group elements, any generic hybrid quantumclassical algorithm must make either $\Omega(\sqrt{\mathcal G})$ group operation queries in total or $\Omega(\log \mathcal G/\log (tr))$ quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond $\Omega(\log \mathcal 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 passwordauthenticated key exchange protocol.
Note: A typo in the title has been corrected.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 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
 20230711: revised
 20230705: received
 See all versions
 Short URL
 https://ia.cr/2023/1054
 License

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} }