Skip to yearly menu bar Skip to main content


Poster

Differentially Private Set Representations

Sarvar Patel · Giuseppe Persiano · Joon Young Seo · Kevin Yeo

West Ballroom A-D #6209
[ ]
[ Paper [ Poster [ OpenReview
Wed 11 Dec 11 a.m. PST — 2 p.m. PST

Abstract: We study the problem of differentially private (DP) mechanisms for representingsets of size k from a large universe.Our first construction creates(ϵ,δ)-DP representations with error probability of 1/(eϵ+1) using space at most 1.05kϵlog(e) bits wherethe time to construct a representation is O(klog(1/δ)) while decoding time is O(log(1/δ)).We also present a second algorithm for pure ϵ-DP representations with the same error using space at most kϵlog(e) bits, but requiring large decoding times.Our algorithms match the lower bounds on privacy-utility trade-offs (including constants but ignoring δ factors) and we also present a new space lower boundmatching our constructions up to small constant factors.To obtain our results, we design a new approach embedding sets into random linear systemsdeviating from most prior approaches that inject noise into non-private solutions.

Chat is not available.