This April, cryptography and security community have been stirred by a new research from Yilei Chen. If the claimed result held it could potentially impact the security of applied cryptography, especially in the era of quantum computing. This work was very difficult to immediately understand due to its complexity. But it is now retracted after finding a mistake.

"Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold."

Our public-key encryption systems are built on  mathematical problems assumed difficult to solve without a secret key (i.e. it's easy to encrypt, difficult to decrypt), such as those used in RSA or elliptic curve systems. The whole internet security depends on those being safe. But we know that quantum computers could one day undermine this security. That's what motivated the work on post-quantum computing, now being standardised and also test/deployed by big techology companies.

The new schemes include those based on lattice problems (i.e. NTRU, NewHope, Kyber, Dilithium). They work on similar core assumptions like the different ones we use today: it's simple to encrypt, difficult to decrypt (impossible, if you don't have the key).  While even the claimed progress in the now-retracted paper did not directly break them, it's fair to say that it somewhat reduced the sense of security. In other words: it was not supposed to be this way, and not so fast, at least. Furthermore, if those schemes would be broken, it would be pointless to migrate to them.

This issue underscores the ongoing evolution and challenges in cryptography, influenced heavily by the prospective quantum algorithm development. We need to watch this space.