Quantum Threats to EVM-based Blockchains

Shor’s Algorithm [Peter W. Shor, 1994] makes it possible for a sufficiently powerful quantum computer to break the ECDSA algorithm. That is, starting from a transaction signed with an ECDSA private key, one can extract the public key and then derive the private key. This is the ultimate game over condition, as the attacker can then transfer any balance associated with the external owned account (EOA) at will.

In contrast, quantum computers pose no such (known) threat to hashing algorithms. Grover’s Algorithm [Lov K. Grover, 1996] (aka quantum search algorithm), reduces the search for collisions in Keccak-256 (Ethereum’s hash algorithm) from 2^256 to 2^128 which is less efficient than some generic collision search algorithms. (A quick peek ahead: this hashing resilience to quantum attacks will play a key role in our approach).

For the underlying cryptography, the National Institute of Standards and Technology (NIST) initiated a standardisation effort for quantum resilient signature schemes, and is currently evaluating a number of candidate schemes. All of these come with their own set of trade-offs, particularly when compared with key size, speed and re-use of the same key pair by the EVM family of blockchains [see B. Westerban for discussion].

In terms of the threat timeline, (i.e, how long until quantum hardware is capable of breaking ECDSA), estimates vary between experts. Many believe the threat is still in the distant future (e.g., Vitalik was famously quoted comparing quantum computing advances to going from hydrogen bombs to harnessing nuclear fusion).

For a systematic approach, the Global Risk Institute conducts an annual survey on the threat timeline of leading subject matter experts. According to its 2022 report, the “likelihood” estimates have been trending upwards from initial surveys. Nearly 25% of respondents estimated a 50% chance for the threat to materialise within a 10-year time window in light of recent advances (i.e., Google’s Quantum Supremacy & IBM Quantum System One) and the nation state competition (aka “quantum race”) with high levels of funding. The inevitable question, much like the plight of global warming, isn’t a question of ‘if’ - it’s a question of ‘when’.