Further improvements of the estimation of key enumeration with applications to solving LWE

In post-quantum cryptography (PQC), Learning With Errors (LWE) is one of the dominant underlying mathematical problems. For example, in NIST's PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. The primal and the dual attacks are the two main strategies considered for solving the underlying LWE problem of multiple cryptographic schemes, including Kyber. Recently, the dual attack gathered significant attention within the research community. A series of studies initially suggested that it might be more efficient than the primal attack. Then, a subsequent work by Ducas and Pulles (Crypto'23) raised doubts on the estimated complexity of such an approach. The attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key.

Previous works dealt with this problem either using unexplained models for estimating the cost of enumeration or by using unnecessarily pessimistic upper limit formulas. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to decrease the estimated cost of this procedure and, hence, of the whole attack both classically and quantumly. In addition, we explore different enumeration strategies to achieve some further improvements. Our work is independent from the questions raised by Ducas and Pulles which do not concern the estimation of the enumeration procedure in the dual attack.

As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas.