Quantum computing presents great opportunities, but it also poses great threats to the security of the Internet. Certain mathematical problems that form the basis of today’s most common cryptographic algorithms are much easier to solve in quantum than in “classical” computers. Chinese researchers recently claimed that existing algorithms could be used in today’s quantum computers to defeat the RSA algorithm, the fundamental underpinning of secure Internet communications. At the same time, there are doubts about the reliability of the publication.
The underlying claim of the paper, published last Christmas by 24 Chinese researchers, is that they have discovered an algorithm that can break 2,048-bit RSA keys even on the relatively low-power quantum computers currently available. That’s what it means.
The fact that quantum computers pose a general risk to the reliability of cryptographic procedures that ensure secure Internet communications, such as RSA open-key cryptography and the Diffie-Hellman key exchange algorithm, is nothing new. These procedures are based on mathematical problems that are practically unsolvable on conventional computers, but can be solved in hours with a sufficiently powerful quantum computer. In this case, big enough means 20 million quantum bits (qubits). The problem with this 20 million number is that IBM’s quantum computer, the largest quantum computer known today, can only render 433 of his 20 million qubits.
It’s no exaggeration to say that Chinese researchers chose one of the steepest hills to climb. But will they really be able to overcome this ordeal?
Integer factorization is the most widely used infeasible mathematical problem to ensure that cryptographic algorithms are virtually unbreakable. Factoring numbers with a few digits is trivial (15 = 3 * 5), but the computational power required increases exponentially with the number of digits. For hundreds or even thousands of digits, the effort required to compute it is so enormous that even with the most powerful supercomputers, the time required to compute it would roughly equal the lifetime of the universe. increase.
According to the National Institute of Standards and Technology (NIST) recommendation, the minimum RSA key size considered secure is 2048 bits. This means about 600 digits, but larger keys of 3,072 or 4,096 bits are also often used. There, the number of decimal digits already exceeds 1000, making these keys practically infeasible by conventional methods.
In 1994, Peter Scholl had already come up with an algorithm that could perform prime factorization much more efficiently than before on quantum computers, which existed only in theory at the time. This breakthrough means that a significant portion of our encryption procedures are no longer breakable.
Has the cipher apocalypse arrived?
Chinese researchers could only provide a theoretical answer to this question. Because the solutions and techniques they outlined require a 372-qubit computer. Such a computer exists within his IBM walls, but the Chinese researcher did not have this machine at his disposal. However, they succeeded in factoring a 48-bit (15-digit) number on his 10-qubit computer.
This may not seem like much of a breakthrough, but note that this is the largest number ever factored using a common algorithm. Not to mention the fact that I was able to put theory into practice. The question is whether we were able to close the aforementioned gaps. A correspondence between Bruce Schneier, one of his iconic figures in IT security, and Roger A. Grimes, author of several books on cryptography, revealed the following:
“Apparently another person had previously announced that he was able to break conventional asymmetric cryptography using a conventional computer… but a reviewer found a flaw in his algorithm, and the person The paper had to be retracted, but this Chinese team realized that the step that killed everything could be solved by a tiny quantum computer, so they tested it and it worked.”
You might think the cryptic apocalypse is here.
keep calm and dig deep
The basis of the Chinese researcher’s algorithm relies on Claus Schnorr’s factorization algorithm (not to be confused with Shor’s algorithm). The Schnorr algorithm works well for small numbers, which the researchers themselves have tested, but breaks down for large numbers. It is precisely this limitation that Chinese researchers claim to have overcome. However, the details are not mentioned, and the lack of a quantum computer with sufficient capacity has prevented us from proving the full theory in practice. As Schneier quoted the situation on his blog:
“Thus, if it is true that the Chinese paper relies on this Schnorr method that does not scale, then neither does the method in this Chinese paper. I think it breaks a bunch of cryptosystems, too.)”
Will uncertainty remain until someone tries the algorithm on a sufficiently large quantum computer?
In fact, there are some signs that cast doubt on the whole story. One of his is the Chinese researcher’s failure to win his $200,000 prize offered in the RSA factoring challenge to anyone who successfully cracks his 2048-bit RSA key. . Of course, you could say they didn’t have the necessary hardware, but even if it was shared, it would certainly have been worth it to send a letter to IBM for the prize.
Those who are drawn to conspiracy theories may ask why the Chinese government didn’t keep the discovery for themselves and started pouring money into developing a proper quantum computer. This obviously costs a lot, but it also brings huge benefits.
At the same time, there is also strong skepticism from the scientific side. Scott Aaronson, a former MIT researcher now at the University of Texas, made a shocking statement on his blog about the Chinese paper. Aaronson focuses primarily on quantum computing and complexity theory in his research. This is probably the most important scientific area on our topic. Here is his three-word review of the publication’s content: Just no. He categorically criticized the publication.
“And finally, they clarify one important point in one sentence in the conclusion section. We should point out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA. “Unknown” is an understatement. It seems to me that it would take a miracle for the approach here to provide any benefit compared to running classical Schnorr’s algorithm on a laptop. If the latter he could have broken RSA, he would have already. Overall, this is one of the most actively misleading quantum computing papers I’ve seen in his 25 years, and I’ve seen many. ”
Aaronson isn’t alone in his opinion. Many others have criticized this study on the same basis.
“There may be obvious problems with this paper.”
It should also be emphasized that the research-sharing platform (arXiv) in which the Chinese studies were published was not peer-reviewed. This means that the mere fact of being published doesn’t mean much, especially in popular fields like quantum computing and cryptography. .
In popular and highly regarded fields like cryptography and quantum computing, even if we could recognize all the research paper factories we would inevitably expect, the harsh reality remains. Surviving the challenges posed by quantum computers could become dangerous in the not too distant future. As a result, to mitigate the impact of the Harvest Now Decrypt Later technique, we need to use algorithms that are considered secure against attacks by quantum computers (because they cannot be ruled out).
In the case of high-profile encryption issues like 2014’s Heartbleed, the market reacted relatively quickly, but it took several weeks before the 100,000 most-visited pages were free of errors. Other less-hyped cases can take years, according to Qualys Pulse statistics. In other words, we cannot expect the introduction of post-quantum cryptography to happen much sooner than this.
This is just like global warming, and it is a problem that cannot be helped if it becomes serious in the future. It has to deal with the present. The similarity is amazing given the fact that scientists have been horrifying people with horror stories about quantum computers for decades. What seemed like theory for a while is now a reality. IBM promises him a 1,000-qubit computer by the end of the year, and Google promises him a million-qubit computer by the end of his decade. The latter does not promise good results as it is only a matter of data storage capacity, i.e. how much data can be accessed after the RSA is decryptable.
The first to have a sufficiently capable machine will probably be the still-much-criticized tech giant and the most powerful state. Legislators sometimes call for cryptographic backdoors despite warning of the serious risks involved, but with technological breakthroughs like this, they don’t necessarily have to. But this can have unpredictable consequences, both for privacy and the consequences of disputes that are increasingly transferred to cyberspace.
