Paper 2016/240

On Error Distributions in Ring-based LWE

Wouter Castryck, Ilia Iliashenko, and Frederik Vercauteren

Abstract

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 $$ with $$ the discriminant of $$. As a main result, we provide for any $$ a family of number fields $$ for which this variant of Ring-LWE can be broken easily as soon as the errors are scaled up by $$.