Tight generic quantum and hybrid quantum-classical complexity of the discrete logarithm problem: constant factors, interleaved hybrid tradeoffs, and Shoup-style generic group models

In the quantum generic group model (QGGM), the discrete logarithm (DL) problem over a prime-order cyclic group $G$ requires $\Omega(\log|G|)$ quantum group operations and is solvable with $O(\log|G|)$ operations by Shor's algorithm, so its asymptotic generic quantum complexity is settled. Hhan, Yamakawa, and Yun (CRYPTO 2024), who established this characterization together with matching hybrid quantum-classical and memory-bounded lower bounds, explicitly left open its quantitative completion: closing the constant-factor gap between the proven lower bounds and the known algorithms, determining the achievable tradeoffs between small numbers of quantum group operations and large amounts of classical group-operation work in interleaved hybrid algorithms, and extending the hybrid and memory-bounded lower bounds from the Maurer-style QGGM to the stronger Shoup-style (label-based) post-quantum generic group model. A follow-up by Hhan (EUROCRYPT 2025) resolved two further directions raised by the same paper (the composite-order case and the tight asymptotics of the multiple discrete logarithm problem) and proved a fully-quantum lower bound of $0.5\log|G|$ under a cost metric that also charges quantum equality gates, whereas the source paper's $0.25\log|G|+O(1)$ bound uses the QGGM convention in which equality queries are free; the three questions above remain open as of August 2026. This record states the surviving core as one problem: determine the tight group-operation complexity of generic quantum and hybrid quantum-classical DL algorithms, namely the exact constants, the full quantum-classical tradeoff curve, and the model-independence of the bounds.

Background

The discrete logarithm (DL) problem asks, given a generator $g$ of a cyclic group $G$ and an element $h = g^x$, to recover the exponent $x$. Its assumed hardness underpins widely deployed public-key cryptography (Diffie-Hellman key exchange and DSA/ECDSA signatures), so the quantum resources needed to solve it are a central parameter in planning the migration to post-quantum cryptography.

The generic group model (GGM) studies DL algorithms that use only the group operation, inversion, and equality tests, ignoring any special structure of how group elements are encoded. Two formalizations exist: Shoup's version, in which the algorithm manipulates random labels of group elements and queries an oracle to compose them, and Maurer's version, in which an oracle holds all group elements and the algorithm accesses them through group-operation and equality queries. Zhandry proved the two models equivalent for single-stage games, a class that includes DL. Shoup showed in 1997 that any classical generic algorithm needs $\Omega(\sqrt{p})$ group operations in a group of prime order $p$. Quantumly, Shor's algorithm solves DL with only $O(\log|G|)$ group operations, so the classical square-root barrier disappears; before 2023 no nontrivial lower bound on the quantum generic complexity of DL itself was known (the Cleve-Watrous bound concerns the depth of the quantum Fourier transform, a subroutine of Shor's algorithm, not the DL problem).

Hhan, Yamakawa, and Yun introduced the quantum generic group model (QGGM), a quantum analogue of Maurer's model in which group operations, inversions, and equality checks act as unitary gates on quantum registers holding group elements. They proved that any generic quantum DL algorithm over a prime-order group makes $\Omega(\log|G|)$ group operations, of depth $\Omega(\log|G|)$, so Shor's algorithm is asymptotically optimal among generic quantum algorithms even with parallelism. They also formalized a model of hybrid quantum-classical algorithms, which may interleave classical and quantum group-operation queries and are forced to measure their registers once their quantum operation or depth counters exceed a threshold, and proved that any hybrid algorithm with $Q$ total group operations needs $\Omega(\log|G|/\log Q)$ quantum group operations. In a memory-bounded variant, where the algorithm has quantum memory for only $t$ group elements and quantum random-access classical memory (QRACM, classical data readable in coherent superposition) for $r$ elements, any hybrid algorithm needs either $\Omega(\sqrt{|G|})$ total group operations or $\Omega(\log|G|/\log(tr))$ quantum group operations. Matching algorithms exist on all three fronts, including hybrid algorithms that first compute $O(\mathrm{polylog}|G|)$ group elements classically and then run a quantum phase with only $O(\log|G|/\log\log|G|)$ quantum group operations of depth $O(\log\log|G|)$.

