A Locally Differential Private Coding-Assisted Succinct Histogram Protocol

• URL: http://arxiv.org/abs/2506.17767v1
• Date: Sat, 21 Jun 2025 17:30:31 GMT
• Title: A Locally Differential Private Coding-Assisted Succinct Histogram Protocol
• Authors: Hsuan-Po Liu, Hessam Mahdavifar,
• Abstract summary: A succinct histogram captures frequent items and their frequencies across clients.<n>Local differential privacy (LDP) has been utilized and shown promising results.<n>This work presents the first practical $(epsilon,delta)$-LDP protocol for constructing succinct histograms using error-correcting codes.
• Score: 20.802423208503082
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A succinct histogram captures frequent items and their frequencies across clients and has become increasingly important for large-scale, privacy-sensitive machine learning applications. To develop a rigorous framework to guarantee privacy for the succinct histogram problem, local differential privacy (LDP) has been utilized and shown promising results. To preserve data utility under LDP, which essentially works by intentionally adding noise to data, error-correcting codes naturally emerge as a promising tool for reliable information collection. This work presents the first practical $(\epsilon,\delta)$-LDP protocol for constructing succinct histograms using error-correcting codes. To this end, polar codes and their successive-cancellation list (SCL) decoding algorithms are leveraged as the underlying coding scheme. More specifically, our protocol introduces Gaussian-based perturbations to enable efficient soft decoding. Experiments demonstrate that our approach outperforms prior methods, particularly for items with low true frequencies, while maintaining similar frequency estimation accuracy.

Related papers

• Fault Tolerant Decoding of QLDPC-GKP Codes with Circuit Level Soft Information [3.075816977152969]
  We study the performance of QLDPC-GKPd codes under circuit-level noise.<n>We show that real-time soft information is critical for decoding under circuit-level noise.
  arXiv  Detail & Related papers  (2025-05-09T19:11:36Z)
• Threshold Selection for Iterative Decoding of $(v,w)$-regular Binary Codes [84.0257274213152]
  Iterative bit flipping decoders are an efficient choice for sparse $(v,w)$-regular codes.<n>We propose concrete criteria for threshold determination, backed by a closed form model.
  arXiv  Detail & Related papers  (2025-01-23T17:38:22Z)
• When Focus Enhances Utility: Target Range LDP Frequency Estimation and Unknown Item Discovery [7.746385592375338]
  Local Differential Privacy protocols have been successfully deployed in real-world scenarios by tech companies like Google, Apple, and Microsoft.<n>We propose a Generalized Count Mean Sketch protocol that captures many existing frequency estimation protocols.<n>We present a novel protocol for collecting data within unknown domain, as our frequency estimation protocols only work effectively with known data domain.
  arXiv  Detail & Related papers  (2024-12-23T05:50:11Z)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  Low-Density Parity-Check (LDPC) codes possess several advantages over other families of codes. The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
  arXiv  Detail & Related papers  (2024-06-09T12:08:56Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• PEOPL: Characterizing Privately Encoded Open Datasets with Public Labels [59.66777287810985]
  We introduce information-theoretic scores for privacy and utility, which quantify the average performance of an unfaithful user. We then theoretically characterize primitives in building families of encoding schemes that motivate the use of random deep neural networks.
  arXiv  Detail & Related papers  (2023-03-31T18:03:53Z)
• Composably secure data processing for Gaussian-modulated continuous variable quantum key distribution [58.720142291102135]
  Continuous-variable quantum key distribution (QKD) employs the quadratures of a bosonic mode to establish a secret key between two remote parties. We consider a protocol with homodyne detection in the general setting of composable finite-size security. In particular, we analyze the high signal-to-noise regime which requires the use of high-rate (non-binary) low-density parity check codes.
  arXiv  Detail & Related papers  (2021-03-30T18:02:55Z)
• Lossless Compression of Efficient Private Local Randomizers [55.657133416044104]
  Locally Differentially Private (LDP) Reports are commonly used for collection of statistics and machine learning in the federated setting. In many cases the best known LDP algorithms require sending prohibitively large messages from the client device to the server. This has led to significant efforts on reducing the communication cost of LDP algorithms.
  arXiv  Detail & Related papers  (2021-02-24T07:04:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.