Quantum Computers and Bitcoin: Neither The Camel, Nor the Sub-way Dog. Yet!

Quantum Computers and Bitcoin: Neither The Camel, Nor the Sub-way Dog. Yet!
Quantum Computers and Bitcoin: Neither The Camel, Nor the Sub-way Dog. Yet!


Still in the incipient stages, the force of these brawny machines may not be ready enough to crack the Bitcoin Maths. But when that happens, a Quantum Computer could turn out to be more of a friend than an antagonist for the crypto camps

Two ways to disappoint your granny – both sure-shot ones! First, interrupt her when she is telling a story. Second, ask rational questions after you have pleaded her to tell a tale about knights, fairies and dragons.

So you would know the way she rolled her eyes, whenever you sat up (instead of snoring away to happy lands) after she finished the ‘camel and the tent’ story. But weren’t those questions reasonable? A – Why did the camel-owner let the camel talk to him? Heck, why did he not make more money once he knew he had a talking camel? B- Would it not be morning-time by the time the camel slid its entire body inside the tent? After all, it’s a camel we are talking about!

Imagine the questions that follow when we talk of quantum camels then.

Beating humans at boards-games, sure, makes headlines. When computers do that, it sounds like something else too – like a huge creature tucking its nosy face inside the human tent. The stakes can get large enough to push the human out of the tent, when we think of areas like Bitcoin in particular. The innate mathematical difficulty is the core part of the blockchain technology here (assuring us of mining control and bitcoin-transactions’ security). That’s exactly why if a computer solves that hurdle, the entire pack of cards, stacked up so meticulously and long-sighted-ly, can tumble down in a second.

But are we asking the right questions again – would it be a tent cozy enough or near enough for this camel? Or is the camel more of a snail going after a tent-on-wheels?

Do not under-estimate the Camel, or the protein shakes it’s having

Quantum computer technology is such a breakthrough in human history, it harnesses the human technology and delivers huge leaps forward in processing information and data, explains Johnson Xu, Chief Analyst, TokenInsight. What was impossible or too time-heavy for classical computers is an easy sprint for these quantum computers. That’s what makes many people worry about their impact on the crypto-universe.

IBM has been at the fore-front of this new computing race so why not ask Vadim Lyubashevsky – Cryptographer, IBM Research Europe about the intersections we are contemplating. Is it right to expect quantum computers to crack the bitcoin Maths in a few years? Why would this feat be a good measure of QC’s power, if it happens?

Lyubashevsky explains it by boiling the answer down to ‘qubits’ and how it has been suggested that millions of physical qubits will be required to create a sufficient number (a few thousand) of logical qubits needed to attack today’s cryptography. “The actual number of physical qubits required will depend on the quantum error rates achieved and the optimization of algorithm design. Significant innovations in these fields may radically reduce the number of physical qubits required, but this is very difficult to predict.”

A further consideration is that different cryptographic schemes have different vulnerabilities. Elliptic curve cryptography that uses short keys, for example 256-bit ECDSA, will be at risk from quantum attacks earlier than older schemes using longer keys (3072 bit RSA), despite having roughly the same classical security, he reasons. “To your point, a June 2017 paper by Martin Roetteler and several co-authors estimates that such a quantum computer would need to command approximately 2,500 logical qubits of processing power to break the 256-bit encryption used by Bitcoin (Table 2)”

Paul Ginsparg, professor of physics and information science, Cornell University digs deeper in his own way as he confronts the question with his technical lens. “Although it is true that the ECDSA algorithm Bitcoin uses for public key/private key signatures is, in principle, susceptible to quantum speed-ups (just as is RSA encryption), I don’t believe that the 256 bit signatures currently used by bitcoin are at risk for the next decade.”

Based on the ‘quantum supremacy’ result of the fall, he adds, some have recently claimed that the time-frame may be much shorter, as little as a few years, but this claim is uninformed. (Unless one happens to believe that some government has a secret quantum computing facility that’s a decade ahead of anything commercially available, but that is implausible for many reasons Ginsparg quips.)

Darning The Holes

Apparently, in 1994, the mathematician Peter Shor published a quantum algorithm that can break the security assumption of asymmetric cryptography. This meant that anyone with a sufficiently large quantum computer could use this algorithm to derive a private key from its corresponding public key, and thus, falsify any digital signature, according to a Deloitte Paper by Itan Barmes and Bram Bosch. They warned that all coins in p2pk addresses and reused p2pkh addresses are vulnerable to a quantum attack. They also pointed out that p2pk addresses dominated the Bitcoin blockchain in the first year of its existence. Interestingly, the number of coins in p2pk addresses has stayed practically constant (circa 2M Bitcoins). But as p2pkh was introduced 2010, it quickly became dominant and most of the coins created since then are stored in this type of address.

The Tent – made of Goat-skin?