The asymptotics are therefore tight, but the quantitative picture is not. The concrete lower bounds proven by Hhan-Yamakawa-Yun are $0.25\log|G|+O(1)$ quantum group operations in the fully quantum case and $\frac{1}{3}\log|G|+O(1)$ in the memory-bounded hybrid case with $t=r=1$ (the constants depend on the gate conventions, e.g. on whether $g\cdot h^{-1}$ counts as one operation). On the algorithmic side, Shor's algorithm and its early variants make about $2\log|G|$ group operations (the naive variant $4\log|G|$), and the hybrid algorithms of Kaliski and of Ekerå repeat a subroutine with $\log|G|+O(1)$ group operations about $\mathrm{polylog}|G|$ times, so a constant-factor gap of roughly a factor of two to four remains on every front. A follow-up by Hhan (EUROCRYPT 2025) proves lower bounds via a compression lemma for $(C,Q)$-algorithms, algorithms consisting of classical generic preprocessing followed by a quantum phase; it yields a fully-quantum bound of $\frac{1}{2}\log|G|$, but under the richer metric in which $Q$ counts quantum element gates including equality gates, whereas the source paper's $0.25\log|G|+O(1)$ constant uses the convention that equality queries are free, and it resolves two other directions of the original paper while leaving the constant gap and the interleaved-hybrid questions untouched. Finally, all of these bounds are proved in the Maurer-style QGGM. Zhandry's post-quantum GGM, the Shoup-style analogue, is known to be no weaker (every Maurer-style QGGM algorithm works there), but the reverse transfer lacks a proof in the quantum setting even for single-stage games, because the classical equivalence argument does not handle labels in superposition.

Problem Statement

Determine the tight group-operation complexity of generic quantum and hybrid quantum-classical algorithms for the discrete logarithm problem over a prime-order cyclic group $G$, completing the quantitative characterization begun by Hhan, Yamakawa, and Yun. All logs are base 2, and all bounds are in the quantum generic group model (QGGM) or its variants as defined in that paper. The problem has three linked components, each with a recognizable completion boundary of matching upper and lower bounds:

1. Constant factors. Close the constant-factor gap between the best lower bounds and the best algorithms, in each of the two regimes that have a single best lower bound and a single best algorithm: (a) fully quantum generic algorithms, where the best lower bound under the source paper's convention that equality queries are free is $0.25\log|G|+O(1)$ quantum group operations (Hhan's follow-up proves $\frac{1}{2}\log|G|+O(1)$ when quantum equality gates are also counted), while Shor-type algorithms use about $2\log|G|$ and hybrid algorithms of Kaliski and of Ekerå use $\log|G|+O(1)$ group operations per subroutine; and (b) the memory-bounded hybrid regime, where the best lower bound with $t=r=1$ is $\frac{1}{3}\log|G|+O(1)$. The interleaved hybrid regime with unbounded memory is not a separate constant-factor target here, because it has no single best lower bound or single best algorithm; its completion is the full tradeoff curve sought in component 2. The answer must state the exact leading constants under explicitly pinned gate conventions (which of $g\cdot h$, $g\cdot h^{-1}$, and the equality test count as one operation, and how depth and forced measurements are charged).

2. Hybrid tradeoff curve. In the interleaved hybrid model with unbounded memory, where classical group operations may depend on the outcomes of intermediate quantum measurements, characterize the achievable pairs (number of quantum group operations, number of classical group operations). The sharpest open point: does there exist a hybrid DL algorithm making a single quantum group operation and $O(|G|^{1/4})$ classical group operations? The known lower bound (Theorem 6.2) only forces $\Omega(|G|^{1/4})$ classical operations in this case, so such an algorithm is not excluded; it would be a genuine intermediate speedup, since purely classical generic algorithms need $\Omega(\sqrt{|G|})$ operations (Shoup) and fully quantum ones need $\Theta(\log|G|)$. This case is ruled out only under memory constraints (Theorem 7.2) or when the classical work is restricted to preprocessing before the quantum phase (Hhan 2024), so the unbounded-memory interleaved regime is open both for algorithms and for lower bounds.

