We propose to extend the concept of private information retrieval by allowing for distortion in the retrieval process and relaxing the perfect privacy requirement at the same time. In particular, we study the tradeoff between download rate, distortio
n, and user privacy leakage, and show that in the limit of large file sizes this trade-off can be captured via a novel information-theoretical formulation for datasets with a known distribution. Moreover, for scenarios where the statistics of the dataset is unknown, we propose a new deep learning framework by leveraging a generative adversarial network approach, which allows the user to learn efficient schemes from the data itself, minimizing the download cost. We evaluate the performance of the scheme on a synthetic Gaussian dataset as well as on both the MNIST and CIFAR-10 datasets. For the MNIST dataset, the data-driven approach significantly outperforms a non-learning based scheme which combines source coding with multiple file download, while the CIFAR-10 performance is notably better.
In this work, we consider private monomial computation (PMC) for replicated noncolluding databases. In PMC, a user wishes to privately retrieve an arbitrary multivariate monomial from a candidate set of monomials in $f$ messages over a finite field $
mathbb F_q$, where $q=p^k$ is a power of a prime $p$ and $k ge 1$, replicated over $n$ databases. We derive the PMC capacity under a technical condition on $p$ and for asymptotically large $q$. The condition on $p$ is satisfied, e.g., for large enough $p$. Also, we present a novel PMC scheme for arbitrary $q$ that is capacity-achieving in the asymptotic case above. Moreover, we present formulas for the entropy of a multivariate monomial and for a set of monomials in uniformly distributed random variables over a finite field, which are used in the derivation of the capacity expression.
