Paper 2016/796

Digital Signatures Based on the Hardness of Ideal Lattice Problems in all Rings

Vadim Lyubashevsky

Abstract

Many practical lattice-based schemes are built upon the Ring-SIS or Ring-LWE problems, which are problems that are based on the presumed difficulty of finding low-weight solutions to linear equations over polynomial rings $Z_q[x]/\langle f(x) \rangle$. Our belief in the asymptotic computational hardness of these problems rests in part on the fact that there are reduction showing that solving them is as hard as finding short vectors in all lattices that correspond to ideals of the polynomial ring $Z[x]/\langle f(x) \rangle$. These reductions, however, do not give us an indication as to the effect that the polynomial $f(x)$, which defines the ring, has on the average-case or worst-case problems. \\ As of today, there haven't been any weaknesses found in Ring-SIS or Ring-LWE problems when one uses an $f(x)$ which leads to a meaningful worst-case to average-case reduction, but there have been some recent algorithms for related problems that heavily use the algebraic structures of the underlying rings. It is thus conceivable that some rings could give rise to more difficult instances of Ring-SIS and Ring-LWE than other rings. A more ideal scenario would therefore be if there would be an average-case problem, allowing for efficient cryptographic constructions, that is based on the hardness of finding short vectors in ideals of $Z[x]/\langle f(x)\rangle$ for \emph{every} $f(x)$.\\ In this work, we show that the above may actually be possible. We construct a digital signature scheme based (in the random oracle model) on a simple adaptation of the Ring-SIS problem which is as hard to break as worst-case problems in every $f(x)$ whose degree is bounded by the parameters of the scheme. Up to constant factors, our scheme is as efficient as the highly practical schemes that work over the ring $Z[x]/\langle x^n+1\rangle$.