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

TY - GEN

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

AU - Reyzin, Leonid

AU - Smith, Adam

AU - Yakoubov, Sophia

N1 - Conference code: 7

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Obfuscation

KW - Secure computation

KW - Setup freeness

KW - Threshold encryption

UR - http://www.scopus.com/inward/record.url?scp=85111994532&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-78086-9_27

DO - 10.1007/978-3-030-78086-9_27

M3 - Article in proceedings

SN - 978-3-030-78085-2

VL - 12716

T3 - Lecture Notes in Computer Science

SP - 361

EP - 378

BT - Cyber Security Cryptography and Machine Learning - 5th International Symposium, CSCML 2021, Proceedings

PB - Springer

T2 - 7th International Conference on Cryptology and Information Security in Latin America

Y2 - 6 October 2021 through 8 October 2021

ER -