Staal A. Vinterbo

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.