Current proposals for special-purpose factorization hardware will become obsolete if large quantum computers are built: the number-field sieve scales much more poorly than Shor's quantum algorithm for factorization. Will all special-purpose cryptanalytic hardware become obsolete in a post-quantum world?\nA quantum algorithm by Brassard, HØyer, and Tapp has frequently been claimed to reduce the cost of b-bit hash collisions from 2^b/2 to 2^b/3.\nThis paper analyzes the Brassard-HØyer-Tapp algorithm and shows that it has fundamentally worse price-performance ratio than the classical van Oorschot-Wiener hash-collision circuits, even under optimistic assumptions regarding the speed of quantum computers.
Current proposals for special-purpose factorization hardware will become obsolete if large quantum computers are built: the number-field sieve scales much more poorly than Shor's quantum algorithm for factorization. Will all special-purpose cryptanalytic hardware become obsolete in a post-quantum world?\nA quantum algorithm by Brassard, HØyer, and Tapp has frequently been claimed to reduce the cost of b-bit hash collisions from 2^b/2 to 2^b/3.\nThis paper analyzes the Brassard-HØyer-Tapp algorithm and shows that it has fundamentally worse price-performance ratio than the classical van Oorschot-Wiener hash-collision circuits, even under optimistic assumptions regarding the speed of quantum computers.
Traditional cryptographic systems that are based on algorithms such as RSA, ECC, and DH are becoming increasingly vulnerable to quantum-based attacks. This is especially the case attributable to algorithms such as Shor’s, which are able to factor large integers and solve discrete logarithms in an efficient manner. There has been a rapid advancement in quantum computing. There is a significant risk to the integrity, confidentiality, and security of the data that a result of this. Cryptographic algorithms that are immune to both classical and quantum attacks are the goal of post-quantum cryptography, often known as PQC. The purpose of this study is to investigate a variety of post-quantum algorithms, including lattice-based, hash-based, code-based, multivariate, and isogeny-based cryptography, and to evaluate the possibility of these algorithms to successfully defend against future quantum attacks. Within the context of real-world applications, we dissect the security assumptions, performance indicators, and issues that these algorithms present. In addition to this, we investigate the current efforts that are being made to standardize PQC through projects such as the NIST post-quantum cryptography work. In order to ensure the safety of data over the long term, this study offers some insights into the process of developing cryptographic methods that are durable in preparation for the era of quantum computing.
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 integer factorization is a groundbreaking field that explores the use of quantum algorithms, notably Shor's algorithm, to efficiently factorize large integers into their prime components. Its potential implications on modern encryption techniques, such as the Rivest-Shamir-Adleman (RSA) algorithm, are of considerable interest. This paper's central aim is to contrast the computational time and implementation of the Integer Factorization Problem (IFP) between classical and quantum computers. The inner workings of Quantum Shor's algorithm are broken down step by step, and the estimated processing time is contrasted with the classical General Number Field Sieve (GNFS) approach. Given the exponential speedup provided by quantum computing, this comparison helps assess Shor's algorithm's possible advantage over GNFS in factoring large numbers. Direct comparisons with GNFS are currently difficult due to Shor's algorithm's reliance on large-scale quantum computer development for practical execution speeds. This paper focuses on solving integer factorization up to2nbits.
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 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.
Quantum computing is the study of computers that use quantum features
in calculations. For over 20 years, it has been known that if very
large, specialized quantum computers could be built, they could have a
devastating effect on asymmetric classical cryptographic algorithms
such as RSA and elliptic curve signatures and key exchange, as well as
(but in smaller scale) on symmetric cryptographic algorithms such as
block ciphers, MACs, and hash functions. There has already been a
great deal of study on how to create algorithms that will resist
large, specialized quantum computers, but so far, the properties of
those algorithms make them onerous to adopt before they are needed.
Small quantum computers are being built today, but it is still far
from clear when large, specialized quantum computers will be built
that can recover private or secret keys in classical algorithms at the
key sizes commonly used today. It is important to be able to predict
when large, specialized quantum computers usable for cryptanalysis
will be possible so that organization can change to post-quantum
cryptographic algorithms well before they are needed. This document
describes quantum computing, how it might be used to attack classical
cryptographic algorithms, and possibly how to predict when large,
specialized quantum computers will become feasible.