Paper 2018/997

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

Leonid Reyzin and Adam Smith and Sophia Yakoubov

Abstract

We explore large-scale fault-tolerant multiparty computation on a minimal communication graph. Our goal is to be able to privately aggregate data from thousands of users - for example, in order to obtain usage statistics from users' phones. To reflect typical phone deployments, we limit communication to the star graph (so that all users only talk to a single central server). To provide fault-tolerance, we require the computation to complete even if some users drop out mid-computation, which is inevitable if the computing devices are personally owned smartphones. Variants of this setting have been considered for the problem of secure aggregation by Chan et al. (Financial Cryptography 2012) and Bonawitz et al. (CCS 2017). We call this setting Large-scale One-server Vanishing-participants Efficient MPC (LOVE MPC). We show that LOVE MPC requires at least three message flows, and that a three-message protocol requires some setup (such as a PKI). We then build LOVE MPC with optimal round- and communication- complexity (assuming semi-honest participants and a deployed PKI), using homomorphic ad hoc threshold encryption (HATE). We build the first HATE scheme with constant-size ciphertexts (although the public key length is linear in the number of users). Unfortunately, this construction is merely a feasibility result, because it relies on indistinguishability obfuscation. We also construct more practical three- and five- message LOVE MPC in the PKI model for addition or multiplication. Unlike in the obfuscation-based construction, the per user message length in these protocols is linear in the number of users. However, the five-message protocol still has constant amortized message length, because only the first two messages are long, but they need to be exchanged only once (i.e., are input-independent and reusable) and thus can be viewed as setup.

Note: Replaced the diO with iO; minor other edits