VPrivKV: Verifiable Local Differential Privacy for Key-Value Data

Local Differential Privacy (LDP) enables privacy-preserving data analytics without requiring a trusted aggregator and has attracted significant attention from both academia and industry. For key–value data, PrivKV has been proposed to support frequency and mean estimation under LDP. In PrivKV, the user first samples a key uniformly at random and applies a randomization mechanism to perturb the corresponding value. However, since both Sample and Perturb steps are conducted locally, PrivKV is susceptible to output poisoning attacks, where malicious users bypass these steps and submit crafted data, making the aggregation result biased. To address this vulnerability, we propose VPrivKV, a verifiable LDP protocol designed to defend against output poisoning attacks. VPrivKV enables users and the aggregator to jointly perform the sampling step using a coin-flipping protocol, while the perturbation is enforced through an interactive and verifiable mechanism. Furthermore, we propose an enhanced version of VPrivKV that integrates zero-knowledge proofs to prevent the adversary from forging the discretized value to suppress non-target keys, thereby further enhancing robustness. We theoretically analyze the privacy and robustness of the proposed protocols and conduct numerical simulations to demonstrate their effectiveness in defending against output poisoning attacks.