Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Shannon meets Gray : Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy. / Lolck, David Rasmussen; Pagh, Rasmus.
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024. p. 1050-1066.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Shannon meets Gray
T2 - 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
AU - Lolck, David Rasmussen
AU - Pagh, Rasmus
N1 - Publisher Copyright: Copyright © 2024 This paper is available under the CC-BY 4.0 license.
PY - 2024
Y1 - 2024
N2 - Integer data is typically made differentially private by adding noise from a Discrete Laplace (or Discrete Gaussian) distribution. We study the setting where differential privacy of a counting query is achieved using bit-wise randomized response, i.e., independent, random bit flips on the encoding of the query answer. Binary error-correcting codes transmitted through noisy channels with independent bit flips are well-studied in information theory. However, such codes are unsuitable for differential privacy since they have (by design) high sensitivity, i.e., neighbouring integers have encodings with a large Hamming distance. Gray codes show that it is possible to create an efficient sensitivity 1 encoding, but are also not suitable for differential privacy due to lack of noise-robustness. Our main result is that it is possible, with a constant rate code, to simultaneously achieve the sensitivity of Gray codes and the noise-robustness of error-correcting codes (down to the noise level required for differential privacy). An application of this new encoding of the integers is an asymptotically faster, space-optimal differentially private data structure for histograms.
AB - Integer data is typically made differentially private by adding noise from a Discrete Laplace (or Discrete Gaussian) distribution. We study the setting where differential privacy of a counting query is achieved using bit-wise randomized response, i.e., independent, random bit flips on the encoding of the query answer. Binary error-correcting codes transmitted through noisy channels with independent bit flips are well-studied in information theory. However, such codes are unsuitable for differential privacy since they have (by design) high sensitivity, i.e., neighbouring integers have encodings with a large Hamming distance. Gray codes show that it is possible to create an efficient sensitivity 1 encoding, but are also not suitable for differential privacy due to lack of noise-robustness. Our main result is that it is possible, with a constant rate code, to simultaneously achieve the sensitivity of Gray codes and the noise-robustness of error-correcting codes (down to the noise level required for differential privacy). An application of this new encoding of the integers is an asymptotically faster, space-optimal differentially private data structure for histograms.
U2 - 10.1137/1.9781611977912.40
DO - 10.1137/1.9781611977912.40
M3 - Article in proceedings
AN - SCOPUS:85183831665
SP - 1050
EP - 1066
BT - Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
PB - SIAM
Y2 - 7 January 2024 through 10 January 2024
ER -
ID: 394381045