Ring-LWE in polynomial rings

Léo Ducas 1, 2 Alain Durmus 2
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : The Ring-LWE problem, introduced by Lyubashevsky, Peikert, and Regev (Eurocrypt 2010), has been steadily finding many uses in numerous cryptographic applications. Still, the Ring-LWE problem defined in [LPR10] involves the fractional ideal R ∨, the dual of the ring R , which is the source of many theoretical and implementation technicalities. Until now, getting rid of R ∨, 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 =ℤ[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 [LPR10] into an "easy-to-use" Ring-LWE setting (i.e. without the dual ring R ∨), 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.
Type de document :
Communication dans un congrès
Marc Fischlin; Johannes Buchmann; Mark Manulis. PKC 2012 - International Conference on Practice and Theory in Public Key Cryptography, May 2012, Darmstadt, Germany. Springer, LNCS, 7293, pp.34-51, Public Key Cryptography – PKC 2012 International Workshop. 〈10.1007/978-3-642-30057-8_3〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01111627
Contributeur : Brigitte Briot <>
Soumis le : vendredi 30 janvier 2015 - 16:36:23
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Léo Ducas, Alain Durmus. Ring-LWE in polynomial rings. Marc Fischlin; Johannes Buchmann; Mark Manulis. PKC 2012 - International Conference on Practice and Theory in Public Key Cryptography, May 2012, Darmstadt, Germany. Springer, LNCS, 7293, pp.34-51, Public Key Cryptography – PKC 2012 International Workshop. 〈10.1007/978-3-642-30057-8_3〉. 〈hal-01111627〉

Partager

Métriques

Consultations de la notice

105