Quantum Computer 'Threat' To Crypto Is Exaggerated... For Now

Authored by Andrew Singer via CoinTelegraph.com,

A report that Chinese researchers have employed a D-Wave quantum computer to breach encryption algorithms used to secure bank accounts, top-secret military data and crypto wallets is at first glance a matter for deep concern. 

“This is the first time that a real quantum computer has posed a real and substantial threat to multiple full-scale SPN [Substitution-Permutation Network] structured algorithms in use today,” wrote Shanghai University scientists in a peer-reviewed paper, according to the South China Morning Post (SCMP) on Oct. 11.

The paper talks about breaking RSA (Rivest-Shamir-Adleman) encryption, one of the oldest and widely used public-key cryptosystems.  

Details about the latest research have been slow to emerge so it’s difficult to say for sure how dire the threat is to cryptocurrencies and blockchain technology. The paper had yet to be released in English as of Oct. 11, and researchers weren’t taking any interviews, supposedly “due to the sensitivity of the topic,” according to SCMP.

But if the researchers’ results hold up, and can be duplicated by others, “it is a step forward” in the evolution of quantum computing, Marek Narozniak, a physicist with a background in quantum computing, and founder at sqrtxx.com, told Cointelegraph.

Would it mean that the password-protection mechanisms used in many industries, including banking and cryptocurrencies, might soon be vulnerable, as many fear, however?

“From the paper many details are missing, so it is difficult to provide a definite answer” with regard to its possible significance, Massimiliano Sala, Full professor and head of the Laboratory of Cryptography at the University of Trento, told Cointelegraph.

Much depends on whether the scientists were able to break RSA keys of a certain size — i.e., keys as large as those used by banks to secure customer’s savings and checking accounts today. “There is no evidence of that,” said Sala.

But if they had, it would be “huge,” he said.

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, many believe. But full purpose QC devices have yet to emerge at scale.

The D-Wave machines used in Shanghai, sometimes called quantum annealers, are really proto-quantum computers, or forerunners, capable of conducting specialized tasks only. 

D-Wave 2X 1000 Qubit quantum annealing processor chip mounted and wire-bonded in its sample holder. Source: Mwjohnson0

However, if and when universal quantum computers do emerge, they could threaten the elliptic curve cryptographic structure which has served Bitcoin and other cryptos very well until now, some worry.

It could be 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.  

“However, we must keep in mind that D-Wave quantum computers are not general-purpose quantum computers,” added Sala. Moreover, D-Wave’s “ability to factor RSA keys was already established by one of my colleagues a few months ago,” he said.

Takaya Miyano, professor of mechanical engineering at Japan’s Ritsumeikan University, also questioned the significance of the scientists’ results — and along similar lines as Sala. 

The length of the integer that the Shanghai researchers factorized, 22 bits, “is much shorter than that of actual RSA integers, which is usually equal to or greater than 1024 bits, e.g, 1024, 2048, and maximally 4096 bits,” he told Cointelegraph.

Moreover, “the D-wave machine is a kind of quantum simulator for solving optimization problems, not a universal computer,” Miyano added. It isn’t clear that it would be able to conduct rapid factorization of large RSA integers in the real world.

Why prime factorization is important

Factorization is a mathematical process where a number can be written as the product of smaller whole numbers. For instance, 12 can be factorized, or written, as 3 x 2 x 2. Efficient prime number factorization has been called “the holy grail” of breaking a RSA public-key cryptosystem.

RSA is more than encryption, after all. It is also a ‘key’ generation scheme that typically involves multiplying large prime numbers. Two parties — a bank and its customer, for example — typically receive a set of prime numbers that are used to compute their private and public keys, Narozniak explained.

The process of actually generating private and public keys is complex, but if ‘p’ and ‘q’ are prime numbers, and ‘n’ is the product of those two prime numbers (i.e., n = p x q), then one can say that p and q are related to the private keys and n is related to the public key. 

The basic mathematical principle behind RSA encryption is that while it is easy to multiply two prime numbers, it is very difficult to do the reverse, i.e., find the two prime numbers that are factors of a product — and this becomes harder as the numbers get larger. 

