## תקציר

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 polylog(n) other users (and, in particular, can only communicate with 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 α<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: Assuming fully homomorphic encryption (FHE), any computationally efficient function with On·polylog(n)-size output can be securely computed in the GMPC model.Any function that can be computed by a circuit of O(polylog(n)) depth, On·polylog(n) size, and bounded fan-in and fan-out can be securely computed in the GMPC model assuming vector commitment schemes (without assuming FHE).In particular, sorting can be securely computed in the GMPC model assuming vector commitment schemes. This has important applications for the shuffle model of differential privacy, and resolves an open question of Bell et al. [CCS 2020]. Assuming fully homomorphic encryption (FHE), any computationally efficient function with On·polylog(n)-size output can be securely computed in the GMPC model. Any function that can be computed by a circuit of O(polylog(n)) depth, On·polylog(n) size, and bounded fan-in and fan-out can be securely computed in the GMPC model assuming vector commitment schemes (without assuming FHE). In particular, sorting can be securely computed in the GMPC model assuming vector commitment schemes. This has important applications for the shuffle model of differential privacy, and resolves an open question of Bell et al. [CCS 2020].

שפה מקורית | אנגלית |
---|---|

כותר פרסום המארח | Advances in Cryptology – CRYPTO 2024 - 44th Annual International Cryptology Conference, Proceedings |

עורכים | Leonid Reyzin, Douglas Stebila |

מוציא לאור | Springer Science and Business Media Deutschland GmbH |

עמודים | 74-108 |

מספר עמודים | 35 |

מסת"ב (מודפס) | 9783031683961 |

מזהי עצם דיגיטלי (DOIs) | |

סטטוס פרסום | פורסם - 2024 |

אירוע | 44th Annual International Cryptology Conference, CRYPTO 2024 - Santa Barbara, ארצות הברית משך הזמן: 18 אוג׳ 2024 → 22 אוג׳ 2024 |

### סדרות פרסומים

שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

כרך | 14927 LNCS |

ISSN (מודפס) | 0302-9743 |

ISSN (אלקטרוני) | 1611-3349 |

### כנס

כנס | 44th Annual International Cryptology Conference, CRYPTO 2024 |
---|---|

מדינה/אזור | ארצות הברית |

עיר | Santa Barbara |

תקופה | 18/08/24 → 22/08/24 |