Charles Meyer-Hilfiger (INRIA, Paris)

The cryptographic schemes that are used today over the Internet would be broken if a sufficiently powerful quantum computer existed. This fact, along with the recent advances in quantum computing, has started a research effort to find alternatives that are believed to be resistant to an adversary with a quantum computer. To that extent, and after a multi-year competition, the “National Institute of Standards and Technology” selected two so-called Post-Quantum encryption schemes for standardization: Kyber, a lattice-based scheme, and HQC, a code-based scheme. They are believed to be resistant to a quantum adversary and are bound to be widely used over the Internet in the coming years.

The security of HQC relies on the hardness of the decoding problem, and the security of Kyber relies on some generalization, the Learning with Error problem. Both problems can be stated as solving an underdetermined linear system (binary, say), but with an additional non-linear constraint that the solution is of small norm (Hamming weight, say). This additional constraint makes the problem hard. These problems have been actively studied for decades, and the complexity of the state-of-the-art algorithms to solve them is crucially used to correctly choose the secure parameters of those schemes.

The goal of this talk is to present an overview of the recent advances in the so-called dual attacks for solving these problems. In code-based cryptography the first dual attack was introduced by Al-Jabri in 2001, but his algorithm was somehow forgotten as it was shown to be completely uncompetitive against other existing techniques. However, with a series of recent works, it has been massively improved and now even asymptotically greatly outperforms all other known techniques in some regimes. In lattice-based cryptography also, dual attacks have even been greatly improved recently up to the point that they now dent the security of the NIST standard Kyber. These attacks are tricky to analyze, I will also give an overview of the techniques and tools developed to carry out their analysis.

This talk contains different joint works with Kévin Carrier, Thomas Debris-Alazard, Yixin Shen and Jean-Pierre Tillich.