Physics, mathematics, and technology

2020 Issue №4

Back to the list Download the article

Hybrid attack on Learning with Errors (LWE) with sparse secret



In 2007, Howgrave-Graham proposed attack against NTRU cryptosys­tem, 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 sec­ret. The LWE problem is considered to be one of the most important in lat­tice-based cryptography. Large number of cryprographic schemes ranging from basic signature and encryption schemes to advanced schemes like group sig­natures and fully homomorphic encryption, base their security on the hard­ness 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 hyb­rid attack against the LWE problem.