Paper 2022/902

MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably

Bar Alon, Ariel University
Moni Naor, Weizmann Institute of Science
Eran Omri, Ariel University
Uri Stemmer, Tel Aviv University, Google Research

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}

Available format(s)
Cryptographic protocols
Publication info
Contact author(s)
alonbar08 @ gmail com
moni naor @ weizmann ac il
omrier @ ariel ac il
u @ uri co il
2022-07-12: approved
2022-07-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bar Alon and Moni Naor and Eran Omri and Uri Stemmer},
      title = {MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably},
      howpublished = {Cryptology ePrint Archive, Paper 2022/902},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.