Quantum computers are back in the headlines as the next threat to internet security. A new pair of theoretical works, one from Google and one from the start-up Oratomic have sparked claims that encryption could soon be broken far more easily than experts previously predicted. Oratomic’s eye-catching number sounds particularly dramatic: just 10,000 physical qubits to crack modern encryption, compared to earlier estimates in the millions. But before declaring the end of online security, it is worth looking past the headline. To understand the details, it helps to distinguish between different encryption schemes and different kinds of quantum hardware.

by Christian Andersen and Eliška Greplova

Historically, a majority of the discussion of quantum attacks was focused on RSA (Rivest–Shamir–Adleman) cryptosystem, which relies on the difficulty of factoring large numbers into primes. Today, RSA is widely used in server certificates and digital signatures. More recently, the attention has shifted to ECC (elliptic curve cryptography), which is currently more common on the internet and is also used in cryptocurrencies such as Bitcoin. To break ECC, it is needed to solve an algebraic problem, the so-called Elliptic Curve Discrete Logarithm Problem (ECDLP). The advantage of the ECC is that it provides the same level of security with much smaller keys. For example, 256-bit ECC is considered safer than the standard 2048-bit RSA keys. However, this is not true for a quantum computer! That same 256-bit ECC is easier for quantum computer to break than 2048-bit RSA. Roughly speaking, when comparing ECDLP and RSA specifically, the cryptosystems with longer private key are harder for a quantum computer to break, although caution should be taken when generalizing this to other cryptosystems.

Another important point to think about when we talk about cryptographic robustness are hardware properties of the quantum computer we would use to solve the cryptographic problem. Specifically, the distinction between chip-based and atom-based quantum computers is key for this discussion. Chip-based quantum computers use either semiconductor or superconducting circuits to define qubits on a chip, similar to how traditional (classical) computer chips are made. The typical clock speed (time for one operation) for these systems is one cycle per 1 microsecond (one millionth of a second). Because the qubits are defined on a chip, often each qubit is naturally connected only to its neighbors.

Atom-based quantum computers are based on single atoms or ions trapped with laser systems. Because each qubit is a perfect atom, the qubits are guaranteed to be perfectly identical to each other which makes them easy to operate. In contrast to chip-based systems, it is comparatively easy to move the qubits around and therefore all qubits can be connected to all other qubits. However, these qubits are slower compared to their chip-based counterparts. Their typical clock cycle is 1 millisecond (one thousands of a second) – around 1000 times slower than chip-based computers.

Announced in the recent Oratomic preprint was a new encoding scheme that allows to leverage the connectivity of atomic qubits to obtain the required precision to break ECC-256 with just around ten thousand qubits. This estimate may sound scary at first, but once they factor in the typical clock-speed, Oratomic finds that with 10000 qubits, it would take almost 3 years to break a single ECC-256 key. Breaking the much harder RSA-2048 key would then take 100 years. There is, however, a trade-off: with more qubits we can break these cryptographic keys much faster: with 26000 qubits, it would be possible to break ECC-256 in approximately 10 days!

In parallel, Google did a similar estimate for the future chip-based quantum computers and found that around half a million qubits could break ECC-256 in around 10 minutes. The time-scale of 10 minutes is important (even though many more qubits would be needed than for the atom-based system). As explained by Google, 10 minutes would be sufficiently small time to cause real disruption to the bitcoin infrastructure.

It is important to note that both estimates depend on proposed machines that do not actually exist yet, and both approaches face enormous engineering challenges. For chip-based approaches, the challenge is to scale from a few hundred qubits to the required number of qubits. For atomic systems, the challenge is less about the number of qubits but instead to reach the required speed, stability and control. Still, future technical breakthroughs may indeed further lower the required number of even further. That is already an active area of research in both superconducting qubits and semiconductor spin qubits: while not as flexible as atomic systems, they bring the number of qubits down significantly without sacrificing speed. For example, researchers at QuTech recently demonstrated that shuttling (moving around) semiconductor qubits can give flexibility like atomic qubits without compromising fidelity. On top of that, any improvement in qubit quality would further reduce the number of qubits needed across the board. That is why the real race is not just about building more qubits: It is about building better qubits, smarter architectures with better connectivity and better operation frameworks.

Learn how to implement quantum-safe encryption in your organization:

https://www.edx.org/learn/communication/delft-university-of-technology-towards-sq-transition-and-management-aspects