International Association
for Cryptologic Research

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.

Starting from the one-way group action framework of Brassard and Yung (Crypto’90), we revisit building cryptography based on group actions. Several previous candidates for one-way group actions no longer stand, due to progress both on classical algorithms (e.g., graph isomorphism) and quantum algorithms (e.g., discrete logarithm).We propose the general linear group action on tensors as a new candidate to build cryptography based on group actions. Recent works (Futorny–Grochow–Sergeichuk Lin. Alg. Appl., 2019) suggest that the underlying algorithmic problem, the tensor isomorphism problem, is the hardest one among several isomorphism testing problems arising from areas including coding theory, computational group theory, and multivariate cryptography. We present evidence to justify the viability of this proposal from comprehensive study of the state-of-art heuristic algorithms, theoretical algorithms, hardness results, as well as quantum algorithms.We then introduce a new notion called pseudorandom group actions to further develop group-action based cryptography. Briefly speaking, given a group G acting on a set S, we assume that it is hard to distinguish two distributions of (s, t) either uniformly chosen from $$S\times S$$, or where s is randomly chosen from S and t is the result of applying a random group action of $$g\in G$$ on s. This subsumes the classical Decisional Diffie-Hellman assumption when specialized to a particular group action. We carefully analyze various attack strategies that support instantiating this assumption by the general linear group action on tensors.Finally, we construct several cryptographic primitives such as digital signatures and pseudorandom functions. We give quantum security proofs based on the one-way group action assumption and the pseudorandom group action assumption.