@inproceedings{
patel2024differentially,
title={Differentially Private Set Representations},
author={Sarvar Patel and Giuseppe Persiano and Joon Young Seo and Kevin Yeo},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=GQNvvQquO0}
}
We study the problem of differentially private (DP) mechanisms for representing
sets of size $k$ from a large universe.
Our first construction creates
$(\epsilon,\delta)$-DP representations with error probability of 
$1/(e^\epsilon + 1)$ using space at most $1.05 k \epsilon \cdot \log(e)$ bits where
the time to construct a representation is $O(k \log(1/\delta))$ while decoding time is $O(\log(1/\delta))$.
We also present a second algorithm for pure $\epsilon$-DP representations with the same error using space at most $k \epsilon \cdot \log(e)$ bits, but requiring large decoding times.
Our algorithms match the lower bounds on privacy-utility trade-offs (including constants but ignoring $\delta$ factors) and we also present a new space lower bound
matching our constructions up to small constant factors.
To obtain our results, we design a new approach embedding sets into random linear systems
deviating from most prior approaches that inject noise into non-private solutions.
Differentially Private Set Representations
Sarvar Patel Giuseppe Persiano Joon Young Seo Kevin Yeo