Differentially Private Selection from Secure Distributed Computing

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Abstract

Given a collection of vectors \boldsymbolx ^(1), \dots,\boldsymbolx ^(n) \in \0,1\ ^d, the selection problem asks to report the index of an "approximately largest'' entry in \boldsymbolx =\sum_j=1 ^n \boldsymbolx ^(j) . Selection abstracts a host of problems, for example: Recommendation of a popular item based on user feedback; releasing statistics on the most popular web sites; hyperparameter tuning and feature selection in machine learning. We study selection under differential privacy, where a released index guarantees privacy for individual vectors. Though selection can be solved with an excellent utility guarantee in the central model of differential privacy, the distributed setting where no single entity is trusted to aggregate the data lacks solutions. Specifically, strong privacy guarantees with high utility are offered in high trust settings, but not in low trust settings. For example, in the popular shuffle model of distributed differential privacy, there are strong lower bounds suggesting that the utility of the central model cannot be obtained. In this paper we design a protocol for differentially private selection in a trust setting similar to the shuffle model - -with the crucial difference that our protocol tolerates corrupted servers while maintaining privacy. Our protocol uses techniques from secure multi-party computation (MPC) to implement a protocol that: (i) has utility on par with the best mechanisms in the central model, (ii) scales to large, distributed collections of high-dimensional vectors, and (iii) uses k\geq 3 servers that collaborate to compute the result, where the differential privacy guarantee holds assuming an honest majority. Since general-purpose MPC techniques are not sufficiently scalable, we propose a novel application of integer secret sharing, and evaluate the utility and efficiency of our protocol both theoretically and empirically. Our protocol improves on previous work by Champion, shelat and Ullman (CCS '19) by significantly reducing the communication costs, demonstrating that large-scale differentially private selection with information-theoretical guarantees is feasible in a distributed setting.

Original languageEnglish
Title of host publicationWWW 2024 - Proceedings of the ACM Web Conference
Number of pages12
Place of publicationNew York
PublisherAssociation for Computing Machinery
Publication dateMay 2024
Pages1103-1114
ISBN (Electronic)9798400701719
DOIs
Publication statusPublished - May 2024
Event33rd ACM Web Conference, WWW 2024 - Singapore, Singapore
Duration: 13 May 202417 May 2024

Conference

Conference33rd ACM Web Conference, WWW 2024
Country/TerritorySingapore
CitySingapore
Period13/05/202417/05/2024
SponsorACM SIGWEB

Keywords

  • differential privacy
  • multi-party computation
  • selection, cryptography

Fingerprint

Dive into the research topics of 'Differentially Private Selection from Secure Distributed Computing'. Together they form a unique fingerprint.

Cite this