Differentially Private Selection from Secure Distributed Computing

TY - GEN

T1 - Differentially Private Selection from Secure Distributed Computing

AU - Damgård, Ivan

AU - Keller, Hannah

AU - Nelson, Boel

AU - Orlandi, Claudio

AU - Pagh, Rasmus

PY - 2024/5

Y1 - 2024/5

N2 - 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.

AB - 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.

KW - differential privacy

KW - multi-party computation

KW - selection, cryptography

UR - http://www.scopus.com/inward/record.url?scp=85194073204&partnerID=8YFLogxK

U2 - 10.1145/3589334.3645435

DO - 10.1145/3589334.3645435

M3 - Article in proceedings

AN - SCOPUS:85194073204

SP - 1103

EP - 1114

BT - WWW 2024 - Proceedings of the ACM Web Conference

A2 - Chua, Tat-Seng

A2 - Ngo, Chong-Wah

A2 - Kumar, Ravi

A2 - Lauw, Hady W.

A2 - Lee, Roy Ka-Wei

PB - Association for Computing Machinery

CY - New York

T2 - 33rd ACM Web Conference, WWW 2024

Y2 - 13 May 2024 through 17 May 2024

ER -