Ginsparg tells us why the ‘quantum supremacy’ demonstration is not directly relevant. “Its calculation was both sufficiently straightforward and tailored to the 53 qubit architecture that the qubits did not need error correction. Decrypting the blockchain signatures would instead require at least many thousands of qubits, and possibly many hundreds of those sands, depending on how much the fidelity of the qubits continues to improve over time. And as yet there hasn’t been a single calculation done even with a handful of error-corrected qubits, and it’s not clear if even that will happen within two years (though that’s now high priority on the near-term agenda). Getting from there to the scale necessary to attack the currently used blockchain encryption with sufficient reliability will certainly take a few more years beyond that.”

How soon can the brute force solve the unbreakable maze? We certainly don’t expect this to happen in the next few years – a much more likely timeframe is sometime within the next 10-30 years, Lyubashevsky surmises. “Nevertheless, there is always a chance that someone could wake up tomorrow and think of something which hasn’t been considered before and speed up the process. In order to prepare, IBM Research has been developing cryptographic algorithms that are resistant to the security concerns posed by quantum computers. Some of these algorithms are based on Lattice Cryptography, which is in turn related to mathematical problems that have been studied since the 1980’s and have not succumbed to any algorithmic attacks, either classical or quantum. Our algorithms make up the “Cryptographic Suite for Algebraic Lattices” that we call “CRYSTALS” which are open source and are currently being considered as a possible standard by the National Institute of Standards and Technology (NIST) Post Quantum Cryptography standardisation process.”

The number of Bitcoins stored in reused p2pkh increases from 2010 to 2014, and since then is decreasing slowly to reach the current amount of 2.5M Bitcoins. There were still over 4 million BTC (about 25% of all Bitcoins) which are potentially vulnerable to a quantum attack – Deloitte Experts.

Present-day reckonings show that a quantum computer will take about 8 hours to derive a typical Bitcoin private key, so as long as people do not reuse addresses, we are good and resistant- but the stakes many change if quantum computer will ever get closer to the 10 minutes mark to derive a private key from its public key – because then the Bitcoin blockchain will be inherently broken – Barmes and Bosch argued in their article.

“It is also quite likely to happen eventually, and yes when it does happen will be a dramatic measure of QC’s power, even more dramatic from a practical standpoint than the quantum supremacy demonstration last fall.” Ginsparg observes.

But even then there will be plenty of warning so it won’t be particularly problematic for current blockchain applications, he underlines. “The reason is that the quantum attack is only really effective for unprocessed transactions, i.e., after a transaction is broadcast to
the network but before it’s placed on the blockchain. So the decryption would have to take on the order of 10 minutes or less. (That makes it a more difficult task than decrypting RSA-encoding text messages in other security contexts, where a message might remain sensitive years after being broadcast.) There will be more than ample warning for when quantum computers get close to that threshold, and it will be relatively straightforward for blockchain applications to swap in an alternate encryption standard that is resistant to the quantum attack well in advance.”

The possibility of building quantum-resistance is as high as building a Quantum-Bitcoin-puzzle-decoder. Xu, too, shakes off any need to be harried about this power. “Practically people should not worry about quantum computers crack the Bitcoin Maths in a couple of years. Instead, people should worry about the encryption standard that we, as individuals, rely on every day from the bank account to social network password since Quantum Computers can be widely adopted.” He stresses that even if these computers are able to unravel the Bitcoin Maths, there are are other concerns that people should worry about first. “Bitcoin can fork (upgrade) its consensus algorithm, change encryption standard by voting through node and mining hash-rate within the industry. Thus, Quantum Computers are not a threat to Bitcoin or crypto-currency industry,” he contends.

Even if we assume that these computers can crack the Bitcoin Maths, with a joint effort, we can see a ‘rebirth’ of the Bitcoin network by changing its algorithm, encryption etc. to achieve Quantum-resistance leveraging a network hard-fork, Xu suggests.

Future capital and investments are getting oriented to the new needs and resistance capabilities that networks may need ahead. Pranav Sharma, Co-founder & Managing Partner – Woodstock Fund asserts that we are years away from any quantum computing hack blockchain. There is already research undergoing to build quantum-resistant networks. Our current focus is Decentralised Ledger technology (DLT) and its applications. Quantum computing has interesting applications in predictive modelling and healthcare. As a fund we are open to the areas of intersection of DLT and Quantum computing.”

So – Why imagine a Wolf out there?

As to some other implications that the industry should be wary of, Xu outlines the positive spins we may not be counting yet. “The research in this area can help the industry to harness the technology innovation to achieve significant breakthroughs in encryption standard; and push the boundary of technology development in the industry. We can fast-track blockchain innovation considerably.”

Xu is confident and positive in calling a Quantum Computer not a threat but a friend in the industry. “With the advancement we are witnessing in Quantum Computing, it will surely break things such as existing encryption standard major algorithms etc. The advantages that this technology bring to the industry outweigh its disadvantages.”

Although people have claimed quantum supremacy in 2019, the technology is still a long way to go before humans can gain meaningful benefits leveraging Quantum Computing, Xu augurs.

Last evening, a grandson heard something odd and told it to a sleepy-grandma. The amazing feat of how some stray dogs in Moscow have cracked the Subway system to board and alight at the exact stations they want to travel – without intruding upon or harming humans in any way. And before she can sit up and ask questions of the logical variety, the child is quick to add the Disclaimer ‘Not a story Granny. It is happening.”