Paper 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Ring-LWEPoly-LWEfinite field
Contact author(s)
m-kudo @ math kyushu-u ac jp
History
2016-12-21: received
Short URL
https://ia.cr/2016/1153
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1153,
      author = {Momonari Kudo},
      title = {Attacks against search Poly-LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1153},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1153}},
      url = {https://eprint.iacr.org/2016/1153}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.