Update: On 18 April, Yilei Chen announced an issue with his algorithm which he does not know how to fix. This means the algorithm does not undermine the mathematics behind post-quantum cryptography. The issue was found independently by researchers Hongxun Wu and Thomas Vidick.
An algorithm that could break supposedly future-proofed encryption methods has cryptographers scrambling to understand the threat, though there is no immediate danger of hackers gaining access to encrypted data.
Quantum computers threaten to one day crack the widely used encryption algorithms that keep banking, email and other data safe, so researchers having been working to develop 鈥�post-quantum鈥� algorithms to replace them. Many of these are based on 鈥渓attice problems鈥�, an area of mathematics that involves regular patterns, or lattices, in space. The algorithms have been approved as secure by standards bodies and are already being adopted industry-wide to prepare for the arrival of quantum computers.
Advertisement
Now, at Tsinghua University in Beijing, China, has to solve these lattice problems faster than is currently possible. Ironically, because Chen鈥檚 algorithm is designed to run on quantum computers, it would only be able to break the encryption designed to be resilient to quantum computers once a powerful quantum computer is created.
There have been suggestions in the past that post-quantum cryptography (PQC) algorithms have security problems, although experts were dubious about their veracity. But Chen鈥檚 algorithm could present more fundamental problems, if proved to be correct, because it attacks the underlying mathematics of the encryption algorithms.
Chen鈥檚 algorithm is extremely complicated, involving nine phases and esoteric mathematics, and it is difficult to intuit how it works. Despite this, there is a widespread effort to understand his work, given the potential risks. 鈥淚t鈥檚 clearly a major concern for the prospects for quantum-resistant cryptography if it鈥檚 correct, and not a concern if it鈥檚 incorrect,鈥� says at the University of Texas at Austin.
Chen declined a request for interview, stating that he preferred to wait for the research to be peer reviewed before commenting. He told New Scientist only that 鈥渢he paper is rather complicated and technical鈥�.
But a released by Tsinghua University said: 鈥淭his could be seen as the greatest breakthrough in quantum algorithms since Peter Shor鈥檚 celebrated algorithm for factoring large numbers 30 years ago.鈥� This is a reference to an algorithm capable of breaking many currently used encryption methods with a sufficiently large quantum computer.
The statement also says that the algorithm, if proved correct, 鈥渕ay have a disruptive effect鈥� on efforts by the US standards body the National Institute of Standards and Technology (NIST) to develop PQC algorithms. 鈥淭he current work would likely cast doubt on their security,鈥� it says.
鈥淚t鈥檚 still really early, and the community has not had enough time to thoroughly evaluate the paper and all its details,鈥� says at NIST. 鈥淲e鈥檝e always known that as PQC is an active research area, that new results could be discovered at any time. For this reason we have ensured that we will have multiple algorithms available, not only those based on lattices.鈥� Of those algorithms approved by NIST so far, three out of four use lattices.
at KU Leuven in Belgium also says it is too early to be concerned. Firstly, Chen鈥檚 algorithm only works with a large, reliable quantum computer 鈥� which doesn鈥檛 yet exist. Added to this, it also only speeds up solving lattice problems that involve numbers far larger than those used in PQC, and it isn鈥檛 clear if it can provide a similar boost to the smaller problems used in practical applications, he says.
鈥淵ou have to build a quantum computer, the algorithm has to be correct and your numbers have to be big enough that the algorithm applies,鈥� says Smart. 鈥淭here鈥檚 a lot of ifs.鈥�
