Locality Sensitive Hashing with Extended Differential Privacy
| Autor: | Takao Murakami, Natasha Fernandes, Yusuke Kawamoto |
|---|---|
| Přispěvatelé: | Concurrency, Mobility and Transactions (COMETE), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Macquarie University [Sydney], National Institute of Advanced Industrial Science and Technology (AIST), National Institute of Advanced Industrial Science and Technology [Tokyo] (AIST), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Theoretical computer science Computer Science - Cryptography and Security Computer science Generalization Computer Science - Information Theory Document processing Machine Learning (cs.LG) Locality-sensitive hashing Computer Science - Information Retrieval [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] Computer Science - Databases Differential privacy Computer Science::Databases ComputingMilieux_MISCELLANEOUS Computer Science::Cryptography and Security Angular distance Information Theory (cs.IT) Small number [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Databases (cs.DB) Euclidean distance Metric (mathematics) Cryptography and Security (cs.CR) Information Retrieval (cs.IR) |
| Zdroj: | ESORICS 2021-26th European Symposium on Research in Computer Security ESORICS 2021-26th European Symposium on Research in Computer Security, Oct 2021, Darmstadt / Virtual, Germany ESORICS 2021-26th European Symposium on Research in Computer Security, Oct 2021, Darmstadt / Virtual, Germany. pp.563--583, ⟨10.1007/978-3-030-88428-4_28⟩ Computer Security – ESORICS 2021 ISBN: 9783030884277 ESORICS (2) |
| Popis: | 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. ESORICS 2021 (the 26th European Symposium on Research in Computer Security) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|