To protect privacy for data-collection-based services, local differential privacy (LDP) is widely adopted due to its rigorous theoretical bound on privacy loss.However, mistakes in complex theoretical analysis or subtle implementation errors may undermine its practical guarantee.To address this, auditing is crucial to confirm that LDP protocols truly protect user data.However, existing auditing methods, though, mainly target machine learning and federated learning tasks based on centralized differentially privacy (DP), with limited attention to LDP.Moreover, the few studies on LDP auditing focus solely on simple frequency estimation task for discrete data, leaving correlated key-value data -which requires both discrete frequency estimation for keys and continuous mean estimation for values -unexplored.To bridge this gap, we propose KV-Auditor, a framework for auditing LDP-based key-value estimation mechanisms by estimating their empirical privacy lower bounds.Rather than traditional LDP auditing methods that relies on binary output predictions, KV-Auditor estimates this lower bound by analyzing unbounded output distributions, supporting continuous data.Specifically, we classify state-of-the-art LDP key-value mechanisms into interactive and non-interactive types.For non-interactive mechanisms, we propose horizontal KV-Auditor for small domains with sufficient samples and vertical KV-Auditor for large domains with limited samples.For interactive mechanisms, we design a segmentation strategy to capture incremental privacy leakage across iterations.Finally, we perform extensive experiments to validate the effectiveness of our approach, offering insights for optimizing LDP-based key-value estimators. CCS Concepts• Security and privacy →

Answering range queries in the context of Local Differential Privacy (LDP) is a widely studied problem in Online Analytical Processing (OLAP). Existing LDP solutions all assume a uniform data distribution within each domain partition, which may not align with real-world scenarios where data distribution is varied, resulting in inaccurate estimates. To address this problem, we introduce PriPL-Tree, a novel data structure that combines hierarchical tree structures with piecewise linear (PL) functions to answer range queries for arbitrary distributions. PriPL-Tree precisely models the underlying data distribution with a few line segments, leading to more accurate results for range queries. Furthermore, we extend it to multi-dimensional cases with novel data-aware adaptive grids. These grids leverage the insights from marginal distributions obtained through PriPL-Trees to partition the grids adaptively, adapting the density of underlying distributions. Our extensive experiments on both real and synthetic datasets demonstrate the effectiveness and superiority of PriPL-Tree over state-of-the-art solutions in answering range queries across arbitrary data distributions.

Collecting and analyzing users' set-valued data with privacy-preserving is a common scenario in real life. However, the existing solutions in LDP are not efficient enough, where users perturbing their data locally introduces a large amount of noise. The shuffle model, which adds a shuffler in LDP to shuffle all perturbed values, can amplify privacy, then improve utility. Inspired by this, we study the frequency estimation and top-$k$frequent item estimation of set-valued data in the shuffle model. To solve the challenges of different item quantities of users and further improve the utility, we combine sampling and shuffling together, and propose theEncoding, Padding, Sampling, and Shufflingframework, i.e., EPS$^{2}$. Based on this framework, we propose three protocols for frequency estimation in different application scenarios, then assemble them into multi-phase protocols for the top-$k$frequent item estimation. Theoretically, we identify all three protocols gain dual privacy amplification from sampling and shuffling. And by setting the size of users' set to 1, we can extend this amplified bound to the single-valued frequency estimation scenario, producing a tighter privacy bound than existing works. Finally, we perform experiments on both synthetic and real-world datasets to demonstrate the effectiveness of our protocols.