Paper 2016/796
Digital Signatures Based on the Hardness of Ideal Lattice Problems in all Rings
Vadim Lyubashevsky
Abstract
Many practical latticebased schemes are built upon the RingSIS or RingLWE problems, which are problems that are based on the presumed difficulty of finding lowweight 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 averagecase or worstcase problems. \\ As of today, there haven't been any weaknesses found in RingSIS or RingLWE problems when one uses an $f(x)$ which leads to a meaningful worstcase to averagecase 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 RingSIS and RingLWE than other rings. A more ideal scenario would therefore be if there would be an averagecase 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 RingSIS problem which is as hard to break as worstcase 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)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in ASIACRYPT 2016
 Keywords
 latticeideal latticeRingSISdigital signatures
 Contact author(s)
 vadim lyubash @ gmail com
 History
 20160820: received
 Short URL
 https://ia.cr/2016/796
 License

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} }