Distributed Public-Key Cryptography from Weak Secrets

By Michel Abdalla, Xavier Boyen, Céline Chevalier, and David Pointcheval.

In Public Key Cryptography (PKC 2009), volume 5443 of Lecture Notes in Computer Science, pages 139-159. Springer, 2009.

Abstract

We introduce the notion of distributed password-based public-key cryptography, where a virtual high-entropy private key is implicitly defined as a concatenation of low-entropy passwords held in separate locations. The users can jointly perform private-key operations by exchanging messages over an arbitrary channel, based on their respective passwords, without ever sharing their passwords or reconstituting the key.

Focusing on the case of ElGamal encryption as an example, we start by formally defining ideal functionalities for distributed public-key generation and virtual private-key computation in the UC model. We then construct efficient protocols that securely realize them in either the RO model (for efficiency) or the CRS model (for elegance).

We conclude by showing that our distributed protocols generalize to a broad class of "discrete-log"-based public-key cryptosystems, which notably includes identity-based encryption. This opens the door to a powerful extension of IBE with a virtual PKG made of a group of people, each one memorizing a small portion of the master key.

Material

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

Reference

@InProceedings{Abdalla+Boyen+Chevalier+Pointcheval:PKC-2009:distributed,
  author = {Michel Abdalla and Xavier Boyen and C\'eline Chevalier and David Pointcheval},
  title = {Distributed Public-Key Cryptography from Weak Secrets},
  booktitle = {Public Key Cryptography---PKC 2009},
  series = {Lecture Notes in Computer Science},
  volume = {5443},
  pages = {139--159},
  publisher = {Berlin: Springer-Verlag},
  year = {2009},
  note = {Available at \url{http://www.cs.stanford.edu/~xb/pkc09/}}
}