Paper 2014/730

Differentially Private Linear Algebra in the Streaming Model

Jalaj Upadhyay

Abstract

The focus of this paper is a systematic study of differential privacy on streaming data using sketch-based algorithms. Previous works, like Dwork {\it et al.} (ICS 2010, STOC 2010), explored random sampling based streaming algorithms. We work in the well studied streaming model of computation, where the database is stored in the form of a matrix and a curator can access the database row-wise or column-wise. Dwork {\it et al.} (STOC 2010) gave impossibility result for any non-trivial query on a streamed data with respect to the user level privacy. Therefore, in this paper, we work with the event level privacy. {We provide optimal, up to logarithmic factor, space data-structure in the streaming model for three basic linear algebraic tasks in a differentially private manner: matrix multiplication, linear regression, and low rank approximation, while incurring significantly less additive error}. The mechanisms for matrix multiplication and linear regression can be seen as the private analogues of known non-private algorithms, and have some similarities with Blocki {\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 2013) on the superficial level, but there are some subtle differences. For example, they perform an affine transformation to convert the private matrix in to a set of $\{\sqrt{w/n},1\}^n$ vectors for some appropriate $w$, while we perform a perturbation that raises the singular values of the private matrix. In order to get a streaming algorithm for low rank approximation, we have to reuse the random Gaussian matrix in a specific way. We prove that the resulting distribution also preserve differential privacy. We do not make any assumptions, like singular value separation, as made in the earlier works of Hardt and Roth (STOC 2013) and Kapralov and Talwar (SODA 2013). Further, we do not assume normalized row as in the work of Dwork {\it et al.} (STOC 2014). All our mechanisms, in the form presented, can also be computed in the distributed setting of Biemel, Nissim, and Omri (CRYPTO 2008).

Note: Updated Section 4 with a simpler construction and proof.