Locality sensitive hashing with extended differential privacy

DOI10.1007/978-3-030-88428-4_28MaRDI QIDQ2148769zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 24 June 2022

Full work available at URL https://arxiv.org/abs/2010.09393

zbMATH Keywords

angular distanceextended differential privacylocal differential privacylocality-sensitive hashing

Mathematics Subject Classification ID

Privacy of data (68P27)

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.

Recommendations

• A locality sensitive hashing filter for encrypted vector databases
• On the Distortion of Locality Sensitive Hashing
• Tight lower bounds for data-dependent locality-sensitive hashing
• Beyond locality-sensitive hashing
• The distortion of locality sensitive hashing
• Locality-sensitive hashing scheme based on p-stable distributions
• Lower Bounds on Locality Sensitive Hashing
• scientific article; zbMATH DE number 5506204
• Extremal mechanisms for local differential privacy
• Locality-sensitive hashing without false negatives

Cites work

• Approximate nearest neighbor search in high dimensions
• Differential Privacy
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 7014213 (Why is no real title available?)
• Local obfuscation mechanisms for hiding probability distributions
• Locality-sensitive hashing scheme based on p-stable distributions
• Min-wise independent permutations
• Processing text for privacy: an information flow perspective
• Randomized response: a survey technique for eliminating evasive answer bias
• Similarity estimation techniques from rounding algorithms
• Theory of Cryptography

Cited in

(1)

• scientific article; zbMATH DE number 7233838 (Why is no real title available?)

Describes a project that uses

Uses Software

• MovieLens
• RAPPOR
• FALCONN
• PrivateLR

This page was built for publication: Locality sensitive hashing with extended differential privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2148769)