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.
Category / Keywords: Date: received 22 Mar 2022, last revised 23 Mar 2022 Contact author: matthieu rambaud at telecom-paris fr Available format(s): PDF | BibTeX Citation Version: 20220328:143212 (All versions of this report) Short URL: ia.cr/2022/378