Welcome to the resource topic for 2022/902
Title:
MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably
Authors: Bar Alon, Moni Naor, Eran Omri, and Uri Stemmer
Abstract:In the current digital world, large organizations (sometimes referred to as tech giants) provide service to extremely large numbers of users. The service provider is often interested in computing various data analyses over the private data of its users, which in turn have their incentives to cooperate, but do not necessarily trust the service provider. In this work, we introduce the \emph{Gulliver multi-party computation model} (GMPC) to realistically capture the above scenario. The GMPC model considers a single highly powerful party, called the {\em server} or {\em Gulliver}, that is connected to n users over a star topology network (alternatively formulated as a full network, where the server can block any message). The users are significantly less powerful than the server, and, in particular, should have both computation and communication complexities that are polylogarithmic in n. Protocols in the GMPC model should be secure against malicious adversaries that may corrupt a subset of the users and/or the server. Designing protocols in the GMPC model is a delicate task, since users can only hold information about \operatorname{polylog}(n) other users (and, in particular, can only communicate with \operatorname{polylog}(n) other users). In addition, the server can block any message between any pair of honest parties. Thus, reaching an agreement becomes a challenging task. Nevertheless, we design generic protocols in the GMPC model, assuming that at most \alpha<1/6 fraction of the users may be corrupted (in addition to the server). Our main contribution is a variant of Feige’s committee election protocol [FOCS 1999] that is secure in the GMPC model. Given this tool we show: \begin{enumerate} \item Assuming fully homomorphic encryption (FHE), any computationally efficient function with O\left(n\cdot\operatorname{polylog}(n)\right)-size output can be securely computed in the GMPC model. \item Any function that can be computed by a circuit of O(\operatorname{polylog}(n)) depth, O\left(n\cdot\operatorname{polylog}(n)\right) size, and bounded fan-in and fan-out can be securely computed in the GMPC model {\em without assuming FHE}. \item In particular, {\em sorting} can be securely computed in the GMPC model without assuming FHE. This has important applications for the {\em shuffle model of differential privacy}, and resolves an open question of Bell et al. [CCS 2020]. \end{enumerate}
ePrint: https://eprint.iacr.org/2022/902
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 .