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

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 Gulliver multi-party computation model (GMPC) to realistically capture the above scenario. The GMPC model considers a single highly powerful party, called the server or 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 \(\textrm{polylog}(n)\) other users (and, in particular, can only communicate with \(\textrm{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/8}\) 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: