Paper 2022/1473

A Hybrid of Lattice-reduction and Meet-LWE via Near-Collision on Babai's Plane

Abstract

A cryptographic primitive based on the Learning With Errors (LWE) problem with variants is a promising candidate for the efficient quantum-resistant public key cryptosystem. As the parameters for such cryptosystems are chosen by the concrete attack cost for the corresponding LWE problem, improving the LWE solving algorithm has a significant importance. In this paper, we present a new hybrid attack on the LWE problem. This new attack combines the primal lattice attack and an improved variant of the MitM attack, Meet-LWE, suggested by May (Crypto'21). This resolves the major open problem posed in the same paper. To this end, we develop several technical tools for hybrid attacks; a new property of Babai's nearest plane algorithm with respect to projection, an approximate variant of Meet-LWE, and a locality-sensitive hashing-based near-collision finding algorithm. We also present a comprehensive analysis of the proposed attack, which involves the complicated arguments of both lattice and representation techniques. We finally estimate the concrete cost of our attack for sparse LWE keys. For some currently deployed parameter sets in fully homomorphic encryption libraries, our attack achieves up to $10$ bits improvement than the previous primal hybrid attacks.