Chinese Researchers Claim Quantum Encryption Hack

Chinese researchers claim to have broken a standard RSA algorithm – a public-key cryptosystem that is widely used for secure data transmission – using a quantum computer.

The researchers at the Beijing Academy of Quantum Information Sciences made the claim late last month on the arXiv repository, an open repository for scientific papers, noting that their quantum computing method was successful in a small-scale demonstration.

However, many experts remain skeptical that this method could be scaled up to outperform conventional computers in the task. They believe it will be many years before quantum computers can outperform conventional computers at decrypting cryptographic keys, the strings of characters used in an encryption algorithm to protect data. 

Shor's Algorithm vs. Schnorr’s Algorithm

One proposed method for breaking RSA is Shor's algorithm, which uses quantum computing to find the prime factors of an integer. It could break RSA encryption ten times faster than classical computing methods.

But applying Shor's method would require a quantum computer substantially more powerful than current prototypes. Researchers estimate breaking RSA encryption with this method would require one million or more qubits.

Shijie Wei, who led the Beijing Academy of Quantum Information Sciences team, instead used Schnorr's algorithm, another method for factoring integer numbers used in digital signatures. Although Schnorr's algorithm was created to function on a classical computer, Wei's team used the quantum approximate optimization algorithm (QAOA) to perform a portion of the process on a quantum computer.

The researchers claim that their algorithm can crack strong RSA keys using only 372 qubits. Critics contend that running the QAOA algorithm on such a small machine would require each of the 372 qubits to work without errors 99.9999% of the time. 

It's also uncertain whether using the QAOA speeds up factoring huge numbers compared to using Schnorr's algorithm on a classic computer. The research paper admitted this, reading: "It should be pointed out that the quantum speedup of the algorithm is unclear."  

Experts believe that while this Schnorr-based method may not pose an immediate threat to online security, it is only a matter of time before Shor's algorithm executed on a quantum computer could do so.