Tightly-Secure Signatures from Lossy Identification Schemes

Michel Abdalla 1 Pierre-Alain Fouque 2, 1, 3, 4 Vadim Lyubashevsky 3, 1, 4 Mehdi Tibouchi 5
1 LIENS - Laboratoire d'informatique de l'école normale supérieure
2 CELTIQUE - Software certification with semantic analysis
IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL, Inria Rennes – Bretagne Atlantique
3 ENS Paris - École normale supérieure - Paris
4 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
5 NTT Secure Platform Laboratories [Tokyo]
Abstract : In this paper we present three digital signature schemes with tight security reductions. Our first signature scheme is a particularly efficient version of the short exponent discrete log based scheme of Girault et al. (J. of Cryptology 2006). Our scheme has a tight reduction to the decisional Short Discrete Logarithm problem, while still maintaining the non-tight reduction to the computational version of the problem upon which the original scheme of Girault et al. is based. The second signature scheme we construct is a modification of the scheme of Lyubashevsky (Asiacrypt 2009) that is based on the worst-case hardness of the shortest vector problem in ideal lattices. And the third scheme is a very simple signature scheme that is based directly on the hardness of the Subset Sum problem. We also present a general transformation that converts what we term lossy identification schemes into signature schemes with tight security reductions. We believe that this greatly simplifies the task of constructing and proving the security of such signature schemes.
Keywords : Signature schemes Fiat-Shamir tight reductions
Type de document :
Communication dans un congrès
Advances in Cryptology - 2012, Apr 2012, Cambridge, United Kingdom. Springer, LNCS 7237, pp.19, 2012, EUROCRYPT 2012. 〈10.1007/978-3-642-29011-4_34〉
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01094318
Contributeur : Pierre-Alain Fouque <>
Soumis le : vendredi 12 décembre 2014 - 10:01:31
Dernière modification le : jeudi 15 novembre 2018 - 11:57:41
Document(s) archivé(s) le : vendredi 13 mars 2015 - 10:30:40

Fichier

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

Identifiants

Collections

INRIA | IRISA | ENS-PARIS | IRISA-D4 | PSL | UR1-UFR-ISTIC | UNIV-RENNES | INRIA-ROCQ

Citation

Michel Abdalla, Pierre-Alain Fouque, Vadim Lyubashevsky, Mehdi Tibouchi. Tightly-Secure Signatures from Lossy Identification Schemes. Advances in Cryptology - 2012, Apr 2012, Cambridge, United Kingdom. Springer, LNCS 7237, pp.19, 2012, EUROCRYPT 2012. 〈10.1007/978-3-642-29011-4_34〉. 〈hal-01094318〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

688

Téléchargements de fichiers

165

Contact


archive-ouverte@inria.fr