Paper 2022/378

Share & Shrink: Ad-Hoc Threshold FHE with Short Ciphertexts and its Application to Almost-Asynchronous MPC

Antoine Urban and Matthieu Rambaud

Abstract

We consider protocols for secure multi-party computation (MPC) under honest majority, i.e., for $N=2t+1$ players of which $t$ are corrupt, that achieve {guaranteed output delivery} (GOD), and in {constant latency}, independently from the circuit and $N$. A generic approach to this problem requires at least $3$ consecutive broadcasts in the plain model without PKI. State-of-the-art protocols with $2$ consecutive broadcasts, namely [GLS, Crypto'15] and [BJMS, Asiacrypt'20], however, suffer from a large size of threshold homomorphic ciphertexts. We aim for more efficient protocols in $2$ broadcasts, that subsequently enjoy a {Responsive execution}, i.e., at the speed of the network. To achieve this goal, we design a new approach with short threshold fully homomorphic (FHE) ciphertexts, which in turn impacts the computational complexity. The main building block of our technique is a threshold encryption scheme which is Ad-Hoc, i.e., which only takes as parameter $N$ public keys independently generated, equipped with a threshold shrinking mechanism into threshold FHE ciphertexts. One ingredient of independent interest is a linear secret sharing over RLWE rings with arbitrary modulus. By contrast, previous threshold FHE required the modulus to be prime and at least as large as $N+1$. Another significant advantage of this approach is that it also allows an arbitrary number of lightweight {external input owners} to feed their inputs in the computation by simply encrypting them with the Ad-Hoc scheme, then go offline. We finally prove the impossibility of $1$-Broadcast-then-Asynchronous MPC for $N\leq 3t-4$, showing tightness of our $2$ broadcasts.