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.
Category / Keywords: Ring-LWE, PLWE Original Publication (with major differences): IACR-EUROCRYPT-2018 Date: received 8 Feb 2018, last revised 12 Feb 2018 Contact author: damien stehle at gmail com, mirunarosca@gmail com, wallet alexandre@gmail com Available format(s): PDF | BibTeX Citation Version: 20180214:124428 (All versions of this report) Short URL: ia.cr/2018/170