Abstract
We study the problem of differentially private (DP) mechanisms for representing sets 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.05 k ε · log(e) bits where the time to construct a representation is O(k log(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 our lower bounds on privacy-utility trade-offs (including constants but ignoring δ 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.