Cryptology ePrint Archive: Report 2012/091

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 formats: (-- 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)

Discussion forum: Show discussion | Start new discussion