Is China close to cracking RSA encryption?

Chinese researchers have presented a very powerful new algorithm on paper, but the American contingent is skeptical.

Along with artificial intelligence, quantum computing is regularly mentioned among the technologies that could completely change the face of humanity.

The power of this technology comes from its ability to store complex information in the form of subtle differences in the state of matter. Indeed, quantum computers work thanks to different logical subunits than the bits found in traditional computers; we’re talking about qubits here.

In very vulgar terms, their special feature is that they can exist in several different states at the same time, unlike ordinary bits that take the value 1 or 0. Without going into detail, the important thing to remember is that this architecture makes it possible to deal with it. certain problems much faster than lambda PC.

Current encryption algorithms are on borrowed time

As they mature, quantum computers will lead to dramatic advances. And this applies to almost every possible and imaginable discipline. But there is an opposite side to this. With such a machine, it would theoretically be possible to pulverize all modern encryption algorithms. Including the strongest ones.

Quite a scary prospect. Because today these algorithms make it possible to protect many critical and sensitive infrastructures and services. A simple and very impressive example: with the existing mature quantum computer, the concept of passwords as we know them today is in danger of breaking down.

Therefore, the current algorithms must be replaced very quickly by other encryption systems that can withstand the attack of quantum computers. There are already several systems that can take over. But to hastily make such a drastic switch from a global infrastructure would surely be an extremely dangerous leap of an angel.

The good news is that we are still a long way from that deadline. Experts traditionally believe that several million qubit machines are needed to crack the most advanced encryption algorithms. For now, the most powerful quantum computers have to make do with a few hundred qubits. Even Osprey, the record quantum processor introduced by IBM in autumn 2022, offers only 433 units (see our article).

Or at least everyone thought so. Because last weekend, the scientific community was in for a big surprise. Experts were caught off guard by the recent work of China’s Tsinghua University.

Quite a revolutionary algorithm… on paper

According to the South China Morning Post, the team led by Professor Long Guilu a new algorithm It is based on Shor’s algorithm. The latter is a mathematical tool proposed in 1994 by the physicist of the same name. In theory, it would make a quantum computer quite fast when it comes to cracking a password.

The researchers explain that their new algorithm, called SQIF (Sublinear Resource Quantum Integer Factorization), will dramatically reduce the number of qubits needed to reach practical applications. And we’re not talking about a small drop; they claim that their algorithm will allow a 372-qubit machine to crack RSA-2048!

For reference, this is one of the strongest security standards in the digital world. It should be a few hundred billion years to a standard computer to find the 2048 elements of the key. If so, he would be holy revolution in the world of computer securityat all levels.

IBM’s Q System One, the first circuit-based quantum computer. © IBM Research

However, when a team in science makes such grandiose claims, the paper had better have exceptionally strong theoretical foundations. And this is where the problem starts to get both very confusing and very interesting. Indeed, the demonstration part did not justify the initial claims.

As a proof of concept, the researchers cracked a 48-bit encryption key with a tiny quantum computer of just 10 qubits. The result is certainly impressive, but far from threatening RSA-2048. Especially since the researchers have no idea suggested any track that would allow you to switch between their results and this goal. And this point in particular raised a few eyebrows.

The first disturbing element is that it is not no secret-defense secret business. However, traditionally, great powers like China have tended to put a leaden veil over any technology that could give them a decisive strategic advantage. This apparent discrepancy alerted the scientific community. Some researchers seriously doubt the reliability of the results.

Much criticized works

We can cite a particular example Scott Aaronson, a great American expert on algorithms and encryption. He maintains an interesting blog where he often provides very well-versed analyzes of such issues. A few years ago, he created a text in which he explained how solving one of the Millennium Problems in particular would allow us to obtain all available bitcoins.

Solving this mathematical problem would allow us to monopolize all existing bitcoins

To say the least, he is particularly skeptical of the Chinese team’s claims. “ It seems to me that it would take a miracle for this approach to be of any use “, he says in a blog post. ” In 25 years of quantum computing research, I’ve rarely seen a paper so actively misleading… and I’ve seen a lot. »

And he’s not the only one who thinks so. Peter Shore, the author of the original algorithm that formed the basis of SQIF, also voiced some of the reservations uncovered by SCMP. ” There seem to be several possible problems with this paper “, he replied to one of his colleagues who accused the Chinese team ” important technical details are omitted “. The arrangement may seem very sober, but in the academic world it is quite a frontal assault.

Looking at these diverse views, a surprising trend emerges. It turns out that most of the open criticism comes from the same place, the United States. However, things immediately get more complicated when a question involves both Chi and Uncle Sam.

Indeed, the two superpowers are currently engaged in a kind of pseudo-cold war. They are actively trying to put spokes on the wheels. This is especially evident on the American side; For example, the Biden administration has launched a massive subsidy plan worth several hundred billion, the purported and purported purpose of which is “ counter china (see our article).

Meeting between Xi Jinping and Joe Biden
Although both reject the term, China and the US are still in what looks like the germ of a Cold War. © Xinhua via Global Times

We find ourselves in a somewhat comical situation. Because when the United States speaks to China and vice versa, it is often difficult to determine what constitutes legitimate propaganda or criticism. Especially since the two giants made it a point of honor to cover their tracks.

A nauseating artistic blur

These ads are a a vast political smokescreen intended to panic the American administration ? This seems unlikely, as Long is a fairly reputable researcher. Another prominent Chinese encryption expert, interviewed by SCMP on condition of anonymity, wanted to defend it anyway. ” Professor Long does serious research and has always been discreet “, the interested party explains. ” He is not willing to risk his academic reputation for political reasons. »

As well as a a great scientific advance that Americans would refuse to recognize because of their pride ? It also seems far-fetched because even though they are mostly American, the reviews still come from cited experts.

Also just a a slightly misleading scientific publication because there are already millions but would cause strong reactions only due to the research topic ? This seems to be the most satisfactory explanation of this scientific-political imbroglio. But for now it is impossible to be sure.

Indeed, the paper has not yet passed the peer review stage. This is an important step in the scientific publication process, where other experts must check the validity of the research before it is published. Therefore, it will be necessary to wait for the article to finish its academic course.

In any case, this incident clearly shows that this topic is beginning to cause some excitement among the major world powers; gives us A taste of the friction and major upheavals that can occur when a country finally embraces this revolutionary technology. It will therefore be interesting to observe how the Chinese and American governments will manage this transition and what place Europe will play in this story.

The text of the pre-publication study is available here.

Leave a Reply

Your email address will not be published. Required fields are marked *