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

Mohammad Alaggan (1, 2) , Mathieu Cunche (1, 2) , Marine Minier (3, 4)

1 CITI - CITI Centre of Innovation in Telecommunications and Integration of services
2 PRIVATICS - Privacy Models, Architectures and Tools for the Information Society
3 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
4 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms

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.

Mots clés: Differential Privacy; Randomized Response; Cardinality Set Intersection

Domaines: Cryptographie et sécurité [cs.CR]

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. ⟨hal-01485412⟩