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
Note: Updated Section 4 with a simpler construction and proof.
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- Differential Privacy
- Contact author(s)
- jalaj upadhyay @ uwaterloo ca
- History
- 2014-11-05: last of 2 revisions
- 2014-09-19: received
- See all versions
- Short URL
- https://ia.cr/2014/730
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/730, author = {Jalaj Upadhyay}, title = {Differentially Private Linear Algebra in the Streaming Model}, howpublished = {Cryptology {ePrint} Archive, Paper 2014/730}, year = {2014}, url = {https://eprint.iacr.org/2014/730} }