Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2405.14381 · IACR Communications in Cryptology

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

Martin Ekerå, Joel Gärtner

Published Apr 8, 2025• 4 citations
arXivHTMLPDF

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.

DOI
10.62056/ayzojb0kr

Related papers

Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes

Vlad Gheorghiu, Michele Mosca

Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.

arXiv:1902.02332•Feb 6, 2019•28 citations

Space-Efficient and Noise-Robust Quantum Factoring

Seyoon Ragavan, Vinod Vaikuntanathan

We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires $O(n^{3/2})$ qubits and $O(n^{3/2} \log n)$ gates, while Shor's circuit requires $O(n^2 \log n)$ gates but only $O(n \log n)$ qubits. As with Regev, to factor an $n$-bit integer $N$, we run our circuit independently $O(\sqrt{n})$ times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all $\approx \sqrt{n}$ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.

arXiv:2310.00899•Oct 2, 2023•2 citations

Quantum resource estimation for large scale quantum algorithms

Vlad Gheorghiu, Michele Mosca

Quantum algorithms are often represented in terms of quantum circuits operating on ideal (logical) qubits. However, the practical implementation of these algorithms poses significant challenges. Many quantum algorithms require a substantial number of logical qubits, and the inherent susceptibility to errors of quantum computers require quantum error correction. The integration of error correction introduces overhead in terms of both space (physical qubits required) and runtime (how long the algorithm needs to be run for). This paper addresses the complexity of comparing classical and quantum algorithms, primarily stemming from the additional quantum error correction overhead. We propose a comprehensive framework that facilitates a direct and meaningful comparison between classical and quantum algorithms. By acknowledging and addressing the challenges introduced by quantum error correction, our framework aims to provide a clearer understanding of the comparative performance of classical and quantum computing approaches. This work contributes to understanding the practical viability and potential advantages of quantum algorithms in real-world applications. We apply our framework to quantum cryptanalysis, since it is well known that quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. This analysis provides state-of-the art snap-shot estimates of the realistic costs of implementing quantum attacks on these important cryptographic algorithms, assuming quantum fault-tolerance is achieved using surface code methods, and spanning a range of potential error rates. These estimates serve as a guide for gauging the realistic impact of these algorithms and for benchmarking the impact of future advances in quantum algorithms, circuit synthesis and optimization, fault-tolerance methods and physical error rates.

Future Generation Computer Systems•Aug 12, 2024•17 citations

Implementation And Analysis of Regev’s Quantum Factorization Algorithm

Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec +1 more

Abstract Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor’s algorithm and the more recently developed Regev’s algorithm for factoring composite numbers. We present our implementation of the latter with the aim of exposing experimental phenomena. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev’s and Shor’s algorithms. Our experimental results reveal that Regev’s algorithm outperforms Shor’s algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev’s algorithm’s theoretical asymptotic advantage in effectiveness, our implementation exhibited longer execution times than Shor’s algorithm for small-integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev’s algorithm in realistic quantum computing scenarios.

arXiv:2502.09772•Quantum Information and Computation•Mar 1, 2026•0 citations

Quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes

Vlad Gheorghiu, Michele Mosca

Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.

•Feb 6, 2019•2 citations

Quantum-Safe Cryptography

Kunal Meher

The defense of public key cryptography (PKC) lies in computational issues like the difficulty of factorizing enormous prime numbers and the discrete logarithm calculations. Such kinds of algorithms are called one-way functions because although it is straightforward to compute output given input, it is difficult to compute input if output is given. It is expected that such numerical or computational issues which are utilized in current cryptographic plans are difficult to address for an adversary utilizing present PCs. Yet, many organizations are attempting to assemble a high-powered quantum PC and in the future quantum PCs will be available for business use. Traditional asymmetric cryptographic algorithms are not secure against strong quantum machines. Shor’s algorithm running on a powerful quantum PC is able to solve integer factorization problems and discrete logarithm problems in polynomial time. So, asymmetric algorithms that are used today, like RSA, DSA and Diffie-Hellman will become insecure. Similarly, Grover’s algorithm running on a powerful quantum computer poses a serious threat to symmetric key algorithms which uses small key size. There is a need to work on alternate algorithms to resist quantum threat. NIST has already started with a process for the standardization of algorithms which are known as post-quantum cryptography (PQC) algorithms. Specialists globally are exploring progress toward post-quantum cryptography.

