Cryptology ePrint Archive: Report 2016/1153

Attacks against search Poly-LWE

Momonari Kudo

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]