Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings
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 \(\mathbb {Z}_q[\mathbf{x}]/\lang
- PDF / 373,660 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 199 Views
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 Zq [x]/f . 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]/f . These reductions, however, do not give us an indication as to the effect that the polynomial f , 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 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]/f for every f . 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 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]/xn + 1.
1
Introduction
One of the attractive features of lattice cryptography is that one can construct cryptographic primitives whose security is based on the hardness of worst-case lattice problems [Ajt96]. More concretely, average-case problems such as SIS and LWE are defined in such a way that an adversary who is able to solve these problems could then be used to find short vectors in any lattice. While V. Lyubashevsky—Supported by the SNSF ERC Transfer Grant CRETP2-166734 – FELICITY. c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part II, LNCS 10032, pp. 196–214, 2016. DOI: 10.1007/978-3-662-53890-6 7
Digital Signatures Based on the Hardness of Ideal Lattice Problems
197
the worst-case to average-case reductions do not help us figure out the exact parameter settings that make SIS and LWE hard, they definitely deserve the credit for leading researchers to the right definitions of these problems. Recent years have seen numerous cryptographic protocols constructed based on SIS and LWE. These schemes, however, are not particularly efficient because ˜ 2) SIS and LWE inherently give rise to key sizes and/or outputs which are O(λ in the security parameter λ. For this reason, almost all of the practical latticebased constructions are built upon the average-case
Data Loading...
