Paper 2018/170

On the Ring-LWE and Polynomial-LWE problems

Miruna Rosca, Damien Stehlé, and Alexandre Wallet

Abstract

The Ring Learning With Errors problem (RLWE) comes in various forms. Vanilla RLWE is the decision dual-RLWE variant, consisting in distinguishing from uniform a distribution depending on a secret belonging to the dual O_K^vee of the ring of integers O_K of a specified number field K. In primal-RLWE, the secret instead belongs to O_K. Both decision dual-RLWE and primal-RLWE enjoy search counterparts. Also widely used is (search/decision) Polynomial Learning With Errors (PLWE), which is not defined using a ring of integers O_K of a number field K but a polynomial ring ZZ[x]/f for a monic irreducible f in ZZ[x]. We show that there exist reductions between all of these six problems that incur limited parameter losses. More precisely: we prove that the (decision/search) dual to primal reduction from Lyubashevsky et al. [EUROCRYPT~2010] and Peikert [SCN~2016] can be implemented with a small error rate growth for all rings (the resulting reduction is non-uniform polynomial time); we extend it to polynomial-time reductions between (decision/search) primal RLWE and PLWE that work for a family of polynomials f that is exponentially large as a function of deg f (the resulting reduction is also non-uniform polynomial time); and we exploit the recent technique from Peikert et al. [STOC~2017] to obtain a search to decision reduction for RLWE for arbitrary number fields. The reductions incur error rate increases that depend on intrinsic quantities related to K and f.

Note: SVP to SIVP

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2018
Keywords
Ring-LWEPLWE
Contact author(s)
damien stehle @ gmail com
mirunarosca @ gmail com
wallet alexandre @ gmail com
History
2021-11-02: revised
2018-02-14: received
See all versions
Short URL
https://ia.cr/2018/170
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/170,
      author = {Miruna Rosca and Damien Stehlé and Alexandre Wallet},
      title = {On the Ring-LWE and Polynomial-LWE problems},
      howpublished = {Cryptology ePrint Archive, Paper 2018/170},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/170}},
      url = {https://eprint.iacr.org/2018/170}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.