A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography

Martin Ekerå; Joel Gärtner

doi:10.62056/ayzojb0kr

A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography

Authors

Martin Ekerå, Joel Gärtner

Martin Ekerå

KTH Royal Institute of Technology, Stockholm, Sweden
Swedish NCSA, Swedish Armed Forces, Stockholm, Sweden
ekera at kth dot se

Joel Gärtner

KTH Royal Institute of Technology, Stockholm, Sweden
Swedish NCSA, Swedish Armed Forces, Stockholm, Sweden
jgartner at kth dot se

Keywords: Regev's algorithm Cost estimates Factoring Discrete logarithms

Abstract

We provide a high-level cost comparison between Regev's quantum algorithm with Ekerå–Gärtner's extensions on the one hand, and existing state-of-the-art quantum algorithms for factoring and computing discrete logarithms on the other. This when targeting cryptographically relevant problem instances, and when accounting for the space-saving optimizations of Ragavan and Vaikuntanathan that apply to Regev's algorithm, and optimizations such as windowing that apply to the existing algorithms.

Our conclusion is that Regev's algorithm without the space-saving optimizations may achieve a per-run advantage, but not an overall advantage, if non-computational quantum memory is cheap. Regev's algorithm with the space-saving optimizations does not achieve an advantage, since it uses more computational memory, whilst also performing more work, per run and overall, compared to the existing state-of-the-art algorithms. As such, further optimizations are required for it to achieve an advantage for cryptographically relevant problem instances.

References

[ACD⁺24]

M.R. Albrecht, B. Curtis, L. Ducas, F. Göpfert, H. Hunt, H. Kippen, C. Lefebvre, J. Owen, R. Player, L. Pulles, M. Schmidt, S. Scott, F. Virdia, M. Walter, and C. Yun. Security estimates for lattice problems. GitHub repository malb/lattice-estimator. 2014–2024.

Google Scholar ePrint

[APS15]

M.R. Albrecht, R. Player, and S. Scott. On the concrete hardness of Learning with Errors. J. Math. Cryptol., 9(3):169–203, 2015. DOI: 10.1515/jmc-2015-0016

Google Scholar ePrint

[BBP24]

R. Barbulescu, M. Barcau, and V. Paşol. A comprehensive analysis of Regev's quantum algorithm. (Dated 2024-11-05.). Cryptology ePrint Archive, Paper 2024/1758. 2024.

Google Scholar ePrint

[BCR⁺18]

E. Barker, L. Chen, A. Roginsky, A. Vassilev, and R. Davis. Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. (3rd revision). National Institute of Standards and Technology (NIST) Special Publication (SP) 800-56A. 2018.

Google Scholar ePrint

[BCR⁺19]

E. Barker, L. Chen, A. Roginsky, A. Vassilev, R. Davis, and S. Simon. Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. (2nd revision). National Institute of Standards and Technology (NIST) Special Publication (SP) 800-56B. 2019.

Google Scholar ePrint

[Che13]

Y. Chen. Réduction de réseau et sécurité concrète du chiffrement complètement homomorphe. PhD thesis, Université Paris Diderot (Paris 7), 2013.

Google Scholar ePrint

[Cop02]

D. Coppersmith. An approximate Fourier transform useful in quantum factoring. (Also IBM Research Report RC 19642.). 2002.

Google Scholar ePrint

[DH76]

W. Diffie and M. Hellman. New directions in cryptography. IEEE Trans. Inf. Theory, 22(6):644–654, 1976. DOI: 10.1109/TIT.1976.1055638

Google Scholar ePrint

[EG24a]

M. Ekerå and J. Gärtner. Simulating Regev's quantum factoring algorithm and Ekerå–Gärtner's extensions to discrete logarithm finding, order finding and factoring via order finding. GitHub repository ekera/regevnum. 2023–2024.

Google Scholar ePrint

[EG24b]

M. Ekerå and J. Gärtner. Extending Regev's Factoring Algorithm to Compute Discrete Logarithms. In M.-J. Saarinen and D. Smith-Tone, editors, Post-Quantum Cryptography, pages 211–242, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-62746-0_10

Google Scholar ePrint

[EH17]

M. Ekerå and J. Håstad. Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. In T. Lange and T. Takagi, editors, Post-Quantum Cryptography, pages 347–363, Cham. 2017. Springer International Publishing. DOI: 10.1007/978-3-319-59879-6_20

Google Scholar ePrint

[Eke20]

M. Ekerå. On post-processing in the quantum algorithm for computing short discrete logarithms. Des. Codes Cryptogr., 88(11):2313–2335, 2020. DOI: 10.1007/s10623-020-00783-2

Google Scholar ePrint

[Eke21]

M. Ekerå. Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. J. Math. Cryptol., 15(1):359–407, 2021. DOI: 10.1515/jmc-2020-0006

Google Scholar ePrint

[Eke23]

M. Ekerå. On the success probability of the quantum algorithm for the short DLP. 2023.

Google Scholar ePrint

[Eke24a]

M. Ekerå. Qunundrum. GitHub repository ekera/qunundrum. 2020–2024.

Google Scholar ePrint

[Eke24b]

M. Ekerå. Revisiting Shor's quantum algorithm for computing general discrete logarithms. 2024.

Google Scholar ePrint

[GE21]

C. Gidney and M. 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

Google Scholar ePrint

[Gid19]

C. Gidney. Windowed quantum arithmetic. 2019.

Google Scholar ePrint

[Gil16]

