Paper 2018/997

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

Leonid Reyzin, Adam Smith, and Sophia Yakoubov


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

Available format(s)
Publication info
Published elsewhere. MINOR revision.Cyber Security Cryptology and Machine Learning (CSCML 2021)
MPCthreshold encryptionobfuscation
Contact author(s)
sophia yakoubov @ gmail com
2021-04-07: last of 3 revisions
2018-10-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Leonid Reyzin and Adam Smith and Sophia Yakoubov},
      title = {Turning HATE Into LOVE: Compact Homomorphic Ad Hoc Threshold Encryption for Scalable MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2018/997},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.