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

Cost analysis of hash collisions : will quantum computers make SHARCS obsolete?

Daniel J. Bernstein

Published Jan 1, 2009• 61 citations
OpenAlex

Abstract

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.

Related papers

Algorithms Built to Prevent Future Quantum Attacks: Post-Quantum Cryptography in Preparation for Quantum Computing Threats

Mohan Kumar Gajula, Arunkumar Akuthota

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.

International Conference on Sustainability and Technological Advancements in Engineering Domain (SUSTAINED)•Dec 13, 2024•1 citation

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 Shor's Algorithm vs. Classical General Number Field Sieve (GNFS) Approach for Large Integer Factorization

S. S. Kavitha, Narasimha Kaulgud, B. Sharmila +3 more

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 to$2^{n}$bits.

International Conference on Next Generation Communication & Information Processing (INCIP)•Jan 23, 2025•1 citation

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•71 citations

Investigating the Impact of Quantum Computing on Cryptographic Algorithms

Prof. MSR Prasad

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.

Journal of Contemporary Science and Technology Management•Dec 16, 2025•0 citations

The Transition from Classical to Post-Quantum Cryptography

Paul Hoffman

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.

•May 26, 2020•4 citations
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 to2n2^{n}2nbits.
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.