Practical “Signatures with Efficient Protocols” from Simple Assumptions

Benoît Libert 1, 2 Fabrice Mouhartem 1, 2 Thomas Peters 3 Moti Yung 4, 5
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 Groupe Crypto
ICTEAM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
Abstract : Digital signatures are perhaps the most important base for authentication and trust relationships in large scale systems. More specifically, various applications of signatures provide privacy and anonymity preserving mechanisms and protocols, and these, in turn, are becoming critical (due to the recently recognized need to protect individuals according to national rules and regulations). A specific type of signatures called " signatures with efficient protocols " , as introduced by Camenisch and Lysyanskaya (CL), efficiently accommodates various basic protocols and extensions like zero-knowledge proofs, signing committed messages, or re-randomizability. These are, in fact, typical operations associated with signatures used in typical anonymity and privacy-preserving scenarios. To date there are no " signatures with efficient protocols " which are based on simple assumptions and truly practical. These two properties assure us a robust primitive: First, simple assumptions are needed for ensuring that this basic primitive is mathematically robust and does not require special ad hoc assumptions that are more risky, imply less efficiency, are more tuned to the protocol itself, and are perhaps less trusted. In the other dimension, efficiency is a must given the anonymity applications of the protocol, since without proper level of efficiency the future adoption of the primitives is always questionable (in spite of their need). In this work, we present a new CL-type signature scheme that is re-randomizable under a simple, well-studied, and by now standard, assumption (SXDH). The signature is efficient (built on the recent QA-NIZK constructions), and is, by design, suitable to work in extended contexts that typify privacy settings (like anonymous credentials, group signature , and offline e-cash). We demonstrate its power by presenting practical protocols based on it.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Contributeur : Fabrice Mouhartem <>
Soumis le : vendredi 22 avril 2016 - 11:08:57
Dernière modification le : mardi 13 décembre 2016 - 15:41:57
Document(s) archivé(s) le : mardi 15 novembre 2016 - 09:50:14


Fichiers produits par l'(les) auteur(s)




Benoît Libert, Fabrice Mouhartem, Thomas Peters, Moti Yung. Practical “Signatures with Efficient Protocols” from Simple Assumptions. AsiaCCS 2016, May 2016, Xi'an, China. ACM, 2016, ACM. <>. <10.1145/2897845.2897898>. <hal-01303696v2>



Consultations de
la notice


Téléchargements du document