Welcome to the resource topic for 2022/378
Title:
Share & Shrink: Ad-Hoc Threshold FHE with Short Ciphertexts and its Application to Almost-Asynchronous MPC
Authors: Antoine Urban, 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.
ePrint: https://eprint.iacr.org/2022/378
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .