Quantum Attacks on Bitcoin, and How to Protect Against Them

Authors

  • Divesh Aggarwal Centre for Quantum Technologies, NUS, Singapore
  • Gavin Brennen Macquarie University
  • Troy Lee University of Technology Sydney
  • Miklos Santha CNRS, IRIF, Universite Paris Diderot Centre for Quantum Technologies, NUS, Singapore
  • Marco Tomamichel University of Technology Sydney http://orcid.org/0000-0001-5410-3329

DOI:

https://doi.org/10.5195/ledger.2018.127

Abstract

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.

References

Aaronson, S., Shi, Y. “Quantum Lower Bounds for the Collision and the Element Distinctness Problems.” Journal of the ACM 51.4 595–605 (2004). https://doi.org/10.1145/1008731.1008735.

Akleylek, S., Bindel, N., Buchmann, J., Kramer, J., Marson, G. “An Efficient Lattice-Based Signature Scheme with Provably Secure Instantiation.” In D. Pointcheval, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology–AFRICACRYPT 2016, 8th International Conference on Cryptology in Africa. Berlin: Springer 44–60 (2016) https://doi.org/10.1007/978-3-319-31517-1_3.

Ambainis, A. “Quantum Walk Algorithm for Element Distinctness.” SIAM Journal on Computing 37.1 210–239 (2007) https://doi.org/10.1137/S0097539705447311.

Back, A. “Hashcash–A Denial of Service Counter-Measure.” Hashcash.org (2002) (accessed 2 October 2018) http://www.hashcash.org/papers/hashcash.pdf.

Barends, R., et al. “Superconducting Quantum Circuits at the Surface Code Threshold for Fault Tolerance.” Nature 508.7497 500–503 (2014) https://doi.org/10.1038/nature13171.

Bellare, M., Rogaway, P. “Random Oracles are Practical: A Paradigm for Designing Efficient Protocols.” In CCS ’93 Proceedings of the 1st ACM Conference on Computer and Communications Security. New York: Association for Comuting Machinery 62–73 (1993) https://doi.org/10.1145/168588.168596.

Bennett, C., Bernstein, E., Brassard, G., Vazirani, U. “Strengths and Weaknesses of Quantum Computing.” SIAM Journal on Computing 26.5 1510–1523 (1997) https://doi.org/10.1137/S0097539796300933.

Bernstein, D. J., et al. “SPHINCS: Practical Stateless Hash-Based Signatures.” In E. Oswald, M. Fischlin (Eds.), Advances in Cryptology–EUROCRYPT 2015, 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015. Berlin: Springer 368–397 (2015) https://doi.org/10.1007/978-3-662-46800-5_15.

Bindel, N., et al. “Submission to NIST’s post-quantum project: Lattice-Based Digital Signature Scheme qTESLA.” (2018) (accessed 2 October 2018) Full list of submissions and associated documentation can be found at https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions.

Biryukov, A., Khovratovich, D. “Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem.” Ledger 2 1–30 (2017). https://doi.org/10.5195/ledger.2017.48.

Boyer, M., Brassard, G., Høyer, P., Tapp, A. “Tight Bounds on Quantum Searching.” Fortschritte der Physik 46.4-5 493–505 (1998) https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.

Buchmann, J., Dahmen, E., H¨ulsing, A. “XMSS–A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions.” In B. Yang (Ed.), Post-Quantum Cryptography, 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29–December 2, 2011. Berlin: Springer 117–129 (2011) https://doi.org/10.1007/978-3-642-25405-5_8.

Buterin, V. “Bitcoin Is Not Quantum-Safe, and How We Can Fix It When Needed.” Bitcoin Magazine (2013) (accessed 2 October 2018) http://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150/.

Childs, A. M., Kothari, R., Somma, R. “Quantum Linear Systems Algorithm with Exponentially Improved Dependence on Precision.” arXiv (2015) (accessed 2 October 2018) https://www.arxiv.org/abs/1511.02306.

Chow, J. M., et al. “Implementing a Atrand of a Scalable Fault-Tolerant Quantum Computing Fabric.” Nature Communications 5 https://doi.org/10.1038/ncomms5015.

Corcoles, A. D., et al. “Process Verification of Two-Qubit Quantum Gates by Randomized Benchmarking.” Physical Review A 87.3 030301 (2013) https://www.doi.org/10.1103/PhysRevA.87.030301.

Corcoles, A., et al. “Demonstration of a Quantum Error Detection Code Using a Square Lattice of Four Superconducting Qubits.” Nature Communications 6 6979 (2015) https://www.doi.org/10.1038/ncomms7979.

Courtois, N., Finiasz, M., Sendrier, N. “How to Achieve a McEliece-Based Digital Signature Scheme.” In C. Boyd (Ed.), Advances in Cryptology—ASIACRYPT 2001. Berlin: Springer 157–174 (2001) https://doi.org/10.1007/3-540-45682-1_10.

