28 Sep 2019 · 4 min read

Bitcoin Price Might Hit USD 1M Sooner Than a Quantum Computer Attacks

Researchers uncertain whether a powerful enough quantum computer will ever emerge. Quantum resistant cryptography might help protect cryptocurrencies.

IBM scientist Stefan Filipp, takes a closer look at the dilution refrigerator which will keep qubits at temperatures colder than the deepest parts of outer space. Source: IBM Research

Has Google killed crypto? In a research paper posted to NASA's servers earlier this month and then quickly removed, scientists at the tech company and at the University of California, Santa Barbara detailed how they'd achieved "quantum supremacy" using a quantum processor.

Dubbed Sycamore, this processor consisted in 54 superconducting quantum bits, known as "qubits." By becoming "entangled" with each other these qubits were able to solve a random-number problem in three minutes and 20 seconds, when it would have taken the world's most powerful supercomputer – Summit – 10,000 years.
And now that Google has shown it's possible to build a quantum computer that can do something no previous CPU could practicably do, the future doesn't seem to look so bright for crypto.

However, while a sufficiently powerful quantum computer would be capable of cracking the mathematics used by major cryptocurrencies, there's still no certainty from researchers that such a computer will ever emerge. And if it does, quantum-resistant cryptography may have already arrived to stop it from rendering bitcoin and other cryptocurrencies useless.

The power of quantum computing

Theoretically, at least, quantum computing destroys crypto.

"The security of essentially all current cryptocurrencies relies not on encryption but on digital signature schemes, which allow users to prove the authenticity of transactions transferring their coins to other users," explains David Bernardo, an associate professor at the IT University of Copenhagen (ITU), where he researches cryptography, blockchains, and information technology.

"It is well known that a powerful enough quantum computer would be able to break this basic security guarantee of digital signature schemes currently used by cryptocurrencies, allowing an attacker to forge transactions transferring a user's coins to arbitrary accounts/addresses," he adds.

In fact, the threat posed by quantum computing doesn't stop there, because Bernardo also tells Cryptonews.com that a powerful enough quantum computer could also crack the basic algorithmic underpinnings of the blockchains of various cryptocurrencies.

These include verifiable random functions and commitment schemes, which according to Bernardo are "used for maintaining the blockchain in some cryptocurrencies, allowing an attacker to write and/or redact blockchain information as he wishes."

Decades away, at best

So yes, Google's recent breakthrough would appear to be another step on the long road to making cryptocurrencies unworkable.

Luckily, it's still not certain if a quantum computer that's powerful and stable enough to crack cryptocurrencies in the ways outlined above will ever be built. And if they can eventually be built, it's likely that we'll still have to wait for a number of decades before they emerge.

"Even if one of the existing quantum computers can solve certain computational problems much faster than classical computers, they would need to be orders of magnitude more powerful in order to break this signature scheme," explains Bernardo.

"If one wants to break the signature scheme used in Bitcoin (and other cryptocurrencies), one would need a quantum computer that handles tens of millions of qubits and that is able to sustain computation for many hours."

Tens of millions of qubits is vastly in advance of anything that has been managed in present-day experiments and research, with Google finding it difficult enough to maintain 54 qubits (one of them actually didn't function).

That said, a 2018 study by researchers from Imperial College London calculated that 'only' 1,500 qubits would be needed to successfully run Shor's quantum algorithm, which is capable of breaking the elliptic curve digital signature algorithm (ECDSA) used by cryptocurrencies to sign transactions. But even reaching this smaller number is likely to require a Herculean effort.

"Notice that handling too few qubits is only one of the main issues in current quantum computers, the other being that current hardware is extremely error prone and only able to sustain quantum computation for tens of seconds," adds Bernardo, who also points out that building quantum computers powerful enough to crack cryptocurrencies "would certainly require breakthroughs in engineering and physics."

Consequently, Bernardo is reluctant to put a particular date on the appearance of sufficiently powerful quantum computers, although as a guesstimate he states that we probably "still have a few decades before such powerful quantum computers are built."

Post-quantum cryptocurrencies

A few decades is still a long way off, and in that time we may see the emergence of quantum-resistant cryptography and cryptocurrencies. But just as developing practical quantum computers will be difficult, so too will be developing their crypto counterparts.

"We already know how to construct post-quantum secure cryptographic schemes that in theory allow us to build post-quantum secure cryptocurrencies," says Bernardo.

"However, most (if not all) of the current post-quantum secure cryptographic schemes are much less efficient than their counterparts vulnerable to quantum attacks, requiring much more storage/memory and processing power, which affects their performance."

Added to this, Bernardo also notes that every vulnerable component of a blockchain will have to be made quantum-resistant, and not just the signature scheme. "In fact, in order to make sure a cryptocurrency is post-quantum secure we have to do a full security analysis to mathematically prove that the cryptocurrency is post-quantum secure as a whole, as opposed to just analysing specific components in isolation."

In other words, the race is on. Hopefully, efficient post-quantum cryptocurrencies will emerge before efficient quantum computers, and there's good reason to believe that they will, given that work on them is already more advanced than work on their still (mostly) hypothetical rivals.

P.S. Oh, John McAfee said that bitcoin price will reach USD 1 million on December 31, 2020.