Paper 2014/818

Circulant Matrices and Differential Privacy

Jalaj Upadhyay

Abstract

This paper resolves an open problem raised by Blocki {\it et al.} (FOCS 2012), i.e., whether other variants of the Johnson-Lindenstrauss transform preserves differential privacy or not? We prove that a general class of random projection matrices that satisfies the Johnson-Lindenstrauss lemma also preserves differential privacy. This class of random projection matrices requires only $n$ Gaussian samples and $n$ Bernoulli trials and allows matrix-vector multiplication in $O(n \log n)$ time. In this respect, this work unconditionally improves the run time of Blocki {\it et al.} (FOCS 2012) without using the graph sparsification trick of Upadhyay (ASIACRYPT 2013). For the metric of measuring randomness, we stick to the norm used by earlier researchers who studied variants of the Johnson-Lindenstrauss transform and its applications, i.e., count the number of random samples made. In concise, we improve the sampling complexity by quadratic factor, and the run time of cut queries by an $O(n^{o(1)})$ factor and that of covariance queries by an $O(n^{0.38})$ factor. Our proof for both the privacy and utility guarantee uses several new ideas. In order to improve the dimension bound, we use some known results from the domain of statistical model selection. This makes our proof short and elegant, relying just on one basic concentration inequality. For the privacy proof, even though our mechanism closely resembles that of Blocki {\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013), we cannot use their proof idea. This is because the projection matrices we are interested in introduces non-trivial correlations between any two rows of the published matrix, and, therefore, we cannot invoke the composition theorem of Dwork, Rothblum and Vadhan (STOC 2009). We argue that the published matrix is not $r$-multivariate distribution; rather one matrix-variate distribution. We compute the distribution of the published matrix and then prove it preserves differential privacy.

Note: Comments are welcome.

Metadata
Available format(s)
-- withdrawn --
Publication info
Preprint. MINOR revision.
Keywords
Differential Privacy
Contact author(s)
jalaj upadhyay @ uwaterloo ca
History
2015-10-01: withdrawn
2014-10-12: received
See all versions
Short URL
https://ia.cr/2014/818
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.