de Oliveira, A. K. D., Lopez, J., Cabral, R. “High Performance of Hash-Based Signature Schemes.” International Journal of Advanced Computer Science and Applications 8.3 421–432 (2017) http://dx.doi.org/10.14569/IJACSA.2017.080358.

Deng, X.-H., Barnes, E., Economou, S. E. “Robustness of Error-Suppressing Entangling Gates in Cavity-Coupled Transmon Qubits.” Physical Review B 96.3 035441 (2017) https://www.doi.org/10.1103/PhysRevB.96.035441.

Ding, J., Schmidt, D. “Rainbow, A New Multivariable Polynomial Signature Scheme.” In J. Ioannidis, Keromytis, M. Yung (Eds.), Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA, June 7-10, 2005. Berlin: Springer 164–175 (2005) https://doi.org/10.1007/11496137_12.

Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V. “Lattice Signatures and Bimodal Gaussians.” In R. Canetti, J. A. Garay (Eds.), Advances in Cryptology–CRYPTO 2013, 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Berlin: Springer 40–56 (2013) https://doi.org/10.1007/978-3-642-40041-4_3.

Ducas, L., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehl´e, D. “CRYSTALS–Dilithium: Digital Signatures from Module Lattices.” IACR Cryptology ePrint Archive, 2017 (2017) (accessed 2 October 2018) https://eprint.iacr.org/2017/633.pdf.

Ducas, L., Nguyen, P. Q. “Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures.” In X.Wang, K. Sako (Eds.), Advances in Cryptology–ASIACRYPT 2012, 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Berlin: Springer 433–450 (2012) https://doi.org/10.1007/978-3-642-34961-4_27.

Ekmel Ercan, H., et al. “Measurement-Free Implementations of Small-Scale Surface Codes for Quantum Dot Qubits.” arXiv (2017) (accessed 2 October 2018) https://arxiv.org/abs/1708.08683.

Fouque, P.-A., et al. “FALCON: Fast-Fourier Lattice-Based Compact Signatures over NTRU.” (2018) (accessed 2 October 2018) https://falcon-sign.info/.

Fowler, A. G., Mariantoni, M., Martinis, J. M., Cleland, A. N. “Surface Codes: Towards Practical Large-Scale Quantum Computation.” Phys. Rev. A 86 032324 (2012) https://www.doi.org/10.1103/PhysRevA.86.032324.

Gentry, C., Peikert, C., Vaikuntanathan, V. “Trapdoors for Hard Lattices and New Cryptographic Constructions.” In STOC ’08 Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. New York: Association for Computing Machinery 197–206 (2008) https://doi.org/10.1145/1374376.1374407.

Gingrich, R. M., Williams, C. P., Cerf, N. J. “Generalized Quantum Search with Parallelism.” Physical Review A 61.5 052313 (2000) https://link.aps.org/doi/10.1103/PhysRevA.61.052313.

Grover, L. K. “A Fast Quantum Mechanical Algorithm for Database Search.” In STOC ’96 Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. New York: Association for Computing Machinery 212–219 (1996) https://doi.org/10.1145/237814.237866.

Harrow, A. W., Hassidim, A., Lloyd, S. “Quantum Algorithm for Linear Systems of Equations.” Physical Review Letters 103.15 150502 (2009) https://link.aps.org/doi/10.1103/PhysRevLett.103.150502.

Herr, Q. P., Herr, A. Y., Oberg, O. T., Ioannidis, A. G. “Ultra-Low-Power Superconductor Logic.” Journal of Applied Physics 109.10 103903 (2011) http://www.doi.org/10.1063/1.3585849.

Howe, J., Poppelmann, T., O’Neill, M., O’Sullivan, E., Guneysu, T. “Practical Lattice-Based Digital Signature Schemes.” ACM Transactions on Embedded Computing Systems 14.3 41:1–41:24 (2015) https://doi.acm.org/10.1145/2724713.

IBM. “IBM Doubles Compute Power for Quantum Systems, Developers Execute 300K+ Experiments on IBM Quantum Cloud.” (accessed 2 October 2018) https://developer.ibm.com/dwblog/2017/quantum-computing-16-qubit-processor/.

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.

Kaliski, B. S., Jr. “A Quantum “Magic Box” for the Discrete Logarithm Problem.” IACR Cryptology ePrint Archive (2017) (accessed 2 October 2018) https://eprint.iacr.org/2017/745.

Kirchhoff, S., et al. “Optimized Cross-Resonance Gate for Coupled Transmon Systems.” arXiv (2017) (accessed 2 October 2018) https://arxiv.org/abs/1701.01841.

