### 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 $|\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}$.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Contact author(s)
wouter castryck @ gmail com
History
2016-05-31: last of 3 revisions
See all versions
Short URL
https://ia.cr/2016/240

CC BY

BibTeX

@misc{cryptoeprint:2016/240,
author = {Wouter Castryck and Ilia Iliashenko and Frederik Vercauteren},
title = {On Error Distributions in Ring-based LWE},
howpublished = {Cryptology ePrint Archive, Paper 2016/240},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/240}},
url = {https://eprint.iacr.org/2016/240}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.