Bitcoin, the quantum threat approaches

The quantum threat is not for tomorrow morning, but the recent breakthroughs suggest that the Bitcoina community well made to launch the big maneuvers.

Google threat

We wondered in April whether we had to erase the bitcoins of Satoshi Nakamoto before the arrival of the quantum computer. Google researchers give us the opportunity to dig the subject a little more due to a major advance in the field of quantum factorization.

Breaking classic cryptographs is much easier than anticipated. The resources necessary to break the RSA-2048 encryption have just been reduced by 20. This leap forward is the result of optimization of the Shor algorithm and a better correction of the errors linked to quantum decoherence.

It takes a million qubits now to break RSA-2048, compared to 20 million qubits before. That said, the largest quantum processor currently has only 1021 qubits (IBM's condor). Knowing that the difficulty in maintaining quantum consistency increases exponentially with the number of qubits.

In addition, the quantum computer still does not manage to de facto a number as small of 35. So, until proven otherwise, we have not recorded any tangible progress despite all the great announcements concerning the increase in the number of qubits and the improvement of the correction of errors.

Anyway, there is still material for reflection. Especially since firms like Apple and Microsoft intend to adopt post-quantic cryptography this fall.

Here for the curious the history of scientific breakthroughs that led to the quantum computer:

Bitcoin threatened?

Google's breakthrough concerns Shor algorithm which, combined with the quantum computer, can solve the problem of discreet logarithm exponentially more quickly than with conventional computers. Clearly, it is possible to obtain a private key from a Bitcoin public key.

But although this algorithm can effectively solve both the factorization problem (affecting RSA) and the problem of discreet logarithm (affecting ECDSA / Bitcoin), bitcoin and its elliptical curve “SECP256K1” are not directly impacted by the recent advancement of Google.

The founder of Pauli Group warns, however, that ECDSA is generally easier to break than RSA, and that it is not impossible that AI manages to optimize Shor algorithm To more easily break ECDSA (Bitcoin).

By the way (and this is important), note that the simple fact of doubling the length of the public key (for example, using an elliptical curve “SECP512K1”) only makes you make the derivation of the private key twice more difficult via the Shor algorithm. Protection would therefore be insufficient.

According to the quantum computer manufacturer IONQ, the elliptical curve “SECP32K1” could be broken in 2027. It is 2029 for the “SECP256K1” (Bitcoin). However, these forecasts are to be taken with large tweezers.

Fortunately, the NIST is working on the standardization of post-quantic cryptography algorithms. Three candidates are on the rise for digital signatures: Crystals-Dilithium, Sphincs+ and Falcon. These algorithms could theoretically replace ECDSA.

But it will not be “free”. Signatures and keys are much larger, which will necessarily reduce the onchain transactions. Creating and checking the signatures takes so much more time.

For example, for Crystal-Dilithium Level I, a public key represents 1,312 bytes and a 2,420 bytes signature, much more than the ECDSA (72 bytes) or Schnorr (64 bytes) signatures.

[Le niveau de sécurité Level I du NIST offre une sécurité équivalente à des clés de 128 bits, et le Level V une sécurité de 256 bits]

In short, the parade already exists, but you still have to choose the algorithm that is fine. And that everyone migrates manually towards post-quantic addresses.

BIP-360: Pay to quantum resistant hash (p2qrh)

BIP-360proposed by Hunter Beast, is a “First pragmatic step” (Soft Fork) by introducing a new type of UTXO called “Pay to Quantum resistant hash” (P2QRH) whose addresses would begin with “BC1R”.

Explanation :

Currently, a Bitcoin transaction (destruction and simultaneous creation of UTXO) is taking place by revealing a public key as well as a signature based on the ECDSA algorithm.

BIP-360 proposes that transactions have both ECDSA signatures and post-quantic signatures, like multi-SIG transactions. This mix allows you to have the ECDSA rescue solution if a flaw is discovered in the post-quantic algorithm chosen.

Hunter Beast pleads for the Falcon algorithm which has the advantage of allowing the aggregation of signatures. His first candidate (Sqisign) was finally abandoned because of his slowness.

As said above, there is a price to pay. Public keys and post-skills signatures are much larger than a Schnorr signature of 64 bytes.

SLH-DSA signatures (sphincs+) can reach 29,000 bytes, or even more (or less) depending on the parameters chosen. About 40 times less 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:

Note, for example, the BIP “Quantum-Résistant Address Migration Protocol” (Qramp) proposed by Agustin Cruz. This BIP rather plans a hard fork. In other words, bitcoins that would not migrate to post-quantity addresses would be lost forever.

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

How to protect your bitcoins?

Nowadays, the “public keys” are no longer really public. They are encoded while passing the Hitting functions resistant to the quantum computer SHA-256 and RIPEMD-160 to the reel. The resulting hash is called a “bitcoin address”.

However, public keys must be revealed at the time of transactions. They are therefore vulnerable all the time they spend in Mempool while waiting for a minor to add it to a block.

The threat stops as soon as the block spreads. Unless you make the mistake of returning funds to the same address.

Here is the summary of a transaction to fully understand:

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

Now imagine that you make a payment of 0.5 BTC. You bring your public key and a signature to unlock the script in order to carry out the transaction.

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

-0.5 BTC to the address of the recipient.
-0,0001 BTC to the minor address (transaction costs).
-0.4999 BTC returned to a new exchange address generated by your wallet.

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

On the other hand, it is important not to turn new funds to the original address which contained 1 BTC since it is now known to all.

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