Assessing the impact of a variant of the lastest dual attack

The dual attacks on the Learning With Errors (LWE) problem are currently a subject of controversy within the cryptographic community. In particular, the results of [MATZOV 2022], which assert a substantial reduction in the security level of Kyber— a lattice-based cryptosystem currently being standardized by NIST— have not gained widespread acceptance. Their attack analysis relies on several assumptions that, in certain contexts, contradict established theorems or well-supported heuristics, as noted in [Ducas-Pulles 2023].

In this presentation, I will discuss a collaborative effort with Charles Meyer-Hilfiger, Yixin Shen, and Jean-Pierre Tillich, where we propose a novel dual lattice attack on LWE that reexamines the approach of [MATZOV 2022]. Their method involves transforming a small-LWE problem (defined by a small secret) into another small-LWE problem, which is then reduced to a standard LWE problem where the secret is no longer small but the dimension has been significantly decreased. This second reduction relies on a modulus switching technique. We expand upon this strategy by employing a code-based approach using polar codes over ZZ_q.

I will present a new analysis of our variant of [MATZOV 2022] that does not rely on the independence assumption that they made and which has been challenged by [Ducas-Pulles 2023]. Our results demonstrate that the complexities reported in [MATZOV 2022] are, in fact, achievable.