Paper 2022/1473

Let's Meet Ternary Keys on Babai's Plane: A Hybrid of Lattice-reduction and Meet-LWE

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 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, recently 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. In particular, we take special care in specifying the relevant heuristics and also provide some experimental evidence for them. We finally estimate the concrete cost of our attack, and observe better cost for sparse LWE/NTRU keys than the other existing attacks. In particular, this result has a direct effect on the currently deployed parameter sets used in some fully homomorphic encryption libraries.