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.
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.
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.
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.
The advent of quantum computing poses an existential threat to classical cryptographic systems. Shor’s algorithm (1994) can factor large integers and compute discrete logarithms in polynomial time, breaking widely used schemes like RSA, ECC, and Diffie-Hellman. This paper surveys the state-of-the-art in quantum cryptanalysis, examining its impact on symmetric and asymmetric cryptography, recent progress in quantum attacks, and defenses via post-quantum cryptography (PQC). We analyze key quantum algorithms (Shor’s, Grover’s), their real-world feasibility given current hardware (NISQ-era limitations), and emerging PQC standards (NIST’s CRYSTALS-Kyber, Dilithium). We also discuss novel attack vectors (e.g., hybrid quantum-classical cryptanalysis) and future research directions.
The advent of large-scale quantum computers poses an existential threat to the cryptographic algorithms that underpin modern digital security. Shor's algorithm enables quantum computers to factor large integers and compute discrete logarithms in polynomial time, rendering RSA, Elliptic Curve Cryptography (ECC), and Diffie-Hellman key exchange fundamentally insecure. Meanwhile, Grover's algorithm provides a quadratic speedup for brute-force search, effectively halving the security strength of symmetric ciphers and hash functions. This paper presents a comprehensive investigation into the impact of quantum computing on both asymmetric and symmetric cryptographic algorithms. We analyze the computational resources required by quantum attacks on current standards, evaluate the timeline of quantum threats based on hardware roadmaps from leading quantum computing companies, and conduct a systematic performance comparison of NIST-standardized post-quantum cryptographic (PQC) algorithms. Our experimental evaluation covers key generation time, encapsulation/decapsulation latency, signature generation/verification speed, key sizes, and bandwidth overhead across lattice-based, code-based, hash-based, and multivariate cryptographic schemes. Results indicate that lattice-based schemes, particularly CRYSTALS-Kyber and CRYSTALS-Dilithium, offer the most favorable balance of security and performance for practical deployment. We also propose a phased migration framework for transitioning existing cryptographic infrastructure to quantum-resistant alternatives, addressing compatibility, performance, and operational challenges.
Modern public key cryptosystems rely on two assumptions regarding computational difficulty: the integer factorization problem (RSA) and the discrete logarithm problem (elliptic curve cryptography).These problems have stood the test of time for four decades of cryptanalysis.Yet, their algebraic and periodic nature makes them vulnerable to quantum algorithms, most notably Shor's algorithm (1994).This paper presents a detailed comparison between classical and quantum-resistant cryptographic systems with an emphasis on lattice-based systems.The Learning With Errors (LWE) problem and its variants (Ring-LWE, Module-LWE) do not have the same periodicity that makes problems like integer factorization and discrete logarithms susceptible to quantum algorithms.Furthermore, LWE problems have reductions from worst-case lattice problems and have mathematical proofs of quantum resistance.Due to the vulnerability of ECDSA algorithms for cryptocurrencies, it is estimated that current cryptocurrencies will no longer be secure once quantum computer technology matures within the next 10-30 years, potentially compromising holdings estimated at between $260 billion and $390 billion as of August 2026.The implications of cryptanalysis on public key cryptography systems motivate mathematical recommendations regarding the security of current cryptosystems and the need for a shift to post-quantum cryptographic standards.
Contemporary cryptographic algorithms are resistant to the strongest threats to cybersecurity and high-profile cyber-attacks. In recent times, information security scientists and researchers had developed various cryptographic schemes that defeated attacks using the most sophisticated (in terms of processor speed) classical computer. However, this resistance will soon erode with the arrival of quantum computers. In this paper, we profiled quantum computers and quantum algorithms based on their widely believed threat against currently secure cryptographic primitives. We found that Grover’s and Shor’s quantum-based algorithms actually pose a threat to the continued security of symmetric cryptosystems (e.g. 128-bit AES) and asymmetric (public key) cryptosystems (e.g. RSA, Elgamal, elliptic curve Diffie Hellman (ECDH), etc.) respectively.We discovered that the source of the algorithms’ cryptanalytic power against the current systems, stems from the fact that they (Grover and Shor) both equipped their respective algorithms with a quantum circuit component that can execute the oracle in parallel by applying a single circuit to all possible states of an n-qubit input. With this exponential level of processing characteristic of quantum computers and quantum-based algorithms, it is easy for the current cryptosystems to be broken since the algorithms can existentially solve the underlying mathematical problems such as integer factorization, discrete logarithm problem and elliptic curve problem, which formed the basis of the security of the affected cryptosystems. Based on this realization and as part of our readiness for a post quantum era, we explored other mathematical structures (lattices, hashes, codes, isogenies, high entropy-based symmetric key resistance, and multivariate quadratic problems) whose hardness could surpass the cryptanalytic nightmare posed by quantum computers and quantum-based algorithms. Our contribution is that, based on the findings of this research work, we can confidently assert that all hope is not lost for organizations heavily relying on protocols and applications like HTTPS, TLS, PGP, Bitcoin, etc., which derived their security from the endangered cryptosystems.