TY - GEN
T1 - Practical analysis of key recovery attack against search-LWE problem
AU - Kudo, Momonari
AU - Yamaguchi, Junpei
AU - Guo, Yang
AU - Yasuda, Masaya
N1 - Funding Information:
This work was supported by CREST, JST. This work was also supported by JSPS KAKENHI Grant Number 16H02830.
Publisher Copyright:
© Springer International Publishing Switzerland 2016.
PY - 2016
Y1 - 2016
N2 - The security of a number of modern cryptographic schemes relies on the computational hardness of the learning with errors (LWE) problem. In 2015, Laine and Lauter analyzed a key recovery (or decoding) attack against the search variant of LWE. Their analysis is based on a generalization of the Boneh-Venkatesan method for the hidden number problem to LWE. They adopted the LLL algorithm and Babai’s nearest plane method in the attack against LWE, and they also demonstrated a successful range of the attack by experiments for hundreds of LWE instances. In this paper, we give an alternative analysis of the key recovery attack.While Laine and Lauter’s analysis gives explicit information about the effective approximation factor in the LLL algorithm and Babai’s nearest plane method, our analysis is useful to estimate which LWE instances can be solved by the key recovery attack. Furthermore, our analysis enables one to determine a successful range of the attack with practical lattice reduction such as the BKZ algorithm.
AB - The security of a number of modern cryptographic schemes relies on the computational hardness of the learning with errors (LWE) problem. In 2015, Laine and Lauter analyzed a key recovery (or decoding) attack against the search variant of LWE. Their analysis is based on a generalization of the Boneh-Venkatesan method for the hidden number problem to LWE. They adopted the LLL algorithm and Babai’s nearest plane method in the attack against LWE, and they also demonstrated a successful range of the attack by experiments for hundreds of LWE instances. In this paper, we give an alternative analysis of the key recovery attack.While Laine and Lauter’s analysis gives explicit information about the effective approximation factor in the LLL algorithm and Babai’s nearest plane method, our analysis is useful to estimate which LWE instances can be solved by the key recovery attack. Furthermore, our analysis enables one to determine a successful range of the attack with practical lattice reduction such as the BKZ algorithm.
UR - http://www.scopus.com/inward/record.url?scp=84987986863&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84987986863&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-44524-3_10
DO - 10.1007/978-3-319-44524-3_10
M3 - Conference contribution
AN - SCOPUS:84987986863
SN - 9783319445236
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 164
EP - 181
BT - Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings
A2 - Yoshioka, Katsunari
A2 - Ogawa, Kazuto
PB - Springer Verlag
T2 - 11th International Workshop on Security on Advances in Information and Computer Security, IWSEC 2016
Y2 - 12 September 2016 through 14 September 2016
ER -