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 …