**Hardness of decision (R)LWE for any modulus**

*Adeline Langlois and Damien Stehle*

**Abstract: **The decision Learning With Errors problem has proven an
extremely flexible foundation for devising provably secure
cryptographic primitives. LWE can be expressed in terms of linear
algebra over Z/qZ. This modulus q is the subject of study of
the present work. When q is prime and small, or when it is
exponential and composite with small factors, LWE is known to be at
least as hard as standard worst-case problems over euclidean
lattices (sometimes using quantum reductions). The Ring Learning
With Errors problem is a structured variant of LWE allowing for more
compact keys and more efficient primitives. It is known to be at
least as hard as standard worst-case problems restricted to
so-called ideal lattices, but under even more restrictive arithmetic
conditions on q.

In this work, we prove that the arithmetic form of the modulus q is irrelevant to the computational hardness of LWE and RLWE. More precisely, we show that these problems are at least as hard as standard worst-case problems on lattices, under the unique condition that q is of polynomial bit-size. This result is most useful for adapting LWE-based cryptographic constructions to the RLWE setting. Among others, this allows us to derive the first Identity-Based Encryption scheme of quasi-optimal performance proven secure under standard worst-case lattice assumptions, in the standard model. Other applications include authentication, functional encryption and traitor tracing.

**Category / Keywords: **public-key cryptography /

**Date: **received 23 Feb 2012, last revised 29 Jun 2012, withdrawn 5 Nov 2012

**Contact author: **damien stehle at ens-lyon fr

**Available format(s): **(-- withdrawn --)

**Note: **An improved article is in the works.
Final and stronger results will be published in a paper titled
"Classical hardness of Learning with Errors"
with Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev and Damien Stehle

**Version: **20121105:131302 (All versions of this report)

**Short URL: **ia.cr/2012/091

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]