Back to search

University of Waterloo

Scaling Two-Party Differentially Private Selection

Abstract

dc:description.abstract

We consider the problem of differentially private (DP) selection in the two-party setting. This problem can be solved with excellent utility guarantee in the central setting, but the distributed case is much less studied. Existing solutions use secure multi-party computation (MPC) techniques to simulate computation in the central model, which are not sufficiently scalable to large candidate sets. This work provides a new protocol for two-party DP selection that achieves sublinear runtime in the MPC phase. Our design lets each party locally trim the candidate set before participating in an MPC protocol. Based on this heuristic, we provide two variations, one of which reveals each party’s trimmed candidate set and the other does not. We evaluate our method on public datasets based on review counts and location check-ins. The results demonstrate that the variant hiding the trimmed candidate sets outperforms the other variant in both utility and efficiency. Furthermore, our solution is able to offer competitive utility to the traditional solution at a significantly lower computation cost in lower privacy regimes.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ni, Haoyan

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/22969

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ni, Haoyan. Scaling Two-Party Differentially Private Selection. University of Waterloo, 2026. https://hdl.handle.net/10012/22969