Worst-case to average-case
reductions for module lattices
Adeline Langlois and Damien Stehlé
Abstract: Most lattice-based cryptographic schemes are built upon the
assumed hardness of the Short Integer Solution (SIS) and Learning With
Errors (LWE) problems. Their efficiencies can be drastically improved
by switching the hardness assumptions to the more compact Ring-SIS and
Ring-LWE problems. However, this change of hardness assumptions comes
along with a possible security weakening: SIS and LWE are known to be
at least as hard as standard (worst-case) problems on euclidean
lattices, whereas Ring-SIS and Ring-LWE are only known to be as hard
as their restrictions to special classes of ideal lattices,
corresponding to ideals of some polynomial rings. In this work, we
define the Module-SIS and Module-LWE problems, which bridge SIS with
Ring-SIS, and LWE with Ring-LWE, respectively. We prove that these
average-case problems are at least as hard as standard lattice
problems restricted to module lattices (which themselves generalize
arbitrary and ideal lattices). As these new problems enlarge the
toolbox of the lattice-based cryptographer, they could prove useful
for designing new schemes. Importantly, the worst-case to average-case
reductions for the module problems are (qualitatively) sharp, in the
sense that there exist converse reductions. This property is not known
to hold in the context of Ring-SIS/Ring-LWE: Ideal lattice problems
could reveal easy without impacting the hardness of Ring-SIS/Ring-LWE.
Download: pdf.
Homepage