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
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
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.
Document type :
Conference papers
OPODIS, Dec 2011, Toulouse, France. Springer-Verlag Berlin Heidelberg, 7109, pp.357 - 377, 2011, LNCS
Liste complète des métadonnées


https://hal.inria.fr/hal-00646831
Contributor : Mohammad Alaggan <>
Submitted on : Monday, September 24, 2012 - 5:27:41 PM
Last modification on : Wednesday, August 2, 2017 - 10:06:26 AM
Document(s) archivé(s) le : Tuesday, December 13, 2016 - 6:45:30 PM

File

opodis_AGK11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00646831, version 1

Citation

Mohammad Alaggan, Sébastien Gambs, Anne-Marie Kermarrec. Private Similarity Computation in Distributed Systems: from Cryptography to Differential Privacy. OPODIS, Dec 2011, Toulouse, France. Springer-Verlag Berlin Heidelberg, 7109, pp.357 - 377, 2011, LNCS. <hal-00646831>

Share

Metrics

Record views

714

Document downloads

640