Why can't a longer key combat quantum computers?

Question

Google's new quantum computer performed a calculation in 3.5 minutes that would have taken 10,000 years on a normal computer (so they claim: https://www.space.com/quantum-computer-milestone-supremacy.html).

So this is about 5 billion times faster, but why is this such a dire threat to bitcoin security? If Bitcoin core upgraded to increase the entropy of private keys by a mere 32 bits, this would increase the difficulty of a brute force attack by about 5 billion.

Why are people afraid that quantum computers will threaten the security of Bitcoin and other cryptocurrencies when you can just trivially increase the key size?

Answer 1

Quantum computing isn't simply faster. It is entirely different. Some computations are massively faster on a quantum computer, and other are not faster at all.

What has been demonstrated is meaningless: the "program" that was executed was in fact a randomly generated one, designed to be specifically hard on traditional computers, but easy on that specific type of quantum computer. It doesn't correspond to any real world application.

The real threat for Bitcoin from quantum computers comes from Shor's algorithm for discrete logarithms. While computing the discrete logarithm (private key) for a given 256-bit elliptic curve point (public key) on a traditional computer takes on average 2^128 EC multiplications (over 2^140 cpu cycles, all computers in the world couldn't do this given a time equal to the age of the universe), a sufficiently powerful quantum computer would be able to break it instantaneously.

The key point here is "sufficiently powerful" however. A practical quantum computer able to do this would need 1000s of logical qbits (which likely corresponds to 100000s of physical qbits; the machine Google demonstrated has 53), and billions of gates. A quantum computer with fewer gates or qbits is effectively useless for this task, and would reduce to traditional speeds. This is important: it's effectively an all or nothing; not something that gradually improves with increasing computing strength. At this point I don't think if it's even known whether such a machine is feasible to build, let alone at what cost.

As far as increasing key sizes goes, yes, that helps. It makes the speed of solving slower, even on a quantum computer, but not exponentially like on traditional systems. I believe that given an arbitrarily many qbits/gates quantum computer, doubling the size of the curve only makes breaking it 4 times slower - where on a traditional computer it would make it 2^128 times slower. However, it does increase the number of qbits needed from the machine (linearly) and the number of gates. Even if a particular key size at some point becomes vulnerable, it is very likely that a not very much bigger key size would in fact not be.