Quantum Attacks on Bitcoin, and How to Protect Against Them
Open accessAbstract
The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. One particular area at risk is cryptocurrencies, a market currently worth over 100 billion USD. We investigate the risk posed to Bitcoin, and other cryptocurrencies, by attacks using quantum computers. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates. We analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also review the available post-quantum signature schemes to see which one would best meet the security and efficiency requirements of blockchain applications.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
A 2017 study claimed quantum computers would be large and robust enough to break Bitcoin keys in 10 minutes by 2027.
“Another study by researchers in Singapore, Australia, and France claimed in 2017 that quantum computers would be large and robust enough to break Bitcoin keys in 10 minutes by 202779.”
From Quantum-resistance in blockchain networks (2023) · cites this paper as [79]
The Introduction says that, by the authors’ most optimistic estimates, a quantum computer could break Bitcoin’s elliptic-curve signature scheme in less than 10 minutes as early as 2027. The citing sentence presents that conditional possibility as something that would happen. Our copy also identifies the paper as a 2018 publication, not a 2017 study. (LLM, conf=0.88)
Experimental — accuracy not yet measuredQuantum algorithms like Shor's could break in the future the log of elliptic curves public-key cryptography (ECDSA) or the large integer factorization problem (RSA) needed to generate a signature, which are the baseline of several crypto-protocols used in blockchains.
“Quantum algorithms like Shor's, could break in the future the log of elliptic curves public-key cryptography (ECDSA) or the large integer factorization problem (RSA) needed to generate a signature, which are the baseline of several crypto-protocols used in blockchains (e.g. in bitcoin).”
From Privacy-Preserving Solutions for Blockchain: Review and Challenges (2019) · cites this paper as [91]
Split into 2 atoms — 0 confirmed, 2 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.
Experimental — accuracy not yet measuredWith upcoming Quantum Computing, some proof-of-work algorithms and signatures are under risk.
“With the upcoming Quantum Computing, some proof-ofwork algorithms and signatures are under risk [91].”
From Privacy-Preserving Solutions for Blockchain: Review and Challenges (2019) · cites this paper as [91]
Mixing methods were introduced in 1981 to anonymize email usage and since then have been used to anonymize different services with multiple users.
“To anonymize email usage, [126] introduced the mixing methods in 1981. Since then, these techniques are used to anonymize different services with multiple users.”
From Privacy-Preserving Solutions for Blockchain: Review and Challenges (2019) · cites this paper as [126]
Section 2 (Blockchain Basics) discusses Bitcoin transactions, and Section 3.2 discusses quantum attacks on Bitcoin addresses. Searches for mixing, anonymous email, and 1981 found no passage in our copy addressing the claimed history or later uses of mixing methods. (LLM, conf=0.77)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Bitcoin: A Peer-to-Peer Electronic Cash SystemPreprint
Nakamoto, S. (2019) · SSRN Electronic Journal · doi:10.2139/ssrn.3440802 · Cited by 14,599 · see citing works
Bitcoin: A Peer-to-Peer Electronic Cash SystemPreprint
Squarepants, S. (2022) · SSRN Electronic Journal · doi:10.2139/ssrn.3977007 · Cited by 11,146 · see citing works
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830 · see citing works
Bellare, M., & Rogaway, P. (1993) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/168588.168596 · Cited by 4,695 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325 · see citing works
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · see citing works
Trapdoors for hard lattices and new cryptographic constructions
Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374407 · Cited by 2,501 · see citing works
Superconducting quantum circuits at the surface code threshold for fault tolerance
Barends, R., Kelly, J., Megrant, A., Veitia, A., Sank, D., Jeffrey, E., White, T. C., Mutus, J., Fowler, A. G., Campbell, B., et al. (2014) · Nature · doi:10.1038/nature13171 · Cited by 1,733 · see citing works
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · see citing works
CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
Ducas, L., Kiltz, E., Lepoint, T., et al. (2018) · IACR Trans. Cryptogr. Hardw. Embed. Syst. · doi:10.13154/tches.v2018.i1.238-268 · Cited by 917 · see citing works
Lattice Signatures without Trapdoors
Lyubashevsky, V. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29011-4_43 · Cited by 870 · see citing works
Hashcash - A Denial of Service Counter-Measure
Back, A. (2002) · Cited by 740 · see citing works
Purans, J., Afify, N., Dalba, G., et al. (2004) · HAL (Le Centre pour la Communication Scientifique Directe) · doi:10.1103/physrevlett · Cited by 731 · see citing works
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447311 · Cited by 727 · see citing works
Lattice Signatures and Bimodal Gaussians
Ducas, L., Durmus, A., Lepoint, T., & Lyubashevsky, V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40041-4_3 · Cited by 568 · see citing works
Rainbow, a New Multivariable Polynomial Signature Scheme
Ding, J., & Schmidt, D. S. (2005) · Lecture notes in computer science · doi:10.1007/11496137_12 · Cited by 491 · see citing works
Corcoles, A. D., Magesan, E., Srinivasan, S. J., Cross, A. W., Steffen, M., Gambetta, J., & Chow, J. M. (2015) · Nature Communications · doi:10.1038/ncomms7979 · Cited by 487 · see citing works
Procedure for systematically tuning up cross-talk in the cross-resonance gate
Sheldon, S., Magesan, E., Chow, J. M., & Gambetta, J. (2016) · Physical Review A · doi:10.1103/physreva.93.060302 · Cited by 476 · see citing works
How to Achieve a McEliece-Based Digital Signature Scheme
Courtois, N. T., Finiasz, M., & Sendrier, N. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45682-1_10 · Cited by 440 · see citing works
SPHINCS: Practical Stateless Hash-Based Signatures
Bernstein, D. J., Hopwood, D., Hülsing, A., et al. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46800-5_15 · Cited by 378 · see citing works
Ultra-low-power superconductor logic
Herr, Q. P., Herr, A. Y., Oberg, O. T., et al. (2011) · Journal of Applied Physics · doi:10.1063/1.3585849 · Cited by 337 · see citing works
XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions
Buchmann, J. A., Dahmen, E., & Hülsing, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25405-5_8 · Cited by 326 · see citing works
Quantum lower bounds for the collision and the element distinctness problems
Aaronson, S., & Shi, Y. (2004) · Journal of the ACM · doi:10.1145/1008731.1008735 · Cited by 323 · see citing works
Implementing a strand of a scalable fault-tolerant quantum computing fabric
Chow, J. M., Gambetta, J., Magesan, E., Abraham, D. W., Cross, A. W., Johnson, B., Masluk, N. A., Ryan, C. A., Smolin, J. A., Srinivasan, S. J., et al. (2014) · Nature Communications · doi:10.1038/ncomms5015 · Cited by 280 · see citing works
Quantum circuits of T-depth one
Selinger, P. (2012) · arXiv.org · doi:10.1103/physreva.87.042302 · Cited by 252 · see citing works
Universal Fault-Tolerant Quantum Computation with Only Transversal Gates and Error Correction
Paetznick, A., & Reichardt, B. W. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.090505 · Cited by 244 · see citing works
Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms
Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-70697-9_9 · Cited by 212 · see citing works
Process verification of two-qubit quantum gates by randomized benchmarking
Corcoles, A. D., Gambetta, J., Chow, J. M., Smolin, J. A., Ware, M., Strand, J., Plourde, B. L. T., & Steffen, M. (2013) · Physical Review A · doi:10.1103/physreva.87.030301 · Cited by 210 · see citing works
Ultrafast Quantum Gates in Circuit QED
Romero, G., Ballester, D., Wang, Y., Scarani, V., & Solano, E. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.120501 · Cited by 207 · see citing works
QUARTZ, 128-Bit Long Digital Signatures
Patarin, J., Courtois, N. T., & Goubin, L. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45353-9_21 · Cited by 167 · see citing works
Revisiting Lattice Attacks on Overstretched NTRU Parameters
Kirchner, P., & Fouque, P.-A. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56620-7_1 · Cited by 133 · see citing works
Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures
Nguyễn, P. Q., & Regev, O. (2006) · Lecture notes in computer science · doi:10.1007/11761679_17 · Cited by 130 · see citing works
Estimating the Cost of Generic Quantum Pre-image Attacks on SHA-2 and SHA-3
Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., & Schanck, J. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-69453-5_18 · Cited by 128 · see citing works
Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures
Ducas, L., & Nguyễn, P. Q. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34961-4_27 · Cited by 109 · see citing works
Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem
Biryukov, A., & Khovratovich, D. (2017) · Ledger · doi:10.5195/ledger.2017.48 · Cited by 98 · see citing works
Scherer, A., Valiron, B., Mau, S.-C., Alexander, S., van den Berg, E., & Chapuran, T. E. (2017) · Quantum Information Processing · doi:10.1007/s11128-016-1495-5 · Cited by 73 · see citing works
Selecting Parameters for the Rainbow Signature Scheme
Petzoldt, A., Bulygin, S., & Buchmann, J. A. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12929-2_16 · Cited by 66 · see citing works
Pessl, P., Bruinderink, L. G., & Yarom, Y. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3134023 · Cited by 65 · see citing works
Smart Contracts Make Bitcoin Mining Pools Vulnerable
Velner, Y., Teutsch, J., & Luu, L. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70278-0_19 · Cited by 65 · see citing works
Practical Lattice-Based Digital Signature Schemes
Howe, J., Pöppelmann, T., O'Neill, M. P., O’Sullivan, E., & Güneysu, T. E. (2015) · ACM Transactions on Embedded Computing Systems · doi:10.1145/2724713 · Cited by 59 · see citing works
An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation
Akleylek, S., Bindel, N., Buchmann, J. A., et al. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-31517-1_3 · Cited by 58 · see citing works
Optimized cross-resonance gate for coupled transmon systems
Kirchhoff, S., Keßler, T., Liebermann, P., Assémat, E., Machnes, S., Motzoi, F., & Wilhelm, F. K. (2018) · Physical Review A · doi:10.1103/physreva.97.042348 · Cited by 53 · see citing works
Cuckoo Cycle: A Memory Bound Graph-Theoretic Proof-of-Work
Tromp, J. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48051-9_4 · Cited by 50 · see citing works
Generalized quantum search with parallelism
Gingrich, R. M., Williams, C. P., & Cerf, N. J. (2000) · Physical Review A · doi:10.1103/physreva.61.052313 · Cited by 44 · see citing works
Fault Tolerance with Noisy and Slow Measurements and Preparation
Paz-Silva, G. A., Brennen, G. K., & Twamley, J. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.100501 · Cited by 37 · see citing works
Self-citationOne-Time Signatures Revisited: Have They Become Practical?
Naor, D., Shenhav, A., & Wool, A. (2005) · Cited by 34 · see citing works
Robustness of error-suppressing entangling gates in cavity-coupled transmon qubits
Deng, X., Barnes, E., & Economou, S. E. (2017) · Physical review. B./Physical review. B · doi:10.1103/physrevb.96.035441 · Cited by 32 · see citing works
Quantum linear systems algorithm with exponentially improved dependence on precisionPreprint
Childs, A. M., Kothari, R., & Somma, R. D. (2015) · arXiv (Cornell University) · Cited by 31 · see citing works
Reversible circuit compilation with space constraintsPreprint
Parent, A., Roetteler, M., & Svore, K. M. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.00377 · Cited by 28 · see citing works
Sealing the Leak on Classical NTRU Signatures
Melchor, C. A., Boyen, X., Deneuville, J.-C., et al. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11659-4_1 · Cited by 21 · see citing works
High Performance of Hash-based Signature Schemes
Karina, A., ́opez, J. L., & Cabral, R. (2017) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2017.080358 · Cited by 15 · see citing works
Quantum linear systems algorithm with exponentially improved dependence on precision
Somma, R. D., Childs, A. M., & Kothari, R. (2016) · Bulletin of the American Physical Society · Cited by 14 · see citing works
Measurement-free implementations of small-scale surface codes for quantum-dot qubits
Ercan, H., Ghosh, J., Crow, D., Premakumar, V. N., Joynt, R., Friesen, M. G., & Coppersmith, S. N. (2018) · Physical Review A · doi:10.1103/physreva.97.012318 · Cited by 14 · see citing works
Estimating the Resources for Quantum Computation with the QuRE Toolbox
Suchara, M., Faruque, A. I., Lai, C., Paz-Silva, G. A., Chong, F. T., & Kubiatowicz, J. D. (2013) · UC Berkeley · Cited by 6 · see citing works
A Quantum "Magic Box" for the Discrete Logarithm Problem.Preprint
Kaliski, B. S. (2017) · IACR Cryptology ePrint Archive · Cited by 3 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- IBM. "IBM Makes Quantum Computing Available on IBM Cloud to Accelerate Innovation." (Accessed 2 October 2018) https://www-03.ibm.com/press/us/en/pressrelease/49661.wss.
Cited by
Sorted by citations
Privacy-Preserving Solutions for Blockchain: Review and Challenges
Bernal Bernabe, J., Canovas, J. L., Hernandez-Ramos, J. L., Torres Moreno, R., & Skarmeta, A. (2019) · IEEE Access · doi:10.1109/access.2019.2950872 · Cited by 430 · see citing works
“With the upcoming Quantum Computing, some proof-ofwork algorithms and signatures are under risk [91].”
BackgroundApplications of blockchain in unmanned aerial vehicles: A review
Alladi, T., Chamola, V., Sahu, N., & Guizani, M. (2020) · Vehicular Communications · doi:10.1016/j.vehcom.2020.100249 · Cited by 274 · see citing works
A New Lattice-Based Signature Scheme in Post-Quantum Blockchain Network
Li, C.-Y., Chen, X.-B., Chen, Y.-L., Hou, Y.-Y., & Li, J. (2019) · IEEE Access · doi:10.1109/access.2018.2886554 · Cited by 126 · see citing works
Quantum-resistance in blockchain networks
Allende, M., León, D. L., Cerón, S., Pareja, A., Pacheco, E., Leal, A., Da Silva, M., Pardo, A., Jones, D., Worrall, D. J., et al. (2023) · Scientific Reports · doi:10.1038/s41598-023-32701-6 · Cited by 109 · see citing works
“Another study by researchers in Singapore, Australia, and France claimed in 2017 that quantum computers will be large and robust enough to break Bitcoin keys in 10 minutes by 2017 [56].”
Background
- Authors
- Aggarwal, D., Brennen, G., Lee, T., Santha, M., & Tomamichel, M.
- Affiliations
- Centre for Quantum Technologies (SG)
- Macquarie University (AU)
- University of Technology Sydney (AU)
- Venue
- Ledger
- Published
- 2018-10-17
- Volume
- 3
- ISSN
- 2379-5980 (ISSN-L)
- OpenAlex
- W2766522683
- Cited by
- 231
- References
- 57
- Citations by year
- 2026: 34 · 2025: 28 · 2024: 10 · 2023: 25 · 2022: 25 · 2021: 32 · 2020: 41 · 2019: 21 · 2018: 14 · 2017: 1
- FWCI
- 43.45
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Locations
- Ledger (publishedVersion, cc-by)
- RePEc: Research Papers in Economics (submittedVersion)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- UTS ePRESS (University of Technology Sydney) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Research Foundation (NRF-NRFF2013-13)
- National Research Foundation Singapore (NRF-NRFF 2013-13, NRF RF Award No.~NRF-NRFF2013-13)
- Topics
- Physical Sciences › Computer Science › Information Systems › Blockchain Technology Applications and Security
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- quantum computing threats, Bitcoin, cryptocurrency, proof-of-work, quantum advantage, ECDSA, Shor's algorithm, post-quantum cryptography, blockchain security
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
