Private Similarity Computation in Distributed Systems: from Cryptography to Differential Privacy - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

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

Résumé

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.
Fichier principal
Vignette du fichier
opodis_AGK11.pdf (378.72 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00646831 , version 1 (24-09-2012)

Identifiants

  • HAL Id : hal-00646831 , version 1

Citer

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⟩
369 Consultations
951 Téléchargements

Partager

Gmail Facebook X LinkedIn More