Lattice signatures without trapdoors

Vadim Lyubashevsky 1
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 : We provide an alternative method for constructing lattice-based digital signatures which does not use the "hash-and-sign" methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle model, based on the worst-case hardness of the Õ(n 1.5)-SIVP problem in general lattices. The secret key, public key, and the signature size of our scheme are smaller than in all previous instantiations of the hash-and-sign signature, and our signing algorithm is also quite simple, requiring just a few matrix-vector multiplications and rejection samplings. We then also show that by slightly changing the parameters, one can get even more efficient signatures that are based on the hardness of the Learning With Errors problem. Our construction naturally transfers to the ring setting, where the size of the public and secret keys can be significantly shrunk, which results in the most practical to-date provably secure signature scheme based on lattices.
Type de document :
Communication dans un congrès
David Pointcheval and Patrick Schaumont. EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012., Apr 2012, Cambridge, United Kingdom. Springer, 7237, pp.738-755, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29011-4_43〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00864308
Contributeur : Vadim Lyubashevsky <>
Soumis le : vendredi 20 septembre 2013 - 17:40:01
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Vadim Lyubashevsky. Lattice signatures without trapdoors. David Pointcheval and Patrick Schaumont. EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012., Apr 2012, Cambridge, United Kingdom. Springer, 7237, pp.738-755, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-29011-4_43〉. 〈hal-00864308〉

Partager

Métriques

Consultations de la notice

1790