Non-interactive (t, n)-Incidence Counting from Differentially Private Indicator Vectors

Abstract : We present a novel non-interactive (t,n)-incidence count estimation for indicator vectors ensuring Differential Privacy. Given one or two differentially private indicator vectors, estimating the distinct count of elements in each and their intersection cardinality (equivalently, their inner product) have been studied in the literature, along with other extensions for estimating the cardinality set intersection in case the elements are hashed prior to insertion. The core contribution behind all these studies was to address the problem of estimating the Hamming weight (the number of bits set to one) of a bit vector from its differentially private version, and in the case of inner product and set intersection, estimating the number of positions which are jointly set to one in both bit vectors. We develop the most general case of estimating the number of positions which are set to one in exactly t out of n bit vectors (this quantity is denoted the (t,n)-incidence count), given access only to the differentially private version of those bit vectors. This means that if each bit vector belongs to a different owner, each can locally sanitize their bit vector prior to sharing it, hence the non-interactive nature of our algorithm. Our main contribution is a novel algorithm that simultaneously estimates the (t,n)-incidence counts for all t in {0,...,n}. We provide upper and lower bounds to the estimation error. Our lower bound is achieved by generalizing the limit of two-party differential privacy into n-party differential privacy, which is a contribution of independent interest. In particular we prove a lower bound on the additive error that must be incurred by any n-wise inner product of n mutually differentially-private bit vectors. Our results are very general and are not limited to differentially private bit vectors. They should apply to a large class of sanitization mechanism of bit vectors which depend on flipping the bits with a constant probability. Some potential applications for our technique include physical mobility analytics, call-detail-record analysis, and similarity metrics computation.
Type de document :
Communication dans un congrès
3rd International Workshop on Security and Privacy Analytics (IWSPA 2017), Mar 2017, Scottsdale, United States. 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01485412
Contributeur : Mohammad Alaggan <>
Soumis le : mercredi 8 mars 2017 - 17:14:35
Dernière modification le : jeudi 15 juin 2017 - 09:09:13
Document(s) archivé(s) le : vendredi 9 juin 2017 - 14:03:29

Fichier

iwspa17-alaggan-HAL-PREPRINT.p...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01485412, version 1

Collections

Citation

Mohammad Alaggan, Mathieu Cunche, Marine Minier. Non-interactive (t, n)-Incidence Counting from Differentially Private Indicator Vectors. 3rd International Workshop on Security and Privacy Analytics (IWSPA 2017), Mar 2017, Scottsdale, United States. 2017. 〈hal-01485412〉

Partager

Métriques

Consultations de
la notice

456

Téléchargements du document

62