Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access
Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy. An ideal solution would use space close to information-theoretical lower bounds, have an error distribution that depends optimally on the desired privacy level, and allow fast random...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Labor Dynamics Institute
2022-11-01
|
| Series: | The Journal of Privacy and Confidentiality |
| Subjects: | |
| Online Access: | https://journalprivacyconfidentiality.org/index.php/jpc/article/view/809 |
| _version_ | 1828099513529663488 |
|---|---|
| author | Christian Janos Lebeda Martin Aumüller Rasmus Pagh |
| author_facet | Christian Janos Lebeda Martin Aumüller Rasmus Pagh |
| author_sort | Christian Janos Lebeda |
| collection | DOAJ |
| description |
Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy.
An ideal solution would use space close to information-theoretical lower bounds, have an error distribution that depends optimally on the desired privacy level, and allow fast random access to entries in the vector.
However, existing approaches have only achieved two of these three goals.
In this paper we introduce the Approximate Laplace Projection (ALP) mechanism for approximating k-sparse vectors. This mechanism is shown to simultaneously have information-theoretically optimal space (up to constant factors), fast access to vector entries, and error of the same magnitude as the Laplace-mechanism applied to dense vectors.
A key new technique is a unary representation of small integers, which we show to be robust against ''randomized response'' noise. This representation is combined with hashing, in the spirit of Bloom filters, to obtain a space-efficient, differentially private representation.
Our theoretical performance bounds are complemented by simulations which show that the constant factors on the main performance parameters are quite small, suggesting practicality of the technique.
|
| first_indexed | 2024-04-11T08:16:07Z |
| format | Article |
| id | doaj.art-960ec368602e43f7a1bb92169f180d2e |
| institution | Directory Open Access Journal |
| issn | 2575-8527 |
| language | English |
| last_indexed | 2024-04-11T08:16:07Z |
| publishDate | 2022-11-01 |
| publisher | Labor Dynamics Institute |
| record_format | Article |
| series | The Journal of Privacy and Confidentiality |
| spelling | doaj.art-960ec368602e43f7a1bb92169f180d2e2022-12-22T04:35:09ZengLabor Dynamics InstituteThe Journal of Privacy and Confidentiality2575-85272022-11-01122Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast AccessChristian Janos Lebeda0Martin Aumüller1Rasmus Pagh2a:1:{s:5:"en_US";s:36:"BARC and IT University of Copenhagen";}IT University of CopenhagenBARC and University of Copenhagen Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy. An ideal solution would use space close to information-theoretical lower bounds, have an error distribution that depends optimally on the desired privacy level, and allow fast random access to entries in the vector. However, existing approaches have only achieved two of these three goals. In this paper we introduce the Approximate Laplace Projection (ALP) mechanism for approximating k-sparse vectors. This mechanism is shown to simultaneously have information-theoretically optimal space (up to constant factors), fast access to vector entries, and error of the same magnitude as the Laplace-mechanism applied to dense vectors. A key new technique is a unary representation of small integers, which we show to be robust against ''randomized response'' noise. This representation is combined with hashing, in the spirit of Bloom filters, to obtain a space-efficient, differentially private representation. Our theoretical performance bounds are complemented by simulations which show that the constant factors on the main performance parameters are quite small, suggesting practicality of the technique. https://journalprivacyconfidentiality.org/index.php/jpc/article/view/809AlgorithmsDifferential PrivacySparse VectorsHistograms |
| spellingShingle | Christian Janos Lebeda Martin Aumüller Rasmus Pagh Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access The Journal of Privacy and Confidentiality Algorithms Differential Privacy Sparse Vectors Histograms |
| title | Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access |
| title_full | Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access |
| title_fullStr | Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access |
| title_full_unstemmed | Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access |
| title_short | Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access |
| title_sort | representing sparse vectors with differential privacy low error optimal space and fast access |
| topic | Algorithms Differential Privacy Sparse Vectors Histograms |
| url | https://journalprivacyconfidentiality.org/index.php/jpc/article/view/809 |
| work_keys_str_mv | AT christianjanoslebeda representingsparsevectorswithdifferentialprivacylowerroroptimalspaceandfastaccess AT martinaumuller representingsparsevectorswithdifferentialprivacylowerroroptimalspaceandfastaccess AT rasmuspagh representingsparsevectorswithdifferentialprivacylowerroroptimalspaceandfastaccess |