[Resource Topic] 2022/1473: How to Meet Ternary LWE Keys on Babai’s Nearest Plane

Welcome to the resource topic for 2022/1473

How to Meet Ternary LWE Keys on Babai’s Nearest Plane

Authors: Minki Hhan, Jiseung Kim, Changmin Lee, Yongha Son


A cryptographic primitive based on the Learning With Errors (LWE) problem with its variants is a promising candidate for the efficient quantum-resistant public key cryptosystem. The recent schemes use the LWE problem with a small-norm or sparse secret key for better efficiency. Such constraints, however, lead to more tailor-made attacks and thus are a trade-off between efficiency and security. Improving the algorithm for the LWE problem with the constraints thus has a significant consequence in the concrete security of schemes.

In this paper, we present a new hybrid attack on the LWE problem. This new attack combines the primal lattice attack and an improved MitM attack called Meet-LWE, answering an open problem posed by May [Crypto’21].

According to our estimation, the new hybrid attack performs better than the previous attacks for the LWE problems with a sparse ternary secret key, which plays the significant role for the efficiency of fully homomorphic encryption schemes.

In terms of the technical part, we generalize the Meet-LWE algorithm to be compatible with Babai’s nearest plane algorithm. As a side contribution, we remove the error guessing step in Meet-LWE, resolving another open question.

ePrint: https://eprint.iacr.org/2022/1473

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .