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
-
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},
url = {https://eprint.iacr.org/2016/1153}
}
