[Resource Topic] 2016/240: On Error Distributions in Ring-based LWE

Welcome to the resource topic for 2016/240

On Error Distributions in Ring-based LWE

Authors: Wouter Castryck, Ilia Iliashenko, Frederik Vercauteren


Since its introduction in 2010 by Lyubashevsky, Peikert and Regev, the Ring Learning With Errors problem (Ring-LWE) has become a popular building block for cryptographic primitives, due to its great versatility and its hardness proof consisting of a (quantum) reduction from ideal lattice problems. But for a given modulus q and degree n number field K, generating Ring-LWE samples can be perceived as cumbersome, because the secret keys have to be taken from the reduction mod q of a certain fractional ideal \mathcal{O}_K^\vee \subset K called the codifferent or `dual’, rather than from the ring of integers \mathcal{O}_K itself. This has led to various non-dual variants of Ring-LWE, in which one compensates for the non-duality by scaling up the errors. We give a comparison of these versions, and revisit some unfortunate choices that have been made in the recent literature, one of which is scaling up by |\Delta_K|^{1/2n} with \Delta_K the discriminant of K. As a main result, we provide for any \varepsilon > 0 a family of number fields K for which this variant of Ring-LWE can be broken easily as soon as the errors are scaled up by |\Delta_K|^{(1-\varepsilon)/n}.

ePrint: https://eprint.iacr.org/2016/240

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .