A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More

arXiv:2402.11269v1 Announce Type: cross
Abstract: This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models.
- In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring.
- …

arxiv cryptographic cs.cr factoring find limitations mdl problems quant-ph quantum settings simple studies