Chinese researchers claim to have introduced a new code-breaking algorithm that, if successful, could render mainstream encryption powerless within years rather than decades.
Chinese researchers claim to have introduced a new code-breaking algorithm that, if successful, could render mainstream encryption powerless within years rather than decades.
The team, led by Professor Long Guilu of Tsinghua University, proclaimed that a modest quantum computer constructed with currently available technology could run their algorithm, South China Morning Post (SCMP) reported on Wednesday.
The “new algorithm could dramatically reduce the scale of a practical quantum computer to 372 qubits – even less than that of Osprey [most powerful quantum processor in the world],” said the researchers in a non-peer-reviewed study.
Large-number factoring, a challenging process for conventional computers, can be accelerated by quantum computers to break codes quickly.
However, it is generally accepted that in order to breach a bank account secured by cutting-edge encryption, such a machine would need to manage millions of qubits, the fundamental building block of quantum information.
The new technique
The new technique developed by the Chinese team has the potential to drastically lower the size of a practical quantum computer to 372 qubits, noted the SCMP report.
This is even less than IBM’s Osprey, the most potent quantum computer in the world, which only has 433 qubits and is incapable of cracking codes.
The Chinese researchers argue that their new algorithm, called sublinear-resource quantum integer factorization (SQIF), can decipher data encrypted with RSA-2048.
This asymmetric cryptography is one of the most stringent industry standards used by many governments, financial institutions, and technology firms to protect information security with a 2048-bit-long key.
Shor’s algorithm, a mathematical tool developed by American physicist Peter Shor in 1994 that, in theory, could make a quantum computer much faster than a classical computer in code-breaking, performed inefficiently in real quantum circuits, according to Long’s team.
The Chinese team created SQIF to optimize the quantum calculation process based on a contentious algorithm developed by German mathematician Claus Schnorr in 2013.
To demonstrate the feasibility of SQIF, the researchers used a tiny 10-qubit superconductive quantum computer at Zhejiang University in Hangzhou to break a 48-bit-long encryption key.
The team claims that SQIF is “the most qubit-saving factorization algorithm to date” and that quantum computers capable of handling hundreds of qubits are on the horizon.
“Our study shows great promise in expediting the application of current noisy quantum computers and paves the way to factor large integers of realistic cryptographic significance,” claimed the group.
U.S. experts rebut Long’s study
The statements made by the Chinese academics have, however, sparked worries and doubts from some leading security and quantum specialists in the United States.
The study “is something to take seriously,” according to American cryptographer and computer expert Bruce Schneier, who has testified before the U.S. Congress on matters relating to information security.
On January 3, Schneier, the head of security architecture at Inrupt, said on his blog, “It might not be correct, but it’s not obviously wrong.”
But “there’s the nagging question of why the Chinese government didn’t classify this research,” he questioned.
Despite acknowledging Schneier’s worry, Scott Aaronson, the head of the quantum information center at the University of Texas in Austin, stated he did not think Long’s approach would be successful.
“It seems to me that a miracle would be required for the approach here to yield any benefit at all, compared to just running the classical Schnorr’s algorithm on your laptop,” Aaronson wrote in a blog.
“This is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen many,” he said, doubting the authenticity of the study.
Lawrence Gasman, the founder and president of the website Inside Quantum Technology, which covers advances in quantum technology, referring to Long’s claim, warned that “if it is true, it is catastrophic.”
However, “If an idea is interesting, it is probably wrong,” Gasman said, quoting his former MBA teachers.
The controversial paper was first posted on the scholarly article website arxiv.org last month.
Source: China’s new quantum code-breaking algorithm raises concerns in the US
