Quantum Complexity for Discrete Logarithms and Related Problems

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 \(\mathcal {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 |\mathcal {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. 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.