Differentially Private Set Representations

2025/01/28 by Sarvar Patel, Patel, Sarvar, Giuseppe Persiano +5
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems

paper · pdf · doi:10.48550/arxiv.2501.16680

openalex publication_date 2025/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• A Joint Exponential Mechanism For Differentially Private Top-k
• Differentially Private Set Union
• The Privacy-preserving Padding Problem: Non-negative Mechanisms for Conservative Answers with Differential Privacy
• Differential Privacy on Finite Computers
• Private Algorithms Can Always Be Extended