Kirchner, P., Fouque, P. “Revisiting Lattice Attacks on Overstretched NTRU Parameters.” In J.-S. Coron, J. B. Nielsen (Eds.), Advances in Cryptology–EUROCRYPT 2017, 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017. Berlin: Springer 3–26 (2017) https://doi.org/10.1007/978-3-319-56620-7_1.

Larimer, D. “Momentum–A Memory-Hard Proof-of- Work via Finding Birthday Collisions.” (2014) (accessed 2 October 2018) http://www.hashcash.org/papers/momentum.pdf.

Leighton, F. T., Micali, S. “Large Provably Fast and Secure Digital Signature Schemes Based on Secure Hash Functions.” Google Patents (accessed 2 October 2018) https://patents.google.com/patent/US5432852A/en.

Lyubashevsky, V. “Lattice SignaturesWithout Trapdoors.” In D. Pointcheval, T. Johansson (Eds.), Advances in Cryptology–EUROCRYPT 2012, 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Berlin: Springer 738–755 (2012) https://doi.org/10.1007/978-3-642-29011-4_43.

Matthew, A., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J. “Estimating the Cost of Generic Quantum Pre-Image Attacks on SHA-2 and SHA-3.” IACR Cryptology ePrint Archive (2016) (accessed 2 October 2018) https://eprint.iacr.org/2016/992.

Melchor, C. A., Boyen, X., Deneuville, J.-C., Gaborit, P. “Sealing the Leak on Classical NTRU Signatures.” In M. Mosca (Ed.), Post-Quantum Cryptography, 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014. Berlin: Springer 1–21 (2014) https://doi.org/10.1007/978-3-319-11659-4_1.

Nakamoto, S. “Bitcoin: A Peer-to-Peer Electronic Cash System.” Bitcoin.org (2009) (accessed 2 October 2018) http://www.bitcoin.org/pdf.

Naor, D., Shenhav, A., Wool, A. “One-Time Signatures Revisited: Have They Become Practical?” IACR Cryptology ePrint Archive (2005) (accessed 2 October 2018) https://eprint.iacr.org/2005/442.

Nguyen, P. Q., Regev, O. “Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures.” In S. Vaudenay (Ed.), Advances in Cryptology–EUROCRYPT 2006, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006. Berlin: Springer 271–288 (2006) https://doi.org/10.1007/11761679_17.

Paetznick, A., Reichardt, B. W. “Universal Fault-Tolerant Quantum Computation with Only Transversal Gates and Error Correction.” Physical Review Letters 111.9 090505 (2013) https://link.aps.org/doi/10.1103/PhysRevLett.111.090505.

Parent, A., R¨otteler, M., Svore, K. M. “Reversible Circuit Compilation with Space Constraints.” CoRR (arXiv) (2015) (accessed 2 October 2018) https://arxiv.org/abs/1510.00377.

Patarin, J., Courtois, N., Goubin, L. “Quartz, 128-Bit Long Digital Signatures.” In D. Naccache (Ed.), Topics in Cryptology–CT-RSA 2001, The Cryptographers’ Track at RSA Conference 2001 San Francisco, CA, USA, April 8–12, 2001. Berlin: Springer 282–297 (2001) https://doi.org/10.1007/3-540-45353-9_21.

Paz-Silva, G. A., Brennen, G. K., Twamley, J. “Fault Tolerance with Noisy and Slow Measurements and Preparation.” Physical Review Letters 105.10 100501 (2010) https://link.aps.org/doi/10.1103/PhysRevLett.105.100501.

Pessl, P., Bruinderink, L., Yarom, Y. “To BLISS-B or Not to Be—Attacking strongSwan’s Implementation of Post-Quantum Signatures.” In CCS ’17 Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: Association from Computing Machinery 1843–1855 (2017) https://doi.org/10.1145/3133956.3134023.

Petzoldt, A., Bulygin, S., Buchmann, J. “Selecting Parameters for the Rainbow Signature Scheme.” In N. Sendrier (Ed.), Post-Quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Berlin: Springer 218–240 (2010) https://doi.org/10.1007/978-3-642-12929-2_16.

Reynolds, M. “Google on Track for Quantum Computer Breakthrough by End of 2017.” New Scientist (accessed 2 October 2018) https://www.newscientist.com/article/2138373-google-on-track-for-quantum-computer-breakthrough-by-end-of-2017/.

Roetteler, M., Naehrig, M., Svore, K., Lauter, K. “Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms.” arXiv (2017) (accessed 2 October 2018) https://arxiv.org/abs/1706.06752.

Romero, G., Ballester, D., Wang, Y. M., Scarani, V., Solano, E. “Ultrafast Quantum Gates in Circuit QED.” Physical Review Letters 108.12 120501 (2012) https://www.doi.org/10.1103/PhysRevLett.108.120501.

Scherer, A., Valiron, B., Mau, S.-C., Alexander, S., van den Berg, E., Chapuran, T. E. “Concrete Resource Analysis of the Quantum Linear-System Algorithm Used to Compute the Electromagnetic Scattering Cross Section of a 2D Target.” Quantum Information Processing 16.3 60 (2017) https://doi.org/10.1007/s11128-016-1495-5.

Selinger, P. “Quantum Circuits of $T$-Depth One.” Physical Review A 87.4 042302 (2013) https://link.aps.org/doi/10.1103/PhysRevA.87.042302.

Sheldon, S., Magesan, E., Chow, J. M., Gambetta, J. M. “Procedure for Systematically Tuning Up Cross-Talk in the Cross-Resonance Gate.” Physical Review A 93.6 060302 (2016) https://www.doi.org/10.1103/PhysRevA.93.060302.

Shor, P. W. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Review 41.2 303–332 (1999) https://doi.org/10.1137/S0036144598347011.

Suchara, M., Faruque, A., Lai, C.-Y., Paz, G., Chong, F., Kubiatowicz, J. D. “Estimating the Resources for Quantum Computation with the QuRE Toolbox.” EECS Department, University of California, Berkeley (accessed 2 October 2018) http://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-119.html.

Tromp, J. “Cuckoo Cycle: A Memory Bound Graph-Theoretic proof-of-work.” In M. Brenner, N. Christin, B. Johnson, K. Rohloff (Eds.), Financial Cryptography and Data Security FC 2015 International Workshops, BITCOIN, WAHC, and Wearable, San Juan Puerto Rico, January 30, 2015 Revised Selected Papers. New York: Springer 49–62 (2015) https://doi.org/10.1007/978-3-662-48051-9_4.

Velner, Y., Teutsch, J., Luu, L. “Smart Contracts Make Bitcoin Mining Pools Vulnerable.” IACR Cryptology ePrint Archive (2017) (accessed 2 October 2018) http://eprint.iacr.org/2017/230.

Ledger Volume 3 (2018)

Downloads

Published

2018-10-17

How to Cite

Aggarwal, D., Brennen, G., Lee, T., Santha, M., & Tomamichel, M. (2018). Quantum Attacks on Bitcoin, and How to Protect Against Them. Ledger, 3. https://doi.org/10.5195/ledger.2018.127

Issue

Vol. 3 (2018)

Section

Research Articles

License

Authors who publish with this journal agree to the following terms:

  1. The Author retains copyright in the Work, where the term “Work” shall include all digital objects that may result in subsequent electronic publication or distribution.
  2. Upon acceptance of the Work, the author shall grant to the Publisher the right of first publication of the Work.
  3. The Author shall grant to the Publisher and its agents the nonexclusive perpetual right and license to publish, archive, and make accessible the Work in whole or in part in all forms of media now or hereafter known under a Creative Commons Attribution 4.0 International License or its equivalent, which, for the avoidance of doubt, allows others to copy, distribute, and transmit the Work under the following conditions:
    1. Attribution—other users must attribute the Work in the manner specified by the author as indicated on the journal Web site;
    with the understanding that the above condition can be waived with permission from the Author and that where the Work or any of its elements is in the public domain under applicable law, that status is in no way affected by the license.
  4. The Author is able to enter into separate, additional contractual arrangements for the nonexclusive distribution of the journal's published version of the Work (e.g., post it to an institutional repository or publish it in a book), as long as there is provided in the document an acknowledgement of its initial publication in this journal.
  5. Authors are permitted and encouraged to post online a prepublication manuscript (but not the Publisher’s final formatted PDF version of the Work) in institutional repositories or on their Websites prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work. Any such posting made before acceptance and publication of the Work shall be updated upon publication to include a reference to the Publisher-assigned DOI (Digital Object Identifier) and a link to the online abstract for the final published Work in the Journal.
  6. Upon Publisher’s request, the Author agrees to furnish promptly to Publisher, at the Author’s own expense, written evidence of the permissions, licenses, and consents for use of third-party material included within the Work, except as determined by Publisher to be covered by the principles of Fair Use.
  7. The Author represents and warrants that:
    1. the Work is the Author’s original work;
    2. the Author has not transferred, and will not transfer, exclusive rights in the Work to any third party;
    3. the Work is not pending review or under consideration by another publisher;
    4. the Work has not previously been published;
    5. the Work contains no misrepresentation or infringement of the Work or property of other authors or third parties; and
    6. the Work contains no libel, invasion of privacy, or other unlawful matter.
  8. The Author agrees to indemnify and hold Publisher harmless from Author’s breach of the representations and warranties contained in Paragraph 6 above, as well as any claim or proceeding relating to Publisher’s use and publication of any content contained in the Work, including third-party content.
  9. The Author agrees to digitally sign the Publisher’s final formatted PDF version of the Work.

Revised 7/16/2018. Revision Description: Removed outdated link.