LHKV: A Key-Value Data Collection Mechanism Under Local Differential Privacy

Local differential privacy (LDP) is an emerging technology used to protect privacy. Users are required to locally perturb their raw data under the framework of LDP, before they are transmitted to the server. This technology can be applied to various data types, including key-value data. However, in existing LDP mechanisms for key-value data, it is difficult to balance data utility and communication costs, particularly when the domain of keys is large. In this paper we propose a local-hashing-based mechanism called LHKV for collecting key-value data. LHKV can maintain high utility and keep the end-to-end communication costs low. We provide theoretical proof that LHKV satisfies epsilon-LDP and analyze the variances of frequency and mean estimations. Moreover, we employ Fast Local Hashing to accelerate the aggregation and estimation process, which significantly reduces computation costs. We also conduct experiments to demonstrate that, in comparison with the existing mechanisms, LHKV can effectively reduce communication costs without sacrificing utility while ensuring the same LDP guarantees.