CryptoDB
A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | This paper presents a unified way to study the limitations of the generic quantum and classical algorithms to solve cryptographic problems over algebraic structures. Our main new lower bounds for the discrete logarithm (DL) and integer factoring problems are as follows. 1. Classical lower bounds for the multiple-instance DL (MDL) problem in the presence of the DL oracle and preprocessing in the (classical) generic group model (GGM). 2. Quantum lower bounds for the DL and MDL problems over the composite-order group, even allowing the algorithm to construct uniform (or arbitrary) superpositions of single group elements in the quantum GGM (QGGM). 3. Quantum lower bounds for the order-finding problem and certain factoring algorithms, including Regev’s algorithm, in the quantum generic ring model (QGRM). All lower bounds match the known algorithms, resolving many open problems suggested by Hhan, Yamakawa, and Yun (CRYPTO’24). The central tool of the proofs is the so-called compression lemma. Using this tool, we give alternative and simple proofs for the known lower bounds. We also prove the classical lower bounds for the (basic) index calculus method in the smooth GGM (SGGM). Our use of the compression lemma may be of independent interest. Along the way, we establish new generic models to prove the lower bounds: the QGRM and SGGM, which capture quantum factoring algorithms by Shor and Regev (or slight variations) and the basic index calculus, respectively. Thus, our lower bounds indicate the limitations of those strategies for the DL and factoring problems. |
BibTeX
@inproceedings{eurocrypt-2025-35063,
title={A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More},
publisher={Springer-Verlag},
author={Minki Hhan},
year=2025
}