Chapman & Hall/CRC eBooks•Aug 9, 2023•3 citations
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.
Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.
We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using O(nlog⁡n)O(n \log n)O(nlogn) qubits and O(n3/2log⁡n)O(n^{3/2} \log n)O(n3/2logn) gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires O(n3/2)O(n^{3/2})O(n3/2) qubits and O(n3/2log⁡n)O(n^{3/2} \log n)O(n3/2logn) gates, while Shor's circuit requires O(n2log⁡n)O(n^2 \log n)O(n2logn) gates but only O(nlog⁡n)O(n \log n)O(nlogn) qubits. As with Regev, to factor an nnn-bit integer NNN, we run our circuit independently O(n)O(\sqrt{n})O(n​) times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all ≈n\approx \sqrt{n}≈n​ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.
Quantum algorithms are often represented in terms of quantum circuits operating on ideal (logical) qubits. However, the practical implementation of these algorithms poses significant challenges. Many quantum algorithms require a substantial number of logical qubits, and the inherent susceptibility to errors of quantum computers require quantum error correction. The integration of error correction introduces overhead in terms of both space (physical qubits required) and runtime (how long the algorithm needs to be run for). This paper addresses the complexity of comparing classical and quantum algorithms, primarily stemming from the additional quantum error correction overhead. We propose a comprehensive framework that facilitates a direct and meaningful comparison between classical and quantum algorithms. By acknowledging and addressing the challenges introduced by quantum error correction, our framework aims to provide a clearer understanding of the comparative performance of classical and quantum computing approaches. This work contributes to understanding the practical viability and potential advantages of quantum algorithms in real-world applications. We apply our framework to quantum cryptanalysis, since it is well known that quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. This analysis provides state-of-the art snap-shot estimates of the realistic costs of implementing quantum attacks on these important cryptographic algorithms, assuming quantum fault-tolerance is achieved using surface code methods, and spanning a range of potential error rates. These estimates serve as a guide for gauging the realistic impact of these algorithms and for benchmarking the impact of future advances in quantum algorithms, circuit synthesis and optimization, fault-tolerance methods and physical error rates.
Abstract Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor’s algorithm and the more recently developed Regev’s algorithm for factoring composite numbers. We present our implementation of the latter with the aim of exposing experimental phenomena. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev’s and Shor’s algorithms. Our experimental results reveal that Regev’s algorithm outperforms Shor’s algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev’s algorithm’s theoretical asymptotic advantage in effectiveness, our implementation exhibited longer execution times than Shor’s algorithm for small-integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev’s algorithm in realistic quantum computing scenarios.
Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.
The defense of public key cryptography (PKC) lies in computational issues like the difficulty of factorizing enormous prime numbers and the discrete logarithm calculations. Such kinds of algorithms are called one-way functions because although it is straightforward to compute output given input, it is difficult to compute input if output is given. It is expected that such numerical or computational issues which are utilized in current cryptographic plans are difficult to address for an adversary utilizing present PCs. Yet, many organizations are attempting to assemble a high-powered quantum PC and in the future quantum PCs will be available for business use. Traditional asymmetric cryptographic algorithms are not secure against strong quantum machines. Shor’s algorithm running on a powerful quantum PC is able to solve integer factorization problems and discrete logarithm problems in polynomial time. So, asymmetric algorithms that are used today, like RSA, DSA and Diffie-Hellman will become insecure. Similarly, Grover’s algorithm running on a powerful quantum computer poses a serious threat to symmetric key algorithms which uses small key size. There is a need to work on alternate algorithms to resist quantum threat. NIST has already started with a process for the standardization of algorithms which are known as post-quantum cryptography (PQC) algorithms. Specialists globally are exploring progress toward post-quantum cryptography.