Bitcoin, The Quantum Threat Is Approaching

The quantum threat isn’t imminent, but recent breakthroughs suggest the Bitcoin community was right to start major preparations.

The Google Threat

We wondered in April if we should erase Satoshi Nakamoto’s bitcoins before the arrival of the quantum computer . Google researchers give us a reason to dig deeper with a major breakthrough in quantum factoring.

Breaking classical cryptography is proving to be much easier than expected. The resources needed to break RSA-2048 have just been reduced by a factor of 20. This leap forward results from an optimization of Shor’s algorithm and improved error correction for quantum decoherence.

It now requires one million qubits to break RSA-2048, down from 20 million qubits before. That said, the largest quantum processor currently has only 1021 qubits (IBM’s Condor). Keep in mind that the difficulty of maintaining quantum coherence increases exponentially with the number of qubits.

Moreover, the quantum computer still cannot factor as small a number as 35. So, until proven otherwise, no tangible progress has been recorded despite all the big announcements regarding qubit count increases and error correction improvements.

In any case, it is food for thought. Especially as companies like Apple and Microsoft plan to adopt post-quantum cryptography this fall .

For the curious, here is the history of scientific breakthroughs that led to the quantum computer:

Is Bitcoin Threatened?

Google’s breakthrough involves Shor’s algorithm which, combined with a quantum computer, can solve the discrete logarithm problem exponentially faster than classical computers. Simply put, it is possible to derive a private key from a Bitcoin public key.

However, although this algorithm can efficiently solve both the factorization problem (affecting RSA) and the discrete logarithm problem (affecting ECDSA / Bitcoin), Bitcoin and its elliptic curve “secp256k1” are not directly impacted by Google’s recent advance.

Pauli Group’s founder warns, however, that ECDSA is generally easier to crack than RSA, and it’s not impossible that AI might optimize Shor’s algorithm to more easily break ECDSA (Bitcoin).

By the way (and this is important), note that merely doubling the public key length (for example, by using an elliptic curve “secp512k1”) only makes deriving the private key twice as hard using Shor’s algorithm. So the protection would still be insufficient.

According to quantum computer maker IonQ, the elliptic curve “secp32k1” could be broken by 2027. It’s 2029 for “secp256k1” (Bitcoin). These predictions, however, should be taken with a big grain of salt.

Thankfully, NIST is working on standardizing post-quantum cryptography algorithms. Three candidates are favored for digital signatures: CRYSTALS-Dilithium, SPHINCS+, and FALCON. These algorithms could theoretically replace ECDSA.

But it won’t be “free.” Signatures and keys are much larger, which will inevitably reduce on-chain transaction throughput. Creating and verifying signatures also takes much longer.

For example, for CRYSTALS-Dilithium Level I, a public key is 1,312 bytes and a signature is 2,420 bytes, far larger than current ECDSA (72 bytes) or Schnorr (64 bytes) signatures.

[NIST Level I security offers equivalent security to 128-bit keys, and Level V equates to 256-bit security]

In summary, the solution already exists, but we still need to choose the right algorithm. And everyone must manually migrate to post-quantum addresses.

BIP-360: Pay to Quantum Resistant Hash (P2QRH)

BIP-360 , proposed by Hunter Beast, is a “pragmatic first step” (soft fork) by introducing a new type of UTXO called “Pay to Quantum Resistant Hash” (P2QRH) whose addresses would start with “bc1r”.

Explanation:

Currently, a Bitcoin transaction (simultaneous destruction and creation of UTXOs) reveals a public key along with a signature based on the ECDSA algorithm.

BIP-360 proposes transactions include both ECDSA signatures and post-quantum signatures, similar to multi-sig transactions. This mix allows an ECDSA fallback if a flaw is discovered in the chosen post-quantum algorithm.

Hunter Beast advocates the FALCON algorithm which has the advantage of enabling signature aggregation. His first candidate (SQIsign) was eventually abandoned due to its slowness.

As mentioned earlier, there is a cost. Post-quantum public keys and signatures are much larger than a 64-byte Schnorr signature.

SLH-DSA (SPHINCS+) signatures can reach 29,000 bytes or more (or less) depending on parameters chosen. That means about 40 times fewer transactions per block! FALCON signatures are 20 times larger than Schnorr signatures and 13 times larger than ECDSA signatures.

Other proposals are on the table. Here is a list:

For example, the BIP “Quantum-Resistant Address Migration Protocol” (QRAMP) proposed by Agustin Cruz. This BIP plans a hard fork instead. In other words, bitcoins that do not migrate to post-quantum addresses would be lost forever.

In 2020, Deloitte estimated that 25% of bitcoins are linked to old address types vulnerable to quantum attacks.

How to protect your bitcoins?

Nowadays, “public keys” are not really public anymore. They are encoded by passing through quantum-resistant hash functions SHA-256 and RIPEMD-160. The resulting hash is known as the “Bitcoin address.”

However, public keys must be revealed at the time of transactions. They are therefore vulnerable as long as they remain in the mempool waiting for a miner to include them in a block.

The threat ends once the block propagates. Unless you make the mistake of sending funds back to the same address.

Here is a summary of a transaction to better understand:

Your wallet contains a UTXO of 1 BTC. This UTXO is public and contains information such as the amount (1 BTC) and a P2PKH (Pay-to-Public-Key-Hash) locking script.

Now imagine you make a payment of 0.5 BTC. You supply your public key and a signature to unlock the script and perform the transaction.

Since your UTXO is 1 BTC, this is what the transaction generates:

-0.5 BTC to the recipient’s address.
-0.0001 BTC to the miner’s address (transaction fee).
-0.4999 BTC sent back to a NEW change address generated by your wallet.

Each of these three transactions creates a new UTXO. The 0.4999 BTC change linked to a new Bitcoin address (a new public key) is no longer vulnerable.

On the other hand, you should never send new funds back to the original address that contained 1 BTC since it is now known to everyone.

Here is another article on the quantum threat: Bitcoin and the Quantum Threat .