Separating Computational and Statistical Differential Privacy in the Client-Server Model
By Mark Bun, Yi-Hsiu Chen, Salil P. Vadhan. 2016
16 citations recorded by the source corpus.
Differential privacy is a mathematical definition of privacy for statistical data analysis. It guarantees that any possibly adversarial data analyst is unable to learn too much information that is specific to an individual. Mironov et al.i¾?CRYPTO 2009 proposed several computational relaxations of differential privacy CDP, which relax this guarantee to hold only against computationally bounded adversaries. Their work and subsequent work showed that CDP can yield substantial accuracy improvements in various multiparty privacy problems. However, these works left open whether such improvements are possible in the traditional client-server model of data analysis. In fact, Groce, Katz and Yerukhimovichi¾?TCC 2011 showed that, in this setting, it is impossible to take advantage of CDP for many natural statistical tasks. Our main result shows that, assuming the existence of sub-exponentially secure one-way functions and 2-message witness indistinguishable proofs zaps for $$\mathbf {NP}$$ , that there is in fact a computational task in the client-server model that can be efficiently performed with CDP, but is infeasible to perform with information-theoretic differential privacy.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Ilya Mironov
- Salil P. Vadhan
- Yu-Xiang Wang
- Thomas Steinke
- Jonathan Ullman
- Abhradeep Thakurta
- Kunal Talwar
- Vitaly Feldman
Citations in the corpus
- Rényi Differential Privacy (2017, background): “The IND-CDP notion allows much more accurate functionalities in the two-party setting [12]; in the traditional client-server setup there is a natural class of functionalities where the gap between IND-CDP and ( , δ)-DP is minimal [13], and there are (contrived) examples where the computational relax”
- The Complexity of Differential Privacy (2017, background): “answering a logarithmic number of real-valued queries) as well as outputs in polynomial-sized discrete sets [55, 24].”