Paper 2019/1019 Original: eprint.iacr.org/2019/1019 ↗

Revisiting the Hybrid attack on sparse and ternary secret LWE

Abstract

In the practical use of the Learning With Error (LWE) based cryptosystems, it is quite common to choose the secret to be extremely small: one popular choice is ternary ($\pm 1, 0$) coefficient vector, and some further use ternary vector having only small numbers of nonzero coefficient, what is called sparse and ternary vector. This use of small secret also benefits to attack algorithms against LWE, and currently LWE-based cryptosystems including homomorphic encryptions (HE) set parameters based on the attack complexity of those improved attacks. In this work, we revisit the well-known Howgrave-Graham's hybrid attack, which was originally designed to solve the NTRU problem, with respect to sparse and ternary secret LWE case, and also refine the previous analysis for the hybrid attack in line with LWE setting. Moreover, upon our analysis we estimate attack complexity of the hybrid attack for several LWE parameters. As a result, we argue the currently used HE parameters should be raised to maintain the same security level by considering the hybrid attack; for example, the parameter set $(n, \log q, \sigma) = (65536, 1240, 3.2)$ with Hamming weight of secret key $h = 64,$ which was estimated to satisfy $\ge 128$ bit-security by the previously considered attacks, is newly estimated to provide only $113$ bit-security by the hybrid attack.