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 SonAbstract:
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.
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 .