Aaron Roth
ABSTRACT
We define a new interactive differentially private mechanism --- the median mechanism --- for answering arbitrary predicate queries that arrive online. Given fixed accuracy and privacy constraints, this mechanism can answer exponentially more queries than the previously best known interactive privacy mechanism (the Laplace mechanism, which independently perturbs each query result). With respect to the number of queries, our guarantee is close to the best possible, even for non-interactive privacy mechanisms. Conceptually, the median mechanism is the first privacy mechanism capable of identifying and exploiting correlations among queries in an interactive setting.
We also give an efficient implementation of the median mechanism, with running time polynomial in the number of queries, the database size, and the domain size. This efficient implementation guarantees privacy for all input databases, and accurate query results for almost all input distributions. The dependence of the privacy on the number of queries in this mechanism improves over that of the best previously known efficient mechanism by a super-polynomial factor, even in the non-interactive setting.
- A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. In Proceedings of the 40th annual ACM symposium on Theory of computing, pages 609--618. ACM New York, NY, USA, 2008. Google Scholar
Digital Library
- L. Devroye. Non-uniform random variate generation. 1986.Google Scholar
- M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1--17, 1991. Google ScholarDigital Library
- C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Theory of Cryptography Conference TCC, volume 3876 of Lecture Notes in Computer Science, page 265. Springer, 2006. Google ScholarDigital Library
- I. Dinur and K. Nissim. Revealing information while preserving privacy. In 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 202--210, 2003. Google ScholarDigital Library
- 9}DNRRV09C. Dwork, M. Naor, O. Reingold, G.N. Rothblum, and S. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, pages 381--390. ACM New York, NY, USA, 2009. Google ScholarDigital Library
- C. Dwork. Differential privacy: A survey of results. In Proceedings of Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, volume 4978 of Lecture Notes in Computer Science, page 1. Springer, 2008. Google ScholarDigital Library
- A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. In Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, pages 351--360. ACM New York, NY, USA, 2009. Google ScholarDigital Library
- M. Hardt and K. Talwar. On the Geometry of Differential Privacy. In The 42nd ACM Symposium on the Theory of Computing, 2010. STOC'10, 2010. Google ScholarDigital Library
- S.P. Kasiviswanathan, H.K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What Can We Learn Privately? In IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, 2008. FOCS'08, pages 531--540, 2008. Google ScholarDigital Library
- F. McSherry and K. Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual Symposium on Foundations of Computer Science, 2007. Google ScholarDigital Library
- J. Ullman and S. Vadhan. PCPs and the Hardness of Generating Synthetic Data . Manuscript, 2010.Google Scholar
- V. Vapnik. Structure of statistical learning theory. Computational Learning and Probabilistic Reasoning, page 3, 1996.Google Scholar
Index Terms
- Interactive privacy via the median mechanism
Recommendations
Enhancing the Trajectory Privacy with Laplace Mechanism
TRUSTCOM '15: Proceedings of the 2015 IEEE Trustcom/BigDataSE/ISPA - Volume 01Mobile-aware service systems are dramatically increasing the amount of personal data released to service providers as well as to third parties. Data may reveal individuals' physical conditions, habits, and sensitive information. It raises serious ...
Privacy-aware mechanism design
EC '12: Proceedings of the 13th ACM Conference on Electronic CommerceMechanism design deals with distributed algorithms that are executed with self-interested agents. The designer, whose objective is to optimize some function of the agents private types, needs to construct a computation that takes into account agent ...
Differential Privacy via a Truncated and Normalized Laplace Mechanism
AbstractWhen querying databases containing sensitive information, the privacy of individuals stored in the database has to be guaranteed. Such guarantees are provided by differentially private mechanisms which add controlled noise to the query responses. ...
Comments