Research map / Federated learning and privacy / Differential privacy

Differentially Private Set Representations

NeurIPS 2024 · Federated learning and privacy › Differential privacy · approach: Privacy accounting and mechanisms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes differentially private set representations by embedding the input set into random linear systems (random band and Vandermonde constructions), achieving error 1/(e^eps+1) with near-optimal space and matching lower bounds.

Problem

Releasing a differentially private representation of a small set drawn from a very large universe so that membership queries have low error while space scales with the set size rather than universe size.

Approach

Instead of perturbing a non-private sketch with noise, sample a subset of the input (exclusion probability p) and encode it as a random linear system via hashing; non-members satisfy their constraint only with probability 1/|F|, and the free variables randomization gives privacy with error exactly 1/(e^eps+1).

Key results

• Approximate-DP construction achieves error 1/(e^eps+1) with space 1.05 k eps log(e) bits and three hash functions, encoding O(k log(1/delta)) and decoding O(log(1/delta)).
• Pure-DP Vandermonde construction achieves epsilon-DP with error 1/(e^eps+1) and space k eps log(e) bits, encoding O(k log^2 k), decoding O(k).
• Matching utility lower bound alpha >= (1-delta)/(e^eps+1) and space lower bound Omega((1+delta/e^eps) k log(1/alpha)); experiments show DPSet has much lower error than ALP and DP Count Sketch at equal encoding sizes.

Measured effects reported in the paper

Surprising findings

• Error probability of 1/(e^eps+1) is exponentially smaller than the Omega(1/eps) per-entry error required for private histograms.
• Trivial random-hash mechanism achieves error 1/2 with (0,0)-DP and essentially no space.

Limitations

• Only sparse sets considered, not general sparse histograms with values.
• Assumes fully random hash functions; practical instantiations use cryptographic hashes and yield computational DP only under PRF assumptions.
• Decoding is slower than prior works (under 0.3 ms), and pure-DP construction has slow decoding O(k).

Experimental setup

Benchmarks: synthetic random 128-bit string sets with k in {2^12, 2^16, 2^20}

Metrics: error probability encoding time decoding time encoding size

Baselines: ALP DP Count Sketch randomized response Laplace mechanism histograms

Builds on: Bloom filter ALP mechanism DP count sketch Dietzfelbinger and Walzer random band retrieval Bienstock et al. random band analysis

Closest papers by meaning

• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.87)
• Universal Exact Compression of Differentially Private Mechanisms (NeurIPS 2024 · similarity 0.86)
• Perturb-and-Project: Differentially Private Similarities and Marginals (ICML 2024 · similarity 0.86)
• Privately Counting Partially Ordered Data (ICLR 2025 · similarity 0.86)
• Private Prediction via Shrinkage (NeurIPS 2026 · similarity 0.85)
• Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.85)