Paper 2023/894

Differentially Private Selection from Secure Distributed Computing

Ivan Damgård
Hannah Keller, Aarhus University
Boel Nelson, University of Copenhagen
Claudio Orlandi, Aarhus University
Rasmus Pagh, University of Copenhagen

Given a collection of vectors $\mathbf{x}^{(1)},\dots,\mathbf{x}^{(n)} \in \{0,1\}^d$, the selection problem asks to report the index of an "approximately largest" entry in $\mathbf{x}=\sum_{j=1}^n \mathbf{x}^{(j)}$. Selection abstracts a host of problems; in machine learning it can be used for hyperparameter tuning, feature selection, or to model empirical risk minimization. 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 is the first to demonstrate that large-scale differentially private selection is possible in a distributed setting.

Available format(s)
Cryptographic protocols
Publication info
multi-party computationdifferential privacy
Contact author(s)
ivan @ cs au dk
hkeller @ cs au dk
bn @ di ku dk
orlandi @ cs au dk
pagh @ di ku dk
2023-06-12: approved
2023-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivan Damgård and Hannah Keller and Boel Nelson and Claudio Orlandi and Rasmus Pagh},
      title = {Differentially Private Selection from Secure Distributed Computing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/894},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.