30th December 2024 > > NFK 3 of 9, & the risk of quantum computers.

tl;dr

The third of the nine NFKs. The quantum computing threat to cryptos.

Market Snap

Market Wrap

The techies are back out in force predicting a slide to sub $80k for BTC, which would mean a 35% drawdown from the current ATH. Anything is possible but for long-term investors who only buy on the spot market, it matters not the exact path taken, but only the end destination, and that is wholesale adoption of BTC by the TradFi industry and investors worldwide.

Occasional Series – Project K: Flat Cat. NFK 3 of 9

https://www.curiouscryptos.com/projectk

Curious Cryptos’ Commentary – Quantum computers

The potential risk posed by quantum computers to current cryptography technology has been known about since cryptos were invented. It was first addressed by the CCC nearly three years ago on 1st April 2022.

But just because this is old news does not mean it has no relevance. In these quiet in between days before the next year begins in earnest, this is probably as good a time as any to revisit this topic. A bit of background information might be useful if your cryptography knowledge is sketchy at best.

…

The original objective of cryptography was to keep messages safe even if they were intercepted between the sender and the receiver. Until the 1970s, this was achieved by encrypting a message with a single key to produce what looks like gobbledegook to anyone who does not know the key. If only the sender and the receiver are in possession of the key, then a degree of security in keeping the message contents private has been achieved.

Famously, even with the most basic computers that were available at the time, Alan Turing and his team cracked the German’s Enigma code by targeting a sheer brute force attack on the encrypted messages to reverse engineer the key, which was changed daily. With the computing power available today, single key cryptography is of little use.

In the 1970s a new branch of cryptography was invented that uses the concept of a dual key – one public and one private. The public key is derived (mathematically) from the private key, but the private key cannot be reverse engineered from the public key. They are described as being cryptographically linked. The first few iterations of dual key cryptography have been superseded by the latest technology known as elliptic curve cryptography (ECC). This is the basis of all secure communications the world over, as well as Bitcoin, though the Bitcoin protocol employs ECC in a fundamentally different way.

Users of WattsApp (that’s probably all of you) are using ECC every time you communicate on that platform. You encrypt your message with the receiver’s public key to produce an unintelligible mish mash of letters and numbers. The only means of unencrypting the message is to use the private key from which the public key was generated – and that is owned by the receiver. Assuming that the key remains securely stored within the receiver’s device (there is debate over whether that is the case or not) it is only the person or persons who have access to that device who can read the message.

This is the same process used for all secure communications as recommended by the US NSA (National Security Agency). Cracking this cryptography by using overwhelming computer force would not only allow a malicious actor access to all your WattsApp messages, but also all the email communications of every single member of the US government and others. It would make hacking into any IT system you could name a task as trivial as you could wish for. That is a big prize.

In the crypto world, the encryption process is turned upside down. Messages (“Move 1 BTC to public wallet address X”) are encrypted by the sender’s private key, and are publicly unencrypted using the sender’s public key i.e. the sender’s wallet address. This is an important, if subtle, difference to encrypting communications that are meant to remain secure. It is a genius idea, and a genius application of that idea.

…

Theoretically, it is possible to brute force attack ECC. A malicious actor could target a public address holding a large amount of BTC by running through every possible private key to see if it generates that public key. If a match is found, that wallet can be emptied, that WattsApp message can be read, that diplomatic missive that included indisputable proof that Covid originated in Wuhan but in the lab and not the wet market would roil those useful idiot scientists who claimed otherwise, and the codes for Russia’s nuclear missiles could be made public.

In practice, the probability of this approach being successful with modern computers is so vanishingly small, it Is as close to zero as it is possible to get. I think I once read somewhere that the potential number of private keys is more than the number of the atoms in the universe. Whatever, it is a very large number, and brute force cannot break it. Or at least not yet, which is where the risk of quantum computing comes into the frame.

…

The computers that you and I use are based on traditional bits, that are in a state of 1 or 0. Quantum computers use qubits that exist in a state known as superposition. They exist in any shade between 0 and 1, and their actual value is only known at the point that the solution is revealed, a concept that was used to create flash loan attacks that we covered in January and March 2021 (back issues available on request if you so wish). For reasons that escape us mere mortals, this allows for incredibly complex calculations to be finalised in the merest fraction of the time that even the world’s most powerful supercomputer (currently being built by Elon Musk of course) would take forever to do. And by forever, I really do mean that, or as close to it as is possible to conceive. There is also a body of theory that claims that now that quantum computers are a real thing, that is proof of the multiverse theory, but that is probably a little off-piste for us today.

The latest quantum computer created by Google had 100 qubits, a significant improvement over the previous record of 8 qubits. Importantly, it also broke new ground in the field of error correction which at one time was thought to be a limiting factor in the potential size of quantum computers.

Google claims it solved a problem that would take a supercomputer 10 septillion years, which is pretty close to “forever”, but not everyone is convinced of the fidelity of this claim. There are those who have suggested that two and half days would be enough time to solve the same problem.

…

So, the question is, can a quantum computer use a brute force attack to crack ECC? In theory, yes it can. In practice, not just yet. And that has always been the case – this has always been a known risk.

It has been estimated that a quantum computer would need 13 million qubits running for one year to crack ECC. That is not only a dramatic increase over the current 109 qubits, but requires a level of stability that seems technologically infeasible for now – no quantum computer has been known to last longer than milliseconds before it collapses and loses all functionality.

In short, the best estimate, and this could be revised downwards, is that decades of work are required before quantum computers are a threat to ECC.

Meanwhile, there is a lot of work being done to move on from ECC to quantum-computer resistant cryptography, for all applications that use ECC, not just cryptocurrencies. Back in April 2022, the CCC brought this to our attention:

“’Quantum key distribution (QKD) blockchain network is the only solution that has been mathematically proven to defend against a potential quantum computing-based attack.’

JPM in collaboration with Toshiba and Ciena has deployed and tested a real-world QKD blockchain.”

Crypto OG Vitalik is himself heading up a project known as The Splurge whose objective is to make the Ethereum blockchain quantum computer resistant. This is work that is at the very edges of some very smart mathematics, and we cannot judge just how successful the efforts will be. I think we can safely assume much progress has been made since April 2022. Given what’s potentially at stake – which is of more concern to me than the desirability of the immutability of the blockchain – we must all hope the boffins are successful, for otherwise our world will be made desolate.