Differentially Private Set Representations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909698172649472 |
|---|---|
| author | Patel, Sarvar Persiano, Giuseppe Seo, Joon Young Yeo, Kevin |
| author_facet | Patel, Sarvar Persiano, Giuseppe Seo, Joon Young Yeo, Kevin |
| contents | 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 ε\cdot \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 ε\cdot \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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16680 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differentially Private Set Representations Patel, Sarvar Persiano, Giuseppe Seo, Joon Young Yeo, Kevin Cryptography and Security Data Structures and Algorithms 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 ε\cdot \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 ε\cdot \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. |
| title | Differentially Private Set Representations |
| topic | Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.16680 |