Strong Cryptography from Weak Secrets
Building Efficient PKE and IBE from Distributed Passwords

By Xavier Boyen, Céline Chevalier, Georg Fuchsbauer, and David Pointcheval.

In Progress in Cryptology (AFRICACRYPT 2010), volume 6055 of Lecture Notes in Computer Science, pages 297-315. Springer, 2010.

Abstract

Distributed-password public-key cryptography (DPwPKC) allows the members of a group of people, each one holding a small secret password only, to help a leader to perform the private operation, associated to a public-key cryptosystem. Abdalla et al. recently defined this tool [ABCP09], with a practical construction. Unfortunately, the latter applied to the ElGamal decryption only, and relied on the DDH assumption, excluding any recent pairing-based cryptosystems. In this paper, we extend their techniques to support, and exploit, pairing-based properties: we take advantage of pairing-friendly groups to obtain efficient (simulation-sound) zero-knowledge proofs, whose security relies on the Decisional Linear assumption. As a consequence, we provide efficient protocols, secure in the standard model, for ElGamal decryption as in [ABCP09], but also for Linear decryption, as well as extraction of several identity-based cryptosystems [BF01,BB04]. Furthermore, we strenghten their security model by suppressing the useless testPwd queries in the functionality.

Material

- published paper (PS) (PDF) (also accessible from the publisher) ©
- full version (PS) (PDF)
- presentation slides (HTML)

Reference

@InProceedings{Boyen+Chevalier+Fuchsbauer+Pointcheval:AFRICACRYPT-2010:strong,
  author = {Xavier Boyen and C\'eline Chevalier and Georg Fuchsbauer and David Pointcheval},
  title = {Strong Cryptography from Weak Secrets -- Building Efficient PKE and IBE from Distributed Passwords},
  booktitle = {Progress in Cryptology---AFRICACRYPT 2010},
  series = {Lecture Notes in Computer Science},
  volume = {6055},
  pages = {297--315},
  publisher = {Berlin: Springer-Verlag},
  year = {2010},
  note = {Available at \url{http://www.cs.stanford.edu/~xb/africacrypt10/}}
}