How quantum computing threatens internet security

Internet security – from the most common banking transaction to conversations on messaging platforms – rests mainly on cryptographic keys: strings of characters encrypted by an algorithm.

The difficulty to decipher these keys depends on factorization – the decomposition of an algebraic expression in the form of a product. That is to say: six is equal to three times two. But this simple operation becomes extraordinarily complex if the given number exceeds a relatively small number of digits.

Take a look at this number: 261980999226229. This algebraic expression has been factored by a crude quantum computer in an experiment by Chinese scientists. Published on ArXiv – an online archive run by Cornell University – this unreviewed study has exposed the vulnerability of the encryption system and, therefore, the vulnerability of our entire digital society.

“The fact that quantum computing is a risk for the encryption methods we use today is well known. In 1994, Peter Shor (a mathematician at MIT) showed that a quantum computer could solve the factorization problem efficiently,” warns Antonio Acín, a research professor at the Institute of Photonic Sciences (ICFO) in Barcelona, Spain.

This opinion is not unique. A 2020 paper put out by the UK’s National Cyber Security Centre acknowledges “the serious threat that quantum computers pose to long-term cryptographic security.”

If we dispense with this key-sharing idea and instead find a way to use unpredictable random numbers to encrypt information, the system might be immune

Hiroyuki Tanaka, University of Tokyo

The USA’s National Institute of Standards and Technology (NIST) has spent seven years looking for security algorithms that are resistant to quantum computing. However, some of the proposals have been cracked in just over two days with a laptop. Ward Beullens – of the IBM research center in Zurich, Switzerland – demonstrated this in 2022.

Most researchers think that, for the quantum threat to be feasible, further development of this fledgling science is still necessary. Shor’s algorithm – the formula to decipher current systems, called Rivest-Shamir-Adleman (or RSA) and based on large prime numbers – requires a robust quantum computer, without errors, and millions of qubits (basic units of information in a quantum computer). The last one unveiled – the IBM Osprey processor – has merely 433 qubits.

In the journal Nature, Guilu Long – a physicist at Tsinghua University in China – acknowledges that “increasing the number of qubits without reducing the error rate is not enough.”

“We think that [today’s] cryptography is safe because, at the moment, we don’t have an efficient factorization algorithm,” explains Acín. “Humanity has been trying to find it since classical Greece (...) but it could happen that tomorrow, some very clever mathematician finds this algorithm and knocks everything down. This clever mathematician could be a quantum computer. Today’s world of encryption may be vulnerable as soon as [this is developed].”

The ephemeral security that has allowed for the maintenance of digital society is now being questioned by a team led by Bao Yang, from Shanghai Jiaotong University, after they factored a 48-bit key with a computer of only 10 qubits. The Chinese group stated that, with 372 qubits, the developed factorization algorithm could break an RSA key of more than 600 digits.

However, Acín claims that the problem solved “isn’t impressive, as it can be done with classic computers.”

“They haven’t proven anything. They simply prove that, in this case, it has worked and, perhaps, in the future, it will continue to work.” According to the Spanish physicist, the expectation of being able to break an RSA key made up of 600 digits is excessive.

Scott Aaronson – an expert in quantum computing at the University of Texas – agrees. “This is one of the most actively misleading quantum computing articles I have seen in 25 years. And I’ve seen many,” he wrote on his blog, Shtetl-Optimized.

The work evades Shor’s algorithm and uses one by the mathematician Claus Schnorr – from Goethe University in Frankfurt, Germany – to factor integers.

“This is good because [the researchers] indicate that we should not stick to Shor’s algorithm – which we know requires a very powerful computer – and that the terms can be shortened if we look for an alternative. That’s interesting and original,” says Acín, acknowledging a merit of the Yang team’s publication.

In any case, the Chinese article has managed to highlight the vulnerability of the current encryption system – something that is of concern to companies and governments all over the world. On this subject, the Spanish physicist explains that he is working on two possible solutions. The first is to “replace factorization with other problems that are more difficult for a quantum computer.” It’s the formula that NIST has been looking for for seven years.

The second is to develop “schemes whose security is based on the laws of quantum physics.” This solution depends on the development of quantum computing itself – which is still in its infancy – and requires specific equipment.

Both ways forward are challenging, as the UK National Cyber Security Centre notes: “The transition to any form of new cryptographic infrastructure is a complex and costly process that needs to be carefully planned and managed. There are security risks as systems change and business continuity risks if there is an unforeseen dependency on cryptographic components.”

A team from the University of Tokyo led by Hiroyuki Tanaka has proposed in iScience an alternative security system called Cosmocat. It is based on muons – short-lived subatomic particles (2.2 microseconds) – that are only found in cosmic rays and in laboratories.

“Basically, the problem with our current security paradigm is that it relies on encrypted information and decryption keys that are sent over a network from sender to receiver. Regardless of the way the messages are encrypted, in theory, someone can intercept and use the keys to decrypt apparently secure messages. Quantum computers simply make this process faster,” Tanaka explains.

“If we dispense with this key-sharing idea and instead find a way to use unpredictable random numbers to encrypt information, the system might be immune. [Muons] are capable of generating truly unpredictable numbers.”

The proposed system is based on the fact that the speed of arrival of these subatomic particles is always random. This would be the key to encrypt and decrypt the message, if there is a synchronized sender and receiver. In this way, the sending of keys would be avoided, according to the Japanese team. However, muon detection devices are large, complex and power-hungry, limitations that Tanaka believes the technology could ultimately overcome.

Sign up for our weekly newsletter to get more English-language news coverage from EL PAÍS USA Edition