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

Mohammad Alaggan 1, * Sébastien Gambs 2 Anne-Marie Kermarrec 1
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
OPODIS, Dec 2011, Toulouse, France. Springer-Verlag Berlin Heidelberg, 7109, pp.357 - 377, 2011, LNCS
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00646831
Contributeur : Mohammad Alaggan <>
Soumis le : lundi 24 septembre 2012 - 17:27:41
Dernière modification le : mardi 16 janvier 2018 - 15:54:19
Document(s) archivé(s) le : mardi 13 décembre 2016 - 18:45:30

Fichier

opodis_AGK11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

795

Téléchargements de fichiers

680