Locality Sensitive Hashing with Extended Differential Privacy
arXiv:2010.09393 · doi:10.1007/978-3-030-88428-4_28
Abstract
Extended differential privacy, a generalization of standard differential privacy (DP) using a general metric, has been widely studied to provide rigorous privacy guarantees while keeping high utility. However, existing works on extended DP are limited to few metrics, such as the Euclidean metric. Consequently, they have only a small number of applications, such as location-based services and document processing. In this paper, we propose a couple of mechanisms providing extended DP with a different metric: angular distance (or cosine distance). Our mechanisms are based on locality sensitive hashing (LSH), which can be applied to the angular distance and work well for personal data in a high-dimensional space. We theoretically analyze the privacy properties of our mechanisms, and prove extended DP for input data by taking into account that LSH preserves the original metric only approximately. We apply our mechanisms to friend matching based on high-dimensional personal data with angular distance in the local model, and evaluate our mechanisms using two real datasets. We show that LDP requires a very large privacy budget and that RAPPOR does not work in this application. Then we show that our mechanisms enable friend matching with high utility and rigorous privacy guarantees based on extended DP.
arXiv commentESORICS 2021 (the 26th European Symposium on Research in Computer Security)
References in corpus (10)
- RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
- Geo-Indistinguishability: Differential Privacy for Location-Based Systems
- Optimal Geo-Indistinguishable Mechanisms for Location Privacy
- Discrete Distribution Estimation under Local Privacy
- Practical and Optimal LSH for Angular Distance
- Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
- Mutual Information Optimally Local Private Discrete Distribution Estimation
- Local Obfuscation Mechanisms for Hiding Probability Distributions
- Metric-based local differential privacy for statistical applications
- On the Anonymization of Differentially Private Location Obfuscation