**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.

**Category / Keywords: **Differential Privacy

**Date: **received 9 Oct 2014, last revised 5 Nov 2014, withdrawn 1 Oct 2015

**Contact author: **jalaj upadhyay at uwaterloo ca

**Available format(s): **(-- withdrawn --)

**Note: **Comments are welcome.

**Version: **20151001:205511 (All versions of this report)

**Short URL: **ia.cr/2014/818

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]