Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access. / Aumüller, Martin; Lebeda, Christian Janos; Pagh, Rasmus.
In: Journal of Privacy and Confidentiality, Vol. 12, No. 2, 2022.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access
AU - Aumüller, Martin
AU - Lebeda, Christian Janos
AU - Pagh, Rasmus
N1 - Publisher Copyright: © 2022, Cornell University. All rights reserved.
PY - 2022
Y1 - 2022
N2 - Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy. An ideal solution would require 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 showing that the constant factors on the main performance parameters are quite small and supporting practicality of the technique.
AB - Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy. An ideal solution would require 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 showing that the constant factors on the main performance parameters are quite small and supporting practicality of the technique.
KW - Algorithms
KW - differential privacy
KW - histograms
KW - sparse vectors
UR - http://www.scopus.com/inward/record.url?scp=85140973339&partnerID=8YFLogxK
U2 - 10.29012/jpc.809
DO - 10.29012/jpc.809
M3 - Journal article
AN - SCOPUS:85140973339
VL - 12
JO - Journal of Privacy and Confidentiality
JF - Journal of Privacy and Confidentiality
SN - 2575-8527
IS - 2
ER -
ID: 340691561