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$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2016
Keywords
latticeideal latticeRing-SISdigital signatures
Contact author(s)
vadim lyubash @ gmail com
History
2016-08-20: received
Short URL
https://ia.cr/2016/796
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/796,
      author = {Vadim Lyubashevsky},
      title = {Digital Signatures Based on the Hardness of Ideal Lattice Problems in all Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2016/796},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/796}},
      url = {https://eprint.iacr.org/2016/796}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.