The first quantum computer to crack encryption is now shockingly close

A quantum computer capable of breaking the encryption that secures the Internet appears to be just around the corner. A stunning revelation by two research teams outlines how this might happen, with one suggesting that the current largest quantum machine is already more than half the size needed.

These two studies concern an encryption technique based on the Elliptic Curve Discrete Logarithm Problem (ECDLP). The details of how this mathematical problem is solved have made it a good candidate for data encryption and led to its widespread adoption for securing large amounts of Internet communication, including banking transactions, and almost every major cryptocurrency, including Bitcoin.

Elliptic curve encryption is extremely difficult for conventional computers to crack, but scientists have known since the 1990s that quantum computers won’t have the same difficulty. However, building a quantum computer large enough was technically impossible, so it seemed like a distant concern.

In recent years, both theory and engineering have advanced at an astonishing rate, greatly compressing the timeline. On the theoretical front, researchers have optimized quantum hacking algorithms to reduce the actual amount of quantum computing power needed. For example, in 2019 the best estimate of the size needed to break a related encryption method called RSA-2048 was 20 million qubits—a qubit is the quantum equivalent of a traditional computer bit. This February, that number reached just 100,000 qubits.

What’s more, in 2019, state-of-the-art quantum computers barely surpassed 50 qubits. Today’s largest quantum computers have more than 1,000 qubits, and the largest qubit array—which hasn’t actually been used for computation yet—has 6,100.

Now, Dolev Bluvstein at Oratomic and his team believe that ECDLP could fail on a machine with just 10,000 qubits. While this decryption process would take several years of running a quantum computer, Ryan Babbush of Google’s Quantum Research Unit and his colleagues independently mapped how 500,000 qubits could do the same thing in just 9 minutes.

“Today is an important day for quantum computing and cryptography,” Justin Drake at the Ethereum Foundation, which collaborated with Google researchers, wrote on.

Bluvstein and his colleagues based their calculations on qubits made from extremely cold atoms driven by lasers. Such qubits can be connected to each other in many ways, and this high connectivity partly accounts for the reduced requirement per qubit.

Creating an array of 10,000 ultracold qubits may be possible within a year, Bluvstein says, but the real challenge will be controlling them well enough and making them work fast enough. There are no shortcuts like hooking up multiple existing machines, as the qubits must be able to interact properly with each other.

Bluvstein thinks a sufficiently capable machine won’t be ready until the end of the decade. “There’s a lot of progress to be made, but it’s starting to become something that people can really imagine,” he says.

Concerns about cryptocurrencies

The Google team reached its conclusions based on another type of quantum computer made of superconducting circuits, which are generally considered to be more advanced technology and which Google supports the most.

The researchers declined to comment publicly on the work, but write in their paper that “resource estimates could be substantially reduced by making more aggressive assumptions about hardware capabilities,” suggesting that the 500,000 qubit estimate is conservative. Notably, the researchers chose to omit all details of their decryption algorithm, citing security concerns.

They also write that such a quantum computer could be used to intercept a cryptocurrency transaction and divert the funds — essentially stealing them — in the short period of time before it is recorded.

Given these two studies, Bitcoin definitely appears to be vulnerable to a quantum attack earlier than previously known, he says Scott Aaronson at the University of Texas at Austin.

Stefano Gogioso at the University of Oxford, says that both types of quantum computers face significant technical challenges before any of the results can be implemented in practice, particularly the ultracold-atom approach, which is a much more unproven technology. But there is reason to worry about the security of our digital world, he says.

Some internet browsers already offer encryption resistant to quantum attacks, so-called post-quantum encryption (PQC), and conventional banks may be able to fend off quantum hackers after they’ve been attacked, but highly decentralized cryptocurrency systems will be much more vulnerable, Gogioso says. Google recently called for a migration to PQC by 2029, which Gogioso says seems increasingly necessary.

“That’s exactly why we started the PQC standardization project more than ten years ago,” he says Dustin Moody at the National Institute of Standards and Technology (NIST) in Maryland. “We’ve always known that as quantum hardware improves, so do the algorithms.”

NIST has selected several PQC algorithms that could become the security standard in a future full of practical quantum computers, and the US federal government plans to transition to using them by 2035. But Moody says organizations should start the transition as soon as possible. “These documents reinforce the idea that the window for migration is finite and the time to act is now,” he says.

topics:

• security/
• quantum computing