Skip to Main content Skip to Navigation
Conference papers

Private Similarity Computation in Distributed Systems: from Cryptography to Differential Privacy

Mohammad Alaggan 1, * Sébastien Gambs 2 Anne-Marie Kermarrec 1
* Corresponding author
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
2 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : In this paper, we address the problem of computing the similarity between two users (according to their profiles) while preserving their privacy in a fully decentralized system and for the passive adversary model. First, we introduce a two-party protocol for privately computing a threshold version of the similarity and apply it to well-known similarity measures such as the scalar product and the cosine similarity. The output of this protocol is only one bit of information telling whether or not two users are similar beyond a predetermined threshold. Afterwards, we explore the computation of the exact and threshold similarity within the context of differential privacy. Differential privacy is a recent notion developed within the field of private data analysis guaranteeing that an adversary that observes the output of the differentially private mechanism, will only gain a negligible advantage (up to a privacy parameter) from the presence (or absence) of a particular item in the profile of a user. This provides a strong privacy guarantee that holds independently of the auxiliary knowledge that the adversary might have. More specifically, we design several differentially private variants of the exact and threshold protocols that rely on the addition of random noise tailored to the sensitivity of the considered similarity measure. We also analyze their complexity as well as their impact on the utility of the resulting similarity measure. Finally, we provide experimental results validating the effectiveness of the proposed approach on real datasets.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Mohammad Alaggan Connect in order to contact the contributor
Submitted on : Monday, September 24, 2012 - 5:27:41 PM
Last modification on : Thursday, January 20, 2022 - 4:20:10 PM
Long-term archiving on: : Tuesday, December 13, 2016 - 6:45:30 PM


Files produced by the author(s)


  • HAL Id : hal-00646831, version 1


Mohammad Alaggan, Sébastien Gambs, Anne-Marie Kermarrec. Private Similarity Computation in Distributed Systems: from Cryptography to Differential Privacy. OPODIS, Dec 2011, Toulouse, France. pp.357 - 377. ⟨hal-00646831⟩



Les métriques sont temporairement indisponibles