Counterpoint to the article's interviewee claiming that the cryptopocalyse will occur with forewarning: Nation states may seek to keep QC advances secret.
Also, QC breakthroughs can happen overnight.
Combine those two realities and we could have an institution or govt wielding a Shor's-enabled QC in private without notice nor fanfare.
There is far more to be gained via silent espionage on the internet at large. It's worth far more than all cryptocurrency.
Whoever is hoarding pcap's encrypted with ECC will have a field day. This is the reason for the urgent push by NIST/NSA to roll out qc resistant crypto.
Cryptocurrency is a sensational sideshow in comparison.
On the other hand we've learned that claims of "10 years away" technology can be repeated for multiple decades. 10 years is the magic number for saying we have something promising but there are some unknowns left on the way.
My understanding is Bitcoin unspent transaction outputs (spendable bitcoins) are spendable depending on the script (some opcodes that are agreed upon). The most common is pay to public key hash.
So you not only need to solve secp256k1 ecdsa, but your bitcoin utxo is also protected by the hash function which derives the address.
Put another way, starting with an address, you need to reverse engineer a hash collision (super difficult) to find a public key as that has not been announced yet. Then find a private key for that.
So you need to break two technologies.
Also my understanding is that quantum can only reduce complexity by sqrt, so 2^256 problem is reduced only to 2^128 which is unsolvable.
I think we’re safe for now.
And if ecdsa does get broken, it will be more like “we can generate keys in 2 years” and practically speaking, everybody can transfer their bitcoin utxo’s to a new script by only exposing their public key for a short time (tens of minutes) into the transaction mempool. Not enough time to break it.
> Also my understanding is that quantum can only reduce complexity by sqrt, so 2^256 problem is reduced only to 2^128 which is unsolvable.
The sqrt speedup is for Grover's unstructured search algorithm, which is the only known quantum speedup for breaking hash functions such as RIPE160 protecting public keys in P2PKH. So it would still take on the order of 2^80 quantum steps to find a hash preimage.
But to find the private key corresponding to a given public key, Shor's algorithm provides exponential speedup, so a large scale quantum computer would completely break ECDSA.
There are large amounts of bitcoin protected only by P2PK (i.e. without the RIPE160 hash), or protected by P2PKH with already known public keys (from widespread key reuse), so Bitcoin would be quickly destroyed by successful application of Shor's algorithm alone.
That said, I consider projections of large scale quantum computers existing within 10 years wildly optimistic, even more so than nuclear fusion being "just a few decades away".
I wonder what the timeline will look like as each thing gets broken. This is only talking about the privacy of the wallet. There's the hashing to compute the next block, when that's broken the chain is no longer secure.
So the important thing is the timing of these events, when they happen, who knows first and for how long.
If asymmetric cryptography is broken, it won't only be Bitcoin wallets we have to worry about, we'll have problems everywhere to deal with.
9 comments
[ 0.24 ms ] story [ 31.7 ms ] threadAlso, QC breakthroughs can happen overnight.
Combine those two realities and we could have an institution or govt wielding a Shor's-enabled QC in private without notice nor fanfare.
Sure, the first few instances will be dismissed by the community as 'someone stole your keys', but after that I assume people would notice...
Whoever is hoarding pcap's encrypted with ECC will have a field day. This is the reason for the urgent push by NIST/NSA to roll out qc resistant crypto.
Cryptocurrency is a sensational sideshow in comparison.
So you not only need to solve secp256k1 ecdsa, but your bitcoin utxo is also protected by the hash function which derives the address.
Put another way, starting with an address, you need to reverse engineer a hash collision (super difficult) to find a public key as that has not been announced yet. Then find a private key for that.
So you need to break two technologies.
Also my understanding is that quantum can only reduce complexity by sqrt, so 2^256 problem is reduced only to 2^128 which is unsolvable.
I think we’re safe for now.
And if ecdsa does get broken, it will be more like “we can generate keys in 2 years” and practically speaking, everybody can transfer their bitcoin utxo’s to a new script by only exposing their public key for a short time (tens of minutes) into the transaction mempool. Not enough time to break it.
The sqrt speedup is for Grover's unstructured search algorithm, which is the only known quantum speedup for breaking hash functions such as RIPE160 protecting public keys in P2PKH. So it would still take on the order of 2^80 quantum steps to find a hash preimage.
But to find the private key corresponding to a given public key, Shor's algorithm provides exponential speedup, so a large scale quantum computer would completely break ECDSA.
There are large amounts of bitcoin protected only by P2PK (i.e. without the RIPE160 hash), or protected by P2PKH with already known public keys (from widespread key reuse), so Bitcoin would be quickly destroyed by successful application of Shor's algorithm alone.
That said, I consider projections of large scale quantum computers existing within 10 years wildly optimistic, even more so than nuclear fusion being "just a few decades away".
So the important thing is the timing of these events, when they happen, who knows first and for how long.
If asymmetric cryptography is broken, it won't only be Bitcoin wallets we have to worry about, we'll have problems everywhere to deal with.