The industry may have 10 years or less to devise defenses against quantum computers capable of breaching its elliptic curve cryptography.
By many accounts, quantum computing (QC), which uses atomic “spin” instead of an electrical charge to represent its binary 1’s and 0’s, is evolving at an exponential rate. If QC is ever realized at scale, it could be a boon for human society, helping to improve crop yields, design better medicines and engineer safer airplanes, among other benefits.
The crypto sector could profit too. Just last week, for instance, a Bank of Canada-commissioned project simulated cryptocurrency adoption among Canadian financial organizations using quantum computing.
“We wanted to test the power of quantum computing on a research case that is hard to solve using classical computing techniques,” said Maryam Haghighi, director of data science at the Bank of Canada, in a press release.
But, others worry that quantum computing, given its extraordinary “brute force” power, could also crack blockchain’s cryptographic structure, which has served Bitcoin (BTC) so well since its inception. Indeed, some say it is only a matter of time before quantum computers will be able to identify the enormous prime numbers that are key constituents of a BTC private key — assuming no countermeasures are developed.
Along these lines, a recently published paper calculated just how much quantum power would be needed to duplicate a BTC private key, i.e., “the number of physical qubits required to break the 256-bit elliptic curve encryption of keys in the Bitcoin network,” as explained by the paper’s authors, who are associated with the University of Sussex.
To be sure, this will be no easy task. Bitcoin’s algorithm that converts public keys to private keys is “one way,” which means that it is easy to generate a public key from a private key but virtually impossible to derive a private key from a public key using present-day computers.
In addition, this would all have to be done in about 10 minutes, the average amount of time that a public key is exposed or vulnerable on the Bitcoin network. It also assumes that the public key is identical to the BTC address, as were most in Bitcoin’s early days before it became common practice to use the KECCAK algorithm to “hash” public keys to generate BTC addresses. It’s estimated that about one-quarter of existing Bitcoin is using unhashed public keys.
Given these constraints, the authors estimate that 1.9 billion qubits would be needed to penetrate a single Bitcoin private key within 10 minutes. Qubits, or quantum bits, are the analog to “bits” in classical computing. By comparison, most proto-QC computers today can summon up 50–100 qubits, though IBM’s state-of-the-art Eagle quantum processor can manage 127 qubits.IBM Q System One, the first circuit-based commercial quantum computer. Source: IBM Research
Put another way, that’s 127 qubits against the 1.9 billion needed to crack Bitcoin’s security using a large-scale trapped ion quantum computer, as proposed in the AVS Quantum Science paper.
Mark Webber, quantum architect at Universal Quantum, a University of Sussex spin-out firm, and the paper’s lead author, said, “Our estimated requirement [...] suggests Bitcoin should be considered safe from a quantum attack for now, but quantum computing technologies are scaling quickly with regular breakthroughs affecting such estimates and making them a very possible scenario within the next 10 years.”
Could Bitcoin’s security really be cracked? “I think that quantum computers could break cryptocurrency,” Takaya Miyano, a professor of mechanical engineering at Japan’s Ritsumeikan University, told Cointelegraph, “Though, not in a few years time, but in 10–20 years time.”
Miyano recently lead a team that developed a chaos-based stream cipher designed to withstand attacks from large-scale quantum computers.
David Chaum, writing last year for Cointelegraph, also sounded the alarm — not only for crypto but for wider society as well:
“Perhaps most terrifying for a society so reliant on the internet, quantum-level computing puts all of our digital infrastructures at risk. Our contemporary internet is built on cryptography — the use of codes and keys to secure private communication and storage of data.”
Meanwhile, for cryptocurrencies like Bitcoin and Ether (ETH), “for whom this concept is fundamental, one sufficiently powerful quantum computer could mean the theft of billions of dollars of value or the destruction of an entire blockchain altogether,” continued Chaum.
There are more than 4 million BTC “that are potentially vulnerable to a quantum attack,” consulting firm Deloitte estimates, a number that comprises owners using un-hashed public keys or who are reusing BTC addresses, another unwise practice. At current market prices, that amounts to about $171 billion at risk.
“Personally, I think that we are unable at the moment to make a good estimation” of the time it will take before quantum computers can break BTC’s encryption, Itan Barmes, quantum security lead at Deloitte Netherlands and project fellow at the World Economic Forum, told Cointelegraph. But, many experts today estimate 10-15 years, he said. Many of these estimates, too, are for breaking the encryption without time constraints. Doing it all within 10 minutes will be more difficult.
Other cryptocurrencies, not just Bitcoin, could be vulnerable too, including those with proof-of-stake (PoS) validation mechanisms; Bitcoin uses a proof-of-work (PoW) protocol. “If blockchain protocol exposes public keys for a sufficiently long time, it automatically becomes vulnerable under quantum attacks,” Marek Narozniak, a physicist and member of Tim Byrnes’ quantum research group at New York University, told Cointelegraph. “It could allow an attacker to forge transactions or impersonate block producers’ identity for PoS systems.”
It seems the crypto industry might have about a decade to get ready for a potential QC onslaught, and this is crucial. Narozniak noted:
“There is more than enough time to develop quantum-safe cryptography standards and work out adequate forks to currently used blockchain protocols.”
When asked if he was confident that post-quantum cryptography will be developed in time to thwart hackers before the 10-minute barrier is broken, Deloitte’s Barmes referenced a more recent paper he co-authored on quantum risks to the Ethereum blockchain that describes two types of attacks: a storage attack and a transit attack. The first “is less complicated to execute, but to defend against it, you don’t necessarily need to replace the cryptography algorithm.” On the other hand, he told Cointelegraph:
“The transit attack is much more difficult to execute and is also much more difficult to protect against. There are some candidate algorithms that are believed to be resistant to quantum attacks. However, they all have performance drawbacks that can be detrimental to the applicability and scalability to the blockchain.”
What is unfolding in this area, then, appears to be a sort of arms race — as computers grow more powerful, defensive algorithms will have to be developed to meet the threat.
“This overall pattern is really nothing new to us,” said Narozniak. “We see it in other industries as well.” Innovations are introduced, and others try to steal them, so piracy protection mechanisms are developed, which provoke even more clever theft devices.
“What makes this quantum-safe cryptography case a little bit different is that the quantum algorithms impose a more drastic change. After all, those devices are based on different physics and for certain problems they offer different computational complexity,” added Narozniak.
Indeed, QC makes use of an uncanny quality of quantum mechanics whereby an electron or atomic particle can be in two states at the same time. In classical computing, an electric charge represents information as either an 0 or a 1 and that is fixed, but in quantum computing, an atomic particle can be both a 0 and a 1, or a 1 and a 1, or a 0 and a 0, etc. If this unique quality can be harnessed, computing power explodes manyfold, and QC’s development, paired with Shor’s algorithm — first described in 1994 as a theoretical possibility, but soon to be a wide-reaching reality, many believe — also threatens to burst apart RSA encryption, which is used in much of the internet including websites and email.
“Yes, it’s a very tough and exciting weapons race,” Miyano told Cointelegraph. “Attacks — including side-channel attacks — to cryptosystems are becoming more and more powerful, owing to the progress in computers and mathematical algorithms running on the machines. Any cryptosystem could be broken suddenly because of the emergence of an incredibly powerful algorithm.”
One shouldn’t necessarily assume that quantum computing’s impact on the crypto sector will be entirely deleterious, however. Samuel Mugel, chief technology officer at Multiverse Computing, the firm that led the above-referenced program at Bank of Canada, explained that in the pilot, they were able to simulate a network of financial relationships in which the decisions that one firm might make were highly dependent on decisions of other firms, further explaining to Cointelegraph:
“Game theory networks like this are very hard for normal supercomputers to solve because more optimal behaviors can get overlooked. Quantum computers have ways of dealing with this type of problem more efficiently.”
Devices based on quantum mechanics potentially offer other unique possibilities, added Narozniak, “For instance, unlike classical states, quantum states cannot be copied. If digital tokens were represented using the quantum states, the no-cloning theorem would automatically protect them from being double-spent.”
Quantum entanglement could also be used to secure quantum smart contracts, Narozniak said. “Tokens could be entangled during the execution of the contract making both parties vulnerable to eventual loss if the smart contract is not executed as agreed.”
All in all, the threat to the cryptoverse from quantum computing appears real, but enormous power would be required to breach crypto’s underlying cryptography, and hackers would also have to work under stringent time constraints — having only 10 minutes to penetrate a BTC private key, for instance. The reality of breaking Bitcoin’s elliptic curve encryption through the use of quantum computing is at least a decade away, too. But, the industry needs to get started now in developing deterrents. “I would say that we should be ready on time, but we need to start working seriously on it,” said Barmes.
In fact, a substantial amount of research is now taking place “in post-quantum crypto,” Dawn Song, a professor in the computer science division at the University of California, Berkeley, told Cointelegraph, adding:
“It is important that we develop quantum-resistant, or post-quantum, cryptography so we have the alternatives ready when quantum computers are powerful enough in reality.”