×

Ring-LWE in polynomial rings. (English) Zbl 1290.94067

Fischlin, Marc (ed.) et al., Public key cryptography – PKC 2012. 15th international conference on practice and theory in public key cryptography, Darmstadt, Germany, May 21–23, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-30056-1/pbk). Lecture Notes in Computer Science 7293, 34-51 (2012).
Summary: The ring-LWE problem, introduced by V. Lyubashevsky et al. [Advances in cryptology – EUROCRYPT 2010. 29th annual international conference on the theory and applications of cryptographic techniques. Lect. Notes Comput. Sci. 6110, 1–23 (2010; Zbl 1279.94099)], has been steadily finding many uses in numerous cryptographic applications. Still, the ring-LWE problem defined in the cited paper involves the fractional ideal \(R^{ \vee }\), the dual of the ring \(R\), which is the source of many theoretical and implementation technicalities. Until now, getting rid of \(R^{\vee }\), required some relatively complex transformation that substantially increase the magnitude of the error polynomial and the practical complexity to sample it. It is only for rings \(R = \mathbb Z[X]/(X ^{n } + 1)\) where \(n\) a power of 2, that this transformation is simple and benign.
In this work we show that by applying a different, and much simpler transformation, one can transfer the results from the paper cited above into an “easy-to-use” ring-LWE \(setting (i.e.\) without the dual ring \(R ^{ \vee })\), with only a very slight increase in the magnitude of the noise coefficients. Additionally, we show that creating the correct noise distribution can also be simplified by generating a Gaussian distribution over a particular extension ring of \(R\), and then performing a reduction modulo \(f(X)\). In essence, our results show that one does not need to resort to using any algebraic structure that is more complicated than polynomial rings in order to fully utilize the hardness of the ring-LWE problem as a building block for cryptographic applications.
For the entire collection see [Zbl 1241.94004].

MSC:

94A60 Cryptography

Citations:

Zbl 1279.94099
PDFBibTeX XMLCite
Full Text: DOI