The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

被引:98
作者
Blocki, Jeremiah [1 ]
Blum, Avrim [1 ]
Datta, Anupam [1 ]
Sheffet, Or [1 ]
机构
[1] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA
来源
2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) | 2012年
关键词
NOISE;
D O I
10.1109/FOCS.2012.67
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
This paper proves that an "old dog", namely - the classical Johnson-Lindenstrauss transform, "performs new tricks" - it gives a novel way of preserving differential privacy. We show that if we take two databases, D and D', such that (i) D' - D is a rank-1 matrix of bounded norm and (ii) all singular values of D and D' are sufficiently large, then multiplying either D or D' with a vector of iid normal Gaussians yields two statistically close distributions in the sense of differential privacy. Furthermore, a small, deterministic and public alteration of the input is enough to assert that all singular values of D are large. We apply the Johnson-Lindenstrauss transform to the task of approximating cut-queries: the number of edges crossing a (S, S)-cut in a graph. We show that the JL transform allows us to publish a sanitized graph that preserves edge differential privacy (where two graphs are neighbors if they differ on a single edge) while adding only O(vertical bar S vertical bar/epsilon) random noise to any given query (w.h.p). Comparing the additive noise of our algorithm to existing algorithms for answering cut-queries in a differentially private manner, we outperform all others on small cuts (vertical bar S vertical bar = o(n)). We also apply our technique to the task of estimating the variance of a given matrix in any given direction. The JL transform allows us to publish a sanitized covariance matrix that preserves differential privacy w.r.t bounded changes (each row in the matrix can change by at most a norm-1 vector) while adding random noise of magnitude independent of the size of the matrix (w.h.p). In contrast, existing algorithms introduce an error which depends on the matrix dimensions.
引用
收藏
页码:410 / 419
页数:10
相关论文
共 30 条
  • [1] [Anonymous], 1984, CONTEMP MATH-SINGAP
  • [2] [Anonymous], 1985, Matrix Analysis
  • [3] [Anonymous], 2010, FOCS
  • [4] [Anonymous], 2003, P 22 ACM SIGMOD SIGA
  • [5] Kernels as features: On kernels, margins, and low-dimensional mappings
    Balcan, Maria-Florina
    Blum, Avrim
    Vempala, Santosh
    [J]. MACHINE LEARNING, 2006, 65 (01) : 79 - 94
  • [6] BHATIA R, 2007, CLASSICS APPL MATH
  • [7] Blocki J., 2012, ABS12042136 CORR, Vabs/1204.2136
  • [8] Blum A, 2008, ACM S THEORY COMPUT, P609
  • [9] Blum Avrim, 2005, P 24 ACM SIGMOD SIGA, P128, DOI [DOI 10.1145/1065167.1065184, 10.1145/1065167.1065184]
  • [10] Chawla S, 2005, LECT NOTES COMPUT SC, V3378, P363