Paper 2019/1019

Revisiting the Hybrid attack on sparse and ternary secret LWE

Yongha Son and Jung Hee Cheon


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. WAHC 2019
Lattice-based CryptographyLearning with ErrorsHomomorphic EncryptionThe Hybrid Attack
Contact author(s)
emsskk @ snu ac kr
2019-09-11: received
Short URL
Creative Commons Attribution


      author = {Yongha Son and Jung Hee Cheon},
      title = {Revisiting the Hybrid attack on sparse and ternary secret LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1019},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.