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 them depends on the 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, such as 261980999226229. This algebraic expression has been factored by a crude quantum computer in an experiment by Chinese scientists published in arxivnot yet reviewed, and has exposed the vulnerability of the system and, therefore, of the entire digital society.

“The fact that quantum computing is a risk for the encryption methods we have today is well known. In 1994, Peter Short [matematico del Instituto de Tecnologia de Massachusetts] showed that a quantum computer could solve the factorization problem efficiently”, warns Antonio Acin, research professor at the Institute of Photonic Sciences (ICFO).

This opinion is not singular. A 2020 UK National Cybersecurity Center paper acknowledges “the serious threat that quantum computers pose to long-term cryptographic security.” The National Institute of Standards and Technology of the United States (NIST, for its acronym in English) has spent seven years looking for security algorithms resistant to quantum computing and some of the proposals have been violated in just over two days with a laptop, such as Ward Beullens of the IBM research center in Zurich, Switzerland, demonstrated last year.

Most researchers consider 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 (only divisible by themselves or one), requires a robust quantum computer, without errors, and millions of of qubits. The last one presented, the IBM Osprey processor, is 433 qubits. Guilu Long, a physicist at Tsinghua University in China, acknowledges in Nature, that “increasing the number of qubits without reducing the error rate is not enough.”

“Current cryptography”, as explained by the physicist Antonio Acin, “we think it is safe because, today, we do not have an efficient factorization algorithm. Humanity has been trying to find it since classical Greece and has not been found. 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. We don’t have the necessary yet, but today’s world of encryption may be vulnerable as soon as it develops.”

This ephemeral security that allows the maintenance of digital society today has been questioned by a team led by Bao Yang, from Shanghai Jiaotong University, when factoring a 48-bit key with a computer of only 10 qubits. The Chinese group affirms that with 372 qubits, the developed factorization algorithm could break an RSA key of more than 600 digits.

Acin explains that the problem he solves “is not impressive because it can be done with classic computers.” “They don’t prove anything. They simply prove that, in this case, it has worked and, perhaps, in the future it will continue to work”. The conclusion of vulnerability of keys with 600 digits is excessive, according to the Spanish physicist. Scott Aaronson, an expert in quantum computing at the University of Texas agrees. “This is one of the most misleading quantum computing articles I have seen in 25 years. And I have seen many ”, he writes on his blog Shtetl-Optimized.

However, Acin acknowledges a merit of the work: “It proposes an astute way to solve it.” The work evades Shor’s algorithm and uses that of mathematician Claus Schnorr, from the Goethe University in Frankfurt (Germany) to factor integers. “It is good because they 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 is interesting and original”, says Acin.

In any case, the Chinese article has managed to recall the vulnerability of the current encryption system. Something that worries all companies and governments in the world. In this sense, 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 is 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 second depends on the development of quantum computing itself, which is still in its infancy, and requires specific equipment, but it is already available.

Both ways are challenging, as the UK National Cybersecurity Center acknowledges: “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 and 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. 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. A source capable of generating truly random unpredictable numbers are muons”, explains Tanaka.

The proposed system is based on the fact that the speed of arrival of these subatomic particles is always random and that 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 overcome.

You can write to [email protected]will follow THE COUNTRY TECHNOLOGY in Facebook and Twitter and sign up here to receive our weekly newsletter.