You are looking at a specific version 20190911:071626 of this paper. See the latest version.

Paper 2019/1019

Revisiting the Hybrid attack on sparse and ternary secret LWE

Yongha Son and Jung Hee Cheon

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. WAHC 2019
Keywords
Lattice-based CryptographyLearning with ErrorsHomomorphic EncryptionThe Hybrid Attack
Contact author(s)
emsskk @ snu ac kr
History
2019-09-11: received
Short URL
https://ia.cr/2019/1019
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.