Hardness of decision
(R)LWE for any modulus
Adeline Langlois and Damien Stehlé
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.
Download: pdf.
Homepage