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.
Multi-source extractors are functions that extract uniform randomness from multiple ( weak ) sources of randomness. Quantum multi-source extractors were considered by Kasher and Kempe [1] (for the quantum independent adversary and the quantum bounded storage adversary ), Chung, Li and Wu [2] (for the general entangled adversary ) and Arnon-Friedman, Portmann and Scholz [3] (for the quantum Markov adversary ). One of the main objectives of this work is to unify all the existing quantum multi-source adversary models. We propose two new models of adversaries: 1) the quantum measurement adversary (qma), which generates side information using entanglement and on post-measurement and 2) the quantum communication adversary (qca), which generates side information using entanglement and communication between multiple sources. We show that, 1) qma is the strongest adversary among all the known adversaries, in the sense that the side information of all other adversaries can be generated by qma. 2) The (generalized) inner-product function (in fact a general class of two-wise independent functions) continues to work as a good extractor with matching parameters as that of Chor and Goldreich [4] against classical adversaries. 3) A non-malleable extractor proposed by Li [5] (against classical adversaries) continues to be secure against quantum side information. This result implies a non-malleable extractor result of Aggarwal, Chung, Lin and Vidick [6] with uniform seed. We strengthen their result via a completely different proof to make the non-malleable extractor of Li secure against quantum side information even when the seed is not uniform. 4) A modification (working with weak local randomness instead of uniform local randomness) of the Dodis and Wichs [7] protocol for privacy-amplification is secure against active quantum adversaries (those who arbitrarily modify the messages exchanged in the protocol). This strengthens on a recent result due to Aggarwal, Chung, Lin and Vidick [6] which uses uniform local randomness. 5) A tight efficiency lower bound for the (generalized) inner-product function (in fact a general class of two-wise independent functions).