Sala’s University of Trento colleagues earlier this year used a quantum annealer to uncover the two prime factors of the number 8,219,999 (i.e., 32,749 and 251) “which, to the best of our knowledge is the largest number which was ever factorized by means of a quantum device,” wrote the researchers.

In Sala’s view the recent Shanghai University paper is significant “only if they have found a way to factorize huge numbers.” 

The University of Trento researchers also cited the great potential of quantum computing to solve complex problems that have long remained “intractable” for classical computers. 

Prime factorization — i.e., the problem of breaking down a number into its prime factors — in particular, “is a good candidate to be effectively solved by quantum computing, in particular by quantum annealing.” 

Crypto keys are safe — For now

Let’s assume, however, that the Shanghai scientists really did find a way to use a quantum annealer to successfully breach cryptographic algorithms, including those like SPN which are foundational for the advanced encryption standard (AES) widely used in the military and finance. What would that do to the crypto industry?

“Symmetric ciphers such as AES-128 used for data encryption are not vulnerable to this kind of attack as they do not rely on number factorization,” said Narozniak.

There might be exceptions, of course, like if the cipher is a shared secret derived via RSA-based key exchange protocol, he continued. But “properly encrypted passwords and other data in general will remain encrypted even if the approach presented in that research scales up and becomes widely available — and if true,” he said. 

A history of unproven RSA claims

Narozniak cautioned against rushing to conclusions. “Before we re-evaluate our level of optimism, let us wait for someone to repeat and confirm this result,” he said. “Claims of breaking RSA are not so uncommon.” 

In early 2023, for instance, Chinese researchers said they had factorized a 48-bit key on a 10-qubit quantum computer, a claim “which still has not been peer reviewed,” commented Narozniak. 

“And two years before that Claus Schnorr, who is an authority in the community, made an honest mistake and claimed RSA to be broken. I personally take such big claims with a grain of salt.”

According to Sala: “Breaking RSA would mean that a lot of software should be updated, but not drastically changed,” because there are already-implemented standards that provide alternatives including elliptic curve cryptography (ECC), used to secure Bitcoin. He added:  

“More drastic would be the impact on credit cards and the like, which would have to be withdrawn massively, to radically change their software.” 

One might wonder why cryptocurrencies are not using RSA widely — as banks do. The crypto industry favors elliptic-curve cryptography because ECC makes it possible to achieve the same level of security with much smaller keys using fewer bytes, said Narozniak. This opens up digital space which enables chains to grow faster. 

Is Buterin’s ‘hard fork’ solution viable?

Elsewhere, Ethereum co-founder Vitalik Buterin suggested in March that a “hard fork” could subvert a quantum attack on Ethereum were it to arise. “We are already well-positioned to make a pretty simple recovery fork to deal with such a situation,” he posted on Oct. 17. Users might have to download new wallet software, but few would lose funds.

Is it really so easy, though? “I disagree that such a hard fork would be ‘simple,’” said Narozniak. And looking ahead, quantum-safe signatures, such ML-DSA, would need to have significantly larger keys and signatures compared with those used today. This could slow on-chain performance and raise gas fees, he suggested.

Executing a hard fork would “be complex, require broad community consensus, and may not restore all lost assets or fully repair trust in the network,” Samuel Mugel, chief technology officer at Multiverse Computing, told Cointelegraph. “Therefore, it’s crucial to implement quantum-resistant cryptography before such an attack happens to avoid this situation.”

Safeguards are needed

“We most certainly need to revisit our current cybersecurity defenses,” Christos Makridis, associate research professor at Arizona State University and CEO/Founder of Dainamic, told Cointelegraph. 

More attention needs to be paid to network capacity loads (i.e., defending against distributed denial of service attacks) and to passwords (e.g., to protect data from hackers) in a world with quantum computing. He further observed:

“One of the emerging views is that the expansion of quantum computing and generative AI has enabled offensive cyber more than defensive.”

The industry can’t become complacent. “Dangerous quantum computers will come, it’s just a matter of time,” Sala warned. 

“The blockchain world must get ready as soon as possible, by planning a roadmap towards a transition to post-quantum cryptography,” he added, developing safeguards able to resist attack even by a “fully-fledged quantum adversary.”