Cryptology ePrint Archive: Report 2016/1153
Attacks against search Poly-LWE
Abstract: The Ring-LWE (RLWE) problem is expected to be a computationally-hard problem even with quantum algorithms. The Poly-LWE (PLWE) problem is closely related to the RLWE problem, and in practice a security base for various recently-proposed cryptosystems. In 2014, Eisentraeger et al. proposed attacks against the decision-variant of the PLWE problem (and in 2015, Elias et al. precisely described and extended their attacks to be applied for that of the RLWE problem). Their attacks against the decision-PLWE problem succeed with sufficiently high probability in polynomial time under certain assumptions, one of which is that the defining polynomial of the PLWE instance splits completely over the ground field.
In this paper, we present polynomial-time attacks against the search-variant of the PLWE problem. Our attacks are viewed as search-case variants of the previous attacks, but can deal with more general cases where the defining polynomial of the PLWE problem does not split completely over the ground field.
Category / Keywords: Ring-LWE, Poly-LWE, finite field
Date: received 15 Dec 2016, last revised 20 Dec 2016
Contact author: m-kudo at math kyushu-u ac jp
Available format(s): PDF | BibTeX Citation
Version: 20161221:152547 (All versions of this report)
Short URL: ia.cr/2016/1153
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]