Joint Encryption and Message-Efficient Secure Computation

This paper connects two areas of recent cryptographic research: secure distributed computation, and group-oriented cryptography. We construct a probabilistic public-key encryption scheme with the following properties: —It is easy to encrypt using the public keys of any subset of parties, such that it is hard to decrypt without the cooperation of every party in the subset.—It is easy for any private key holder to give a “witness” of its contribution to the decryption (e.g., for parallel decryption).—It is “blindable”: From an encrypted bit it is easy for anyone to compute a uniformly random encryption of the same bit.—It is “xor-homomorphic”: Prom two encrypted bits it is easy for anyone to compute an encryption of their xor.—It is “compact”: The size of an encryption does not depend on the number of participants.Using this joint encryption scheme as a tool, we show how to reduce the message complexity of secure computation versus a passive adversary (gossiping faults).