Simple Lattice Trapdoor Sampling from a Broad Class of Distributions

Vadim Lyubashevsky 1, 2 Daniel Wichs 3, *
* Auteur correspondant
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 : At the center of many lattice-based constructions is an algorithm that samples a short vector s, satisfying [A|AR − HG]s = t mod q where A, AR, H, G are public matrices and R is a trapdoor. Although the algorithm crucially relies on the knowledge of the trapdoor R to perform this sampling efficiently, the distribution it outputs should be independent of R given the public values. We present a new, simple algorithm for performing this task. The main novelty of our sampler is that the distribution of s does not need to be Gaussian, whereas all previous works crucially used the properties of the Gaussian distribution to produce such an s. The advantage of using a non-Gaussian distribution is that we are able to avoid the high-precision arithmetic that is inherent in Gaussian sampling over arbitrary lattices. So while the norm of our output vector s is on the order of √ n to n-times larger (the representation length, though, is only a constant factor larger) than in the samplers of Gentry, Peikert, Vaikuntanathan (STOC 2008) and Micciancio, Peikert (EUROCRYPT 2012), the sampling itself can be done very efficiently. This provides a useful time/output trade-off for devices with constrained computing power. In addition, we believe that the conceptual simplicity and generality of our algorithm may lead to it finding other applications.
Type de document :
Communication dans un congrès
Public Key Cryptography 2015, Mar 2015, Gaithersburgh, United States. Springer Verlag, PKC 2015, LNCS (9020), 2015, 〈10.1007/978-3-662-46447-2_32〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01235177
Contributeur : Vadim Lyubashevsky <>
Soumis le : samedi 28 novembre 2015 - 18:29:13
Dernière modification le : jeudi 11 janvier 2018 - 06:22:10
Document(s) archivé(s) le : samedi 29 avril 2017 - 02:12:14

Fichier

unbalanced.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Vadim Lyubashevsky, Daniel Wichs. Simple Lattice Trapdoor Sampling from a Broad Class of Distributions. Public Key Cryptography 2015, Mar 2015, Gaithersburgh, United States. Springer Verlag, PKC 2015, LNCS (9020), 2015, 〈10.1007/978-3-662-46447-2_32〉. 〈hal-01235177〉

Partager

Métriques

Consultations de la notice

553

Téléchargements de fichiers

165