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

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'{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.