Locality sensitive hashing with extended differential privacy

Natasha Fernandes, Yusuke Kawamoto*, Takao Murakami

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationComputer Security – ESORICS 2021
Subtitle of host publication26th European Symposium on Research in Computer Security Darmstadt, Germany, October 4–8, 2021, Proceedings, Part II
EditorsElisa Bertino, Haya Shulman, Michael Waidner
Place of PublicationCham, Switzerland
PublisherSpringer, Springer Nature
Number of pages21
ISBN (Electronic)9783030884284
ISBN (Print)9783030884277
Publication statusPublished - 2021
Event26th European Symposium on Research in Computer Security, ESORICS 2021 - Virtual, Online
Duration: 4 Oct 20218 Oct 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12973 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference26th European Symposium on Research in Computer Security, ESORICS 2021
CityVirtual, Online


  • Local differential privacy
  • Locality sensitive hashing
  • Angular distance
  • Extended differential privacy


Dive into the research topics of 'Locality sensitive hashing with extended differential privacy'. Together they form a unique fingerprint.

Cite this