More Web Proxy on the site http://driver.im/

research-article

Is privacy compatible with truthfulness?

Author:

David XiaoAuthors Info & Claims

ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science

Pages 67 - 86

https://doi.org/10.1145/2422436.2422448

Published: 09 January 2013 Publication History

Abstract

In the area of privacy-preserving data mining, a differentially private mechanism intuitively encourages people to share their data because they are at little risk of revealing their own information. However, we argue that this interpretation is incomplete because external incentives are necessary for people to participate in databases, and so data release mechanisms should not only be differentially private but also compatible with incentives, otherwise the data collected may be false. We apply the notion of truthfulness from game theory to this problem. In certain settings, it turns out that existing differentially private mechanisms do not encourage participants to report their information truthfully.

On the positive side, we exhibit a transformation that takes truthful mechanisms and transforms them into differentially private mechanisms that remain truthful. Our transformation applies to games where the type space is small and the goal is to optimize an insensitive quantity such as social welfare. Our transformation incurs only a small additive loss in optimality, and it is computationally efficient. Combined with the VCG mechanism, our transformation implies that there exists a differentially private, truthful, and approximately efficient mechanism for any social welfare game with small type space.

We also study a model where an explicit numerical cost is assigned to the information leaked by a mechanism. We show that in this case, even differential privacy may not be strong enough of a notion to motivate people to participate truthfully. We show that mechanisms that release a perturbed histogram of the database may reveal too much information. We also show that, in general, any mechanism that outputs a synopsis that resembles the original database (such as the mechanism of Blum et al. (STOC '08)) may reveal too much information.

References

[1]

Noga Alon, Michal Feldman, Ariel D. Procaccia, and Moshe Tennenholtz. Strategyproof approximation of the minimax on networks. Mathematics of Operations Research, 35 (3): 513--526, 2010.

[2]

Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank Mcsherry, and Kunal Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In Proc. of 26th PODS, pages 273--282, 2007.

Digital Library

[3]

Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to non-interactive database privacy. In Proc. 40th STOC, pages 609--618, 2008.

Digital Library

[4]

Yiling Chen, Stephen Chong, Ian A. Kash, Tal Moran, and Salil P. Vadhan. Truthful mechanisms for agents that value privacy. CoRR, abs/1111.5472, 2011.

[5]

T. Dalenius. Towards a methodology for statistical disclosure control. Statistik Tidskrift, 5: 429--444, 1977.

[6]

Anindya De. Lower bounds in differential privacy. In TCC, pages 321--338, 2012.

Digital Library

[7]

Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In In PODS, pages 202--210. ACM Press, 2003.

[8]

Cynthia Dwork. Differential privacy. In Proc. ICALP, pages 1--12. Springer, 2006.

Digital Library

[9]

Cynthia Dwork. Differential privacy: A survey of results. In Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, editors, Theory and Applications of Models of Computation, volume 4978 of Lecture Notes in Computer Science, pages 1--19. Springer Berlin / Heidelberg, 2008.

[10]

Cynthia Dwork, Krishnaram Kenthapadi, Frank Mcsherry, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In In EUROCRYPT, pages 486--503. Springer, 2006.

[11]

Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the 3rd TCC, pages 265--284. Springer, 2006.

Digital Library

[12]

Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proc. 41st STOC, STOC '09, pages 381--390. ACM, 2009.

Digital Library

[13]

Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In FOCS, pages 51--60, 2010.

Digital Library

[14]

Joan Feigenbaum, Aaron D. Jaggard, and Michael Schapira. Approximate privacy: foundations and quantification (extended abstract). In Proc. 11th EC, EC '10, pages 167--178, New York, NY, USA, 2010. ACM.

Digital Library

[15]

Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim. Private coresets. In Proc. 41st STOC, STOC '09, pages 361--370, New York, NY, USA, 2009. ACM.

Digital Library

[16]

I. Fellegi. On the question of statistical confidentiality. J. of the Amer. Stat. Assoc., 67: 7--18, 1972.

[17]

Lisa K. Fleischer and Yu-Han 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.

Digital Library

[18]

Arpita Ghosh and Aaron Roth. Selling privacy at auction. In Proc. 12th EC, EC '11, pages 199--208, New York, NY, USA, 2011. ACM. ISBN 978--1--4503-0261--6.

Digital Library

[19]

Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. In Proc. 41st STOC, STOC '09, pages 351--360. ACM, 2009.

Digital Library

[20]

Moritz Hardt. A Study of Privacy and Fairness in Sensitive Data Analysis. PhD thesis, Princeton University, 2011.

Digital Library

[21]

Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In Proc. 51st FOCS, pages 61--70, Washington, DC, USA, 2010. IEEE Computer Society. 10.1109/FOCS.2010.85.

Digital Library

[22]

Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proc. 42nd STOC, pages 705--714, New York, NY, USA, 2010. ACM. ISBN 978--1--4503-0050--6. 10.1145/1806689.1806786.

Digital Library

[23]

Zhiyi Huang and Sampath Kannan. The exponential mechanism for social welfare: Private, truthful, and nearly optimal. In Proc. FOCS '12, 2012. To appear. Available at http://arxiv.org/abs/1204.1255.

Digital Library

[24]

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? In Proc. 49th FOCS, pages 531--540, Washington, DC, USA, 2008. IEEE.

Digital Library

[25]

Katrina Ligett and Aaron Roth. Take it or leave it: Running a survey when privacy comes at a cost. CoRR, abs/1202.4741, 2012.

[26]

Pinyan Lu, Xiaorui Sun, Yajun Wang, and Zeyuan Allen Zhu. Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM conference on Electronic commerce, EC '10, pages 315--324. ACM, 2010.

Digital Library

[27]

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual Symposium on Foundations of Computer Science. Citeseer, 2007.

Digital Library

[28]

H. Moulin. On strategy-proofness and single peakedness. Public Choice, 35: 437--455, 1980.

[29]

Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proc. 39th STOC, pages 75--84, 2007.

Digital Library

[30]

Kobbi Nissim, Claudio Orlandi, and Rann 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.

Digital Library

[31]

Kobbi Nissim, Rann Smorodinsky, and Moshe 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. ISBN 978--1--4503--1115--1.

Digital Library

[32]

Aaron Roth and Grant 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.

Digital Library

[33]

J. Schummer and R. V. Vohra. Mechanism design without money. In N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 10, pages 243--266. Cambridge University Press, 2007.

[34]

M. R. Spiegel. Theory and Problems of Probability and Statistics. McGraw-Hill, 1992.

[35]

David Xiao. Is privacy compatible with truthfulness? Cryptology ePrint Archive, Report 2011/005, 2011. http://eprint.iacr.org/.

Cited By

Wang HCui LWang ELiu J(2025)A Differentially Private Approach for Budgeted Combinatorial Multi-Armed BanditsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.340183622:1(424-439)Online publication date: Jan-2025
https://doi.org/10.1109/TDSC.2024.3401836
Pourbabaee FEchenique F(2025)Binary Mechanisms under Privacy-Preserving NoiseJournal of Economic Theory10.1016/j.jet.2025.105965(105965)Online publication date: Jan-2025
https://doi.org/10.1016/j.jet.2025.105965
Li ZLiu AXia LCao YWang HWilliams BChen YNeville J(2023)Differentially private condorcet votingProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25714(5755-5763)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25714
Show More Cited By

Index Terms

Is privacy compatible with truthfulness?
1. Theory of computation

Recommendations

Truthful Mechanisms for Agents That Value Privacy
Special Issue on EC'13

Recent work has constructed economic mechanisms that are both truthful and differentially private. In these mechanisms, privacy is treated separately from truthfulness; it is not incorporated in players’ utility functions (and doing so has been shown to ...
Selling privacy at auction
EC '11: Proceedings of the 12th ACM conference on Electronic commerce

We initiate the study of markets for private data, through the lens of differential privacy. Although the purchase and sale of private data has already begun on a large scale, a theory of privacy as a commodity is missing. In this paper, we propose to ...
Redrawing the boundaries on purchasing data from privacy-sensitive individuals
ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science

January 2013

594 pages

ISBN:9781450318594

DOI:10.1145/2422436

Program Chair:
Robert Kleinberg
Cornell University

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ITCS '13

Sponsor:

SIGACT

ITCS '13: Innovations in Theoretical Computer Science

January 9 - 12, 2013

California, Berkeley, USA

Acceptance Rates

Overall Acceptance Rate 172 of 513 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
347
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang HCui LWang ELiu J(2025)A Differentially Private Approach for Budgeted Combinatorial Multi-Armed BanditsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.340183622:1(424-439)Online publication date: Jan-2025
https://doi.org/10.1109/TDSC.2024.3401836
Pourbabaee FEchenique F(2025)Binary Mechanisms under Privacy-Preserving NoiseJournal of Economic Theory10.1016/j.jet.2025.105965(105965)Online publication date: Jan-2025
https://doi.org/10.1016/j.jet.2025.105965
Li ZLiu AXia LCao YWang HWilliams BChen YNeville J(2023)Differentially private condorcet votingProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25714(5755-5763)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25714
Krähmer DStrausz R(2023)Optimal Nonlinear Pricing with Data-Sensitive ConsumersAmerican Economic Journal: Microeconomics10.1257/mic.2021019015:2(80-108)Online publication date: 1-May-2023
https://doi.org/10.1257/mic.20210190
Du LCheng PZheng LXi WLin XZhang WFang J(2023)Dynamic Private Task Assignment under Differential Privacy2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00210(2740-2752)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00210
Zhang LZhu TXiong PZhou WYu P(2021)More than PrivacyACM Computing Surveys10.1145/346077154:7(1-37)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3460771
Pal RLi JCrowcroft JLi YLiu MSastry N(2021)Privacy Risk is a Function of Information Type: Learnings for the Surveillance Capitalism AgeIEEE Transactions on Network and Service Management10.1109/TNSM.2020.304670418:3(3280-3296)Online publication date: Sep-2021
https://doi.org/10.1109/TNSM.2020.3046704
Shahani SVenkateswaran RAbraham J(2021)Cost-based recommendation of parameters for local differentially private data aggregationComputers and Security10.1016/j.cose.2020.102144102:COnline publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1016/j.cose.2020.102144
Biswas SJung KPalamidessi C(2021)An Incentive Mechanism for Trading Personal Data in Data MarketsTheoretical Aspects of Computing – ICTAC 202110.1007/978-3-030-85315-0_12(197-213)Online publication date: 20-Aug-2021
https://doi.org/10.1007/978-3-030-85315-0_12
Chen YSheffet OVadhan S(2020)Privacy GamesACM Transactions on Economics and Computation10.1145/33815338:2(1-37)Online publication date: 3-May-2020
https://dl.acm.org/doi/10.1145/3381533
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents