Hybrid attack on Learning with Errors (LWE) with sparse secret
- Pages
- 10-15
Abstract
In 2007, Howgrave-Graham proposed attack against NTRU cryptosystem, which consists of two parts, combining lattice reduction technique and a combinatorial method called meet-in-the-middle (MiTM). In this article, we apply hybrid attack to the Learning with Errors Problem (LWE) with sparse secret. The LWE problem is considered to be one of the most important in lattice-based cryptography. Large number of cryprographic schemes ranging from basic signature and encryption schemes to advanced schemes like group signatures and fully homomorphic encryption, base their security on the hardness assumption of LWE. In this paper, we review the hybrid attack and the algorithms it is based on. It is required for further practical implementation of the attack, whose main objective is to verify correctness of MiTM to the hybrid attack against the LWE problem.