3. Model robustness. Extend the hybrid and memory-bounded lower bounds (Theorems 1.3 and 1.4 of the source paper) from the Maurer-style QGGM, in which they are currently proved, to the Shoup-style (label-based) post-quantum generic group model introduced by Zhandry. Every Maurer-style QGGM algorithm works in the Shoup-style model, so the Shoup-style bounds would strictly dominate; the obstacle is that the classical equivalence of the two generic-group formulations, known for single-stage games, does not carry over to the quantum setting because labels would have to be handled in superposition.

The three components amount to determining matching upper and lower bounds with explicit constants for each regime of setting 1 under one pinned gate convention; for setting 2, a characterization of the achievable pairs (quantum group operations, classical group operations) that determines the full tradeoff curve, including the single-quantum-operation/$O(|G|^{1/4})$-classical point; and, for setting 3, proofs of the hybrid and memory-bounded lower bounds in the Shoup-style post-quantum generic group model.

References

1. Minki Hhan, Takashi Yamakawa, Aaram Yun. Quantum Complexity for Discrete Logarithms and Related Problems. Advances in Cryptology - CRYPTO 2024, LNCS, pp. 3-36. DOI: 10.1007/978-3-031-68391-6_1; also arXiv:2307.03065. https://arxiv.org/abs/2307.03065
2. Minki Hhan. A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More. Advances in Cryptology - EUROCRYPT 2025, LNCS, pp. 345-374. DOI: 10.1007/978-3-031-91098-2_13; also arXiv:2402.11269. https://arxiv.org/abs/2402.11269
3. Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. Advances in Cryptology - EUROCRYPT 1997, LNCS, pp. 256-266. DOI: 10.1007/3-540-69053-0_18. https://doi.org/10.1007/3-540-69053-0_18
4. Richard Cleve, John Watrous. Fast parallel circuits for the quantum Fourier transform. Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000), pp. 526-536. DOI: 10.1109/SFCS.2000.892140. https://doi.org/10.1109/SFCS.2000.892140
5. Aaram Yun. Generic Hardness of the Multiple Discrete Logarithm Problem. Advances in Cryptology - EUROCRYPT 2015, LNCS, pp. 817-836. DOI: 10.1007/978-3-662-46803-6_27. https://doi.org/10.1007/978-3-662-46803-6_27
6. Mark Zhandry. Redeeming Reset Indifferentiability and Applications to Post-Quantum Security. Advances in Cryptology - ASIACRYPT 2021, LNCS, pp. 518-548. DOI: 10.1007/978-3-030-92062-3_18. https://doi.org/10.1007/978-3-030-92062-3_18
7. Mark Zhandry. To Label, or Not To Label (in Generic Groups). Advances in Cryptology - CRYPTO 2022, LNCS, pp. 66-96. DOI: 10.1007/978-3-031-15982-4_3. https://doi.org/10.1007/978-3-031-15982-4_3
8. Burton S. Kaliski Jr. A Quantum "Magic Box" for the Discrete Logarithm Problem. IACR Cryptology ePrint Archive, Paper 2017/745, 2017. https://eprint.iacr.org/2017/745
9. Martin Ekerå. Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. Journal of Mathematical Cryptology 15(1):359-407, 2021. DOI: 10.1515/jmc-2020-0006. https://doi.org/10.1515/jmc-2020-0006
10. Martin Ekerå, Joel Gärtner. Extending Regev's factoring algorithm to compute discrete logarithms. Post-Quantum Cryptography (PQCrypto 2024), LNCS, pp. 211-242. DOI: 10.1007/978-3-031-62746-0_10; also arXiv:2311.05545. https://arxiv.org/abs/2311.05545
11. Henry Corrigan-Gibbs, Alexandra Henzinger, David J. Wu. The Structured Generic-Group Model. IACR Cryptology ePrint Archive, Paper 2026/384, 2026. https://eprint.iacr.org/2026/384
12. Marcel Tiepelt, Edward Eaton, Douglas Stebila. Making an Asymmetric PAKE Quantum-Annoying by Hiding Group Elements. Computer Security - ESORICS 2023, LNCS, pp. 168-188. DOI: 10.1007/978-3-031-50594-2_9. https://doi.org/10.1007/978-3-031-50594-2_9
13. Craig Gidney, Martin Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5:433, 2021. DOI: 10.22331/q-2021-04-15-433. https://doi.org/10.22331/q-2021-04-15-433