Distribution Privacy Under Function Recoverability

Abstract

A user generates $n$ independent and identically distributed data random variables with a probability mass function that must be guarded from a querier. The querier must recover, with a prescribed accuracy, a given function of the data from each of $n$ independent and identically distributed user-devised query responses. The user chooses the data pmf and the random query responses to maximize distribution privacy as gauged by the divergence between the pmf and the querier’s best estimate of it based on the $n$ query responses. A general lower bound is provided for distribution privacy; and, for the case of binary-valued functions, upper and lower bounds that converge to said bound as $n$ grows. Explicit strategies for the user and querier are identified.