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
Documents
- Fulltext
Accepted author manuscript, 302 KB, PDF document
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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |
Publisher | SIAM |
Publication date | 2024 |
Pages | 1050-1066 |
DOIs | |
Publication status | Published - 2024 |
Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |
Conference
Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|
Land | United States |
By | Alexandria |
Periode | 07/01/2024 → 10/01/2024 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics |
Bibliographical note
Publisher Copyright:
Copyright © 2024 This paper is available under the CC-BY 4.0 license.
ID: 394381045