Paper 2018/997

Turning HATE Into LOVE: Compact Homomorphic Ad Hoc Threshold Encryption for Scalable MPC

Leonid Reyzin, Adam Smith, and Sophia Yakoubov

Abstract

In a public-key threshold encryption scheme, the sender produces a single ciphertext, and any $t+1$ out of $n$ intended recipients can combine their partial decryptions to obtain the plaintext. Ad hoc threshold encryption (ATE) schemes require no correlated setup, enabling each party to simply generate its own key pair. In this paper, we initiate a systematic study of the possibilities and limitations of ad-hoc threshold encryption, and introduce a key application to scalable multiparty computation (MPC). Assuming indistinguishability obfuscation (iO), we construct the first ATE that is sender-compact - that is, with ciphertext length independent of $n$. This allows for succinct communication once public keys have been shared. We also show a basic lower bound on the extent of key sharing: every sender-compact scheme requires that recipients of a message know the public keys of other recipients in order to decrypt. We then demonstrate that threshold encryption that is ad hoc and homomorphic can be used to build efficient large-scale fault-tolerant multiparty computation (MPC) on a minimal (star) communication graph. We explore several homomorphic schemes, in particular obtaining one iO-based ATE scheme that is both sender-compact and homomorphic: each recipient can derive what they need for evaluation from a single short ciphertext. In the resulting MPC protocol, once the public keys have been distributed, all parties in the graph except for the central server send and receive only short messages, whose size is independent of the number of participants. Taken together, our results chart new possibilities for threshold encryption and raise intriguing open questions.

Note: minor edits