D. Gillmor. Negotiated Finite Field Diffie–Hellman Ephemeral Parameters for Transport Layer Security (TLS). Request for Comments (RFC) 7919. 2016.

Google Scholar ePrint

[KJ17]

B. S. Kaliski Jr. Targeted Fibonacci Exponentiation. 2017.

Google Scholar ePrint

[KK03]

M. Kojo and T. Kivinen. More Modular Exponential (MODP) Diffie–Hellman groups for Internet Key Exchange (IKE). Request for Comments (RFC) 3526. 2003.

Google Scholar ePrint

[LLL82]

A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515–534, 1982. DOI: 10.1007/BF01457454

Google Scholar ePrint

[ME99]

M. Mosca and A. Ekert. The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In C.P. Williams, editor, Quantum Computing and Quantum Communications, pages 174–188. 1999. Springer Berlin Heidelberg. DOI: 10.1007/3-540-49208-9_15

Google Scholar ePrint

[{Nat}94]

National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS). Federal Information Processing Standard (FIPS) 186. 1994.

Google Scholar ePrint

[{Nat}23]

National Institute of Standards and Technology (NIST). Digital Signature Standard (DSS). Federal Information Processing Standard (FIPS) 186-5. 2023.

Google Scholar ePrint

[NC23]

National Institute of Standards, Technology (NIST), and Canadian Centre for Cyber Security (CCCS). Implementation guidance for FIPS 140-2 and the cryptographic module validation program. (Dated October 30, 2023.). 2023.

Google Scholar ePrint

[Pil24]

C. Pilatte. Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms. 2024.

Google Scholar ePrint

[PP00]

S. Parker and M.B. Plenio. Efficient Factorization with a Single Pure Qubit and $\log N$ Mixed Qubits. Phys. Rev. Lett., 85:3049–3052, 2000. DOI: 10.1103/PhysRevLett.85.3049

Google Scholar ePrint

[Rag24]

S. Ragavan. Regev Factoring Beyond Fibonacci: Optimizing Prefactors. (Dated 2024-07-01.). Cryptology ePrint Archive, Paper 2024/636. 2024.

Google Scholar ePrint

[Reg25]

O. Regev. An Efficient Quantum Factoring Algorithm. J. ACM, 72(1):10:1–13, 2025. DOI: 10.1145/3708471

Google Scholar ePrint

[RSA78]

R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126, 1978. DOI: 10.1145/359340.359342

Google Scholar ePrint

[RV23]

S. Ragavan and V. Vaikuntanathan. Optimizing Space in Regev's Factoring Algorithm. 2023.

Google Scholar ePrint

[RV24]

S. Ragavan and V. Vaikuntanathan. Space-Efficient and Noise-Robust Quantum Factoring. In L. Reyzin and D. Stebila, editors, Advances in Cryptology — CRYPTO 2024, pages 107–140, Cham, Switzerland. 2024. Springer Nature. DOI: 10.1007/978-3-031-68391-6_4

Google Scholar ePrint

[SE94]

C.-P. Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Program., 66(1):181–199, 1994. DOI: 10.1007/BF01581144

Google Scholar ePrint

[Sei01]

J.-P. Seifert. Using Fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation. In D. Naccache, editor, Topics in Cryptology — CT-RSA 2001, pages 319–327, Berlin, Heidelberg. 2001. Springer Berlin Heidelberg. DOI: 10.1007/3-540-45353-9_24

Google Scholar ePrint

[Sho94]

P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134. 1994. DOI: 10.1109/SFCS.1994.365700

Google Scholar ePrint

[Sho97]

P.W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput., 26(5):1484–1509, 1997. DOI: 10.1137/S0097539795293172

Google Scholar ePrint

[VM08]

R. Van Meter. Architecture of a Quantum Multicomputer Optimized for Shor's Factoring Algorithm. PhD thesis, Keio University, 2008.

Google Scholar ePrint

[VMI05]

R. Van Meter and K.M. Itoh. Fast quantum modular exponentiation. Phys. Rev. A, 71:052320, 2005. DOI: 10.1103/PhysRevA.71.052320

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ayzojb0kr

History

Submitted: 2025-01-14
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Martin Ekerå and Joel Gärtner, A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ayzojb0kr.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/ayzojb0kr,
         author={Martin Ekerå and Joel Gärtner},
         title={A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/ayzojb0kr},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Martin Ekerå
AU  - Joel Gärtner
PY  - 2025
TI  - A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/ayzojb0kr
UR  - https://doi.org/10.62056/ayzojb0kr
AB  - <p>  We provide a high-level cost comparison between Regev's quantum algorithm with Ekerå–Gärtner's extensions on the one hand, and existing state-of-the-art quantum algorithms for factoring and computing discrete logarithms on the other.   This when targeting cryptographically relevant problem instances, and when accounting for the space-saving optimizations of Ragavan and Vaikuntanathan that apply to Regev's algorithm, and optimizations such as windowing that apply to the existing algorithms.</p><p>  Our conclusion is that Regev's algorithm without the space-saving optimizations may achieve a per-run advantage, but not an overall advantage, if non-computational quantum memory is cheap.   Regev's algorithm with the space-saving optimizations does not achieve an advantage, since it uses more computational memory, whilst also performing more work, per run and overall, compared to the existing state-of-the-art algorithms.   As such, further optimizations are required for it to achieve an advantage for cryptographically relevant problem instances. </p>
ER  -

Martin Ekerå and Joel Gärtner, A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ayzojb0kr.