Staal A. Vinterbo

Shuang Song, Susan Little, Sanjay Mehta et al.

Motivated by understanding the dynamics of sensitive social networks over time, we consider the problem of continual release of statistics in a network that arrives online, while preserving privacy of its participants. For our privacy notion, we use differential privacy -- the gold standard in privacy for statistical data analysis. The main challenge in this problem is maintaining a good privacy-utility tradeoff; naive solutions that compose across time, as well as solutions suited to tabular data either lead to poor utility or do not directly apply. In this work, we show that if there is a publicly known upper bound on the maximum degree of any node in the entire network sequence, then we can release many common graph statistics such as degree distributions and subgraph counts continually with a better privacy-accuracy tradeoff. Code available at https://bitbucket.org/shs037/graphprivacycode

Staal A. Vinterbo

Adding random noise to database query results is an important tool for achieving privacy. A challenge is to minimize this noise while still meeting privacy requirements. Recently, a sufficient and necessary condition for $(ε, δ)$-differential privacy for Gaussian noise was published. This condition allows the computation of the minimum privacy-preserving scale for this distribution. We extend this work and provide a sufficient and necessary condition for $(ε, δ)$-differential privacy for all symmetric and log-concave noise densities. Our results allow fine-grained tailoring of the noise distribution to the dimensionality of the query result. We demonstrate that this can yield significantly lower mean squared errors than those incurred by the currently used Laplace and Gaussian mechanisms for the same $ε$ and $δ$.

Staal A. Vinterbo

The standard closed form lower bound on $σ$ for providing $(ε, δ)$-differential privacy by adding zero mean Gaussian noise with variance $σ^2$ is $σ> Δ\sqrt {2}(ε^{-1}) \sqrt {\log \left( 5/4δ^{-1} \right)}$ for $ε\in (0,1)$. We present a similar closed form bound $σ\geq Δ(ε\sqrt{2})^{-1} \left(\sqrt{az+ε} + s\sqrt{az}\right)$ for $z=-\log(4δ(1-δ))$ and $(a,s)=(1,1)$ if $δ\leq 1/2$ and $(a,s)=(π/4,-1)$ otherwise. Our bound is valid for all $ε> 0$ and is always lower (better). We also present a sufficient condition for $(ε, δ)$-differential privacy when adding noise distributed according to even and log-concave densities supported everywhere.

Staal A. Vinterbo

Randomized response is attractive for privacy preserving data collection because the provided privacy can be quantified by means such as differential privacy. However, recovering and analyzing statistics involving multiple dependent randomized binary attributes can be difficult, posing a significant barrier to use. In this work, we address this problem by identifying and analyzing a family of response randomizers that change each binary attribute independently with the same probability. Modes of Google's Rappor randomizer as well as applications of two well-known classical randomized response methods, Warner's original method and Simmons' unrelated question method, belong to this family. We show that randomizers in this family transform multinomial distribution parameters by an iterated Kronecker product of an invertible and bisymmetric $2 \times 2$ matrix. This allows us to present a simple and efficient algorithm for obtaining unbiased maximum likelihood parameter estimates for $k$-way marginals from randomized responses and provide theoretical bounds on the statistical efficiency achieved. We also describe the efficiency - differential privacy tradeoff. Importantly, both randomization of responses and the estimation algorithm are simple to implement, an aspect critical to technologies for privacy protection and security.