A Locally Differential Private Coding-Assisted Succinct Histogram Protocol
This addresses privacy-sensitive machine learning applications by providing a practical LDP protocol for histogram construction, though it appears incremental as it builds on existing LDP and coding techniques.
The paper tackles the problem of constructing succinct histograms under local differential privacy (LDP) by introducing a protocol that uses error-correcting codes, specifically polar codes with Gaussian perturbations, to improve data utility. Experiments show it outperforms prior methods, especially for low-frequency items, while maintaining similar accuracy.
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 $(ε,δ)$-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.