@conference {634705,
	title = {Computational differential privacy},
	booktitle = {S. Halevi, editor, Advances in Cryptology{\textemdash}CRYPTO {\textquoteleft}09, Lecture Notes in Computer Science},
	volume = {5677},
	year = {2009},
	pages = {126-142},
	publisher = {Springer-Verlag},
	organization = {Springer-Verlag},
	abstract = {
	The definition of differential privacy has recently emerged as a leading standard of privacy guarantees for algorithms on statistical databases. We offer several relaxations of the definition which require privacy guarantees to hold only against\&nbsp;efficient{\textemdash}i.e.,\&nbsp;computationally-bounded{\textemdash}adversaries. We establish various relationships among these notions, and in doing so, we observe their close connection with the theory of pseudodense sets by Reingold et al.[1]. We extend the dense model theorem of Reingold et al.\&nbsp;to demonstrate equivalence between two definitions (indistinguishability-and simulatability-based) of computational differential privacy.



	Our computational analogues of differential privacy seem to allow for more accurate constructions than the standard information-theoretic analogues. In particular, in the context of private approximation of the distance between two vectors, we present a differentially-private protocol for computing the approximation, and contrast it with a substantially more accurate protocol that is only\&nbsp;computationally\&nbsp;differentially private.

},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-03356-8_8},
	author = {Ilya Mironov and Omkant Pandey and Omer Reingold and Salil Vadhan}
}
