Redrawing the boundaries on purchasing data from privacy-sensitive individuals

ABSTRACT

We prove new positive and negative results concerning the existence of truthful and individually rational mechanisms for purchasing private data from individuals with unbounded and sensitive privacy preferences. We strengthen the impossibility results of Ghosh and Roth (EC 2011) by extending it to a much wider class of privacy valuations. In particular, these include privacy valuations that are based on (ε δ)-differentially private mechanisms for non-zero δ, ones where the privacy costs are measured in a per-database manner (rather than taking the worst case), and ones that do not depend on the payments made to players (which might not be observable to an adversary).

To bypass this impossibility result, we study a natural special setting where individuals have monotonic privacy valuations, which captures common contexts where certain values for private data are expected to lead to higher valuations for privacy (e. g. having a particular disease). We give new mechanisms that are individually rational for all players with monotonic privacy valuations, truthful for all players whose privacy valuations are not too large, and accurate if there are not too many players with too-large privacy valuations. We also prove matching lower bounds showing that in some respects our mechanism cannot be improved significantly.

References

1. A. Beimel, K. Nissim, and U. Stemmer. Private Learning and Sanitization: Pure vs. Approximate Differential Privacy. In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM '13), Lecture Notes in Computer Science, pages 363--378. Springer-Verlag, 21-23 August 2013.
2. Y. Chen, S. Chong, I. A. Kash, T. Moran, and S. Vadhan. Truthful mechanisms for agents that value privacy. In Proceedings of the fourteenth ACM conference on Electronic commerce, EC '13, pages 215--232, New York, NY, USA, 2013. ACM.
3. Y. Chen, S. Chong, I. A. Kash, T. Moran, and S. P. Vadhan. Truthful Mechanisms for Agents that Value Privacy. CoRR, abs/1111.5472, 2011.
4. A. De. Lower bounds in differential privacy. In Theory of cryptography conference (TCC '12), volume 7194 of Lecture Notes in Comput. Sci., pages 321--338. Springer, Heidelberg, 2012.
5. C. Dwork. Differential privacy. In In Proc. ICALP, pages 1--12. Springer, 2006.
6. C. Dwork and J. Lei. Differential privacy and robust statistics In STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing, pages 371--380. ACM, New York, 2009.
7. C. Dwork, F. Mcsherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In In Proc. of the 3rd TCC, pages 265--284. Springer, 2006.
8. C. Dwork, G. Rothblum, and S. Vadhan. Boosting and Differential Privacy. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS '10), pages 51--60. IEEE, 23-26 October 2010.
9. L. K. Fleischer and Y.-H. Lyu. Approximately optimal auctions for selling privacy when costs are correlated with data. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, pages 568--585, New York, NY, USA, 2012. ACM.
10. A. Ghosh and A. Roth. Selling privacy at auction. In Proc. 12th EC, EC '11, pages 199--208, New York, NY, USA, 2011. ACM.
11. M. Hardt and K. Talwar. On the geometry of differential privacy. In STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 705--714. ACM, New York, 2010.
12. Z. Huang and S. Kannan. The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal. In Proc. FOCS '12, pages 140--149, 2012.
13. M. Kearns, M. M. Pai, A. Roth, and J. Ullman. Mechanism Design in Large Games: Incentives and Privacy. In Proc. ITCS 2013, 2013. Available at http://arxiv.org/abs/1207.4084.
14. K. Ligett and A. Roth. Take it or Leave it: Running a Survey when Privacy Comes at a Cost. In Proceedings of the 8th Workshop on Internet and Network Economics, pages 378--391. Springer, 2012.
15. F. McSherry and K. Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual Symposium on Foundations of Computer Science. Citeseer, 2007.
16. K. Nissim, C. Orlandi, and R. Smorodinsky. Privacy-aware mechanism design. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, pages 774--789, New York, NY, USA, 2012. ACM.
17. K. Nissim, R. Smorodinsky, and M. Tennenholtz. Approximately optimal mechanism design via differential privacy. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pages 203--213, New York, NY, USA, 2012. ACM.
18. M. M. Pai and A. Roth. Privacy and mechanism design. SIGecom Exch., 12(1):8--29, June 2013.
19. A. Roth. Buying private data at auction: the sensitive surveyor's problem. SIGecom Exch., 11(1):1--8, June 2012.
20. A. Roth and G. Schoenebeck. Conducting truthful surveys, cheaply. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, pages 826--843, New York, NY, USA, 2012. ACM.
21. D. Xiao. Is privacy compatible with truthfulness? Technical Report 2011/005, Cryptology ePrint Archive, 2011.
22. D. Xiao. Is privacy compatible with truthfulness? In In Proc. ITCS 2013, pages 67--86, 2013.

Index Terms

• Security and privacy

  • Human and societal aspects of security and privacy

• Social and professional topics

  • Computing / technology policy

    • Privacy policies

• Theory of computation