Distributed Public-Key Cryptography from Weak Secrets

Michel Abdalla (1, 2) , Xavier Boyen (3) , Céline Chevalier (1, 2) , David Pointcheval (1, 2)

1 LIENS - Laboratoire d'informatique de l'école normale supérieure
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
3 Computer Science Department [Stanford]

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.

Domaines: Cryptographie et sécurité [cs.CR]

Michel Abdalla, Xavier Boyen, Céline Chevalier, David Pointcheval. Distributed Public-Key Cryptography from Weak Secrets. Conference on Practice and Theory in Public-Key Cryptography (PKC '09), 2009, Irvine, California, USA, United States. pp.139--159. ⟨inria-00419149⟩