Welcome to the resource topic for 2019/1019
Title:
Revisiting the Hybrid attack on sparse and ternary secret LWE
Authors: Yongha Son, 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.
ePrint: https://eprint.iacr.org/2019/1019
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .