Quantum Attacks on Bitcoin, and How to Protect Against Them

Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, Marco Tomamichel

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.


Full Text:

PDF OPEN REVIEW

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.




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

Refbacks

  • There are currently no refbacks.




Copyright (c) 2018 Marco Tomamichel

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.