### Lossiness and Entropic Hardness for Ring-LWE

Zvika Brakerski and Nico Döttling

##### Abstract

The hardness of the Ring Learning with Errors problem (RLWE) is a central building block for efficiency-oriented lattice-based cryptography. Many applications use an entropic'' variant of the problem where the so-called secret'' is not distributed uniformly as prescribed but instead comes from some distribution with sufficient min-entropy. However, the hardness of the entropic variant has not been substantiated thus far. For standard LWE (not over rings) entropic results are known, using a lossiness approach'' but it was not known how to adapt this approach to the ring setting. In this work we present the first such results, where entropic security is established either under RLWE or under the Decisional Small Polynomial Ratio (DSPR) assumption which is a mild variant of the NTRU assumption. In the context of general entropic distributions, our results in the ring setting essentially match the known lower bounds (Bolboceanu et al., Asiacrypt 2019; Brakerski and Döttling, Eurocrypt 2020).

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2020
Keywords
Ring LWEEntropic Hardness
Contact author(s)
zvika brakerski @ weizmann ac il
History
Short URL
https://ia.cr/2020/1185

CC BY

BibTeX

@misc{cryptoeprint:2020/1185,
author = {Zvika Brakerski and Nico Döttling},
title = {Lossiness and Entropic Hardness for Ring-LWE},
howpublished = {Cryptology ePrint Archive, Paper 2020/1185},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1185}},
url = {https://eprint.iacr.org/2020/1185}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.