Attacks on privacy and deFinetti's theorem

ABSTRACT

In this paper we present a method for reasoning about privacy using the concepts of exchangeability and deFinetti's theorem. We illustrate the usefulness of this technique by using it to attack a popular data sanitization scheme known as Anatomy. We stress that Anatomy is not the only sanitization scheme that is vulnerable to this attack. In fact, any scheme that uses the random worlds model, i.i.d. model, or tuple-independent model needs to be re-evaluated.

The difference between the attack presented here and others that have been proposedin the past is that we do not need extensive background knowledge. An attacker only needs to know the nonsensitive attributes of one individual in the data, and can carry out this attack just by building a machine learning model over the sanitized data. The reason this attack is successful is that it exploits a subtle flaw in the way prior work computed the probability of disclosure of a sensitive attribute. We demonstrate this theoretically, empirically, and with intuitive examples. We also discuss how this generalizes to many other privacy schemes.

REFERENCES

• 1: Charu C. Aggarwal , Jian Pei , Bo Zhang, On privacy preservation against adversarial data mining, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150460]
• 2: Gagan Aggarwal , Tomás Feder , Krishnaram Kenthapadi , Samir Khuller , Rina Panigrahy , Dilys Thomas , An Zhu, Achieving anonymity via clustering, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142374]
• 3: A. Asuncion and D.J. Newman. UCI machine learning repository, 2007.
• 4: F. Bacchus, A. J. Grove, J. Y. Halpern, and D. Koller. From statistics to beliefs. In AAAI, 1992.
• 5: Lars Backstrom , Cynthia Dwork , Jon Kleinberg, Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242598]
• 6: Michael Barbaro and Tom Zeller. A face is exposed for AOL searcher no. 4417749. New York Times, August 9 2006.
• 7: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering, p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 8: Yvonne M. Bishop, Stephen E. Fienberg, and Paul W. Holland. Discrete Multivariate Analysis: Theory and Practice. Springer, 2007.
• 9: Bee-Chung Chen , Lei Chen , Raghu Ramakrishnan , David R. Musicant, Learning from Aggregate Views, Proceedings of the 22nd International Conference on Data Engineering, p.3, April 03-07, 2006 [doi>10.1109/ICDE.2006.86]
• 10: Bee-Chung Chen , Kristen LeFevre , Raghu Ramakrishnan, Privacy skyline: privacy with multidimensional adversarial knowledge, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 11: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 12: Nando de Freitas and Hendrik Kück. Learning about individuals from group statistics. In UAI, pages 332--339, 2005.
• 13: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1--38, 1977.
• 14: Persi Diaconis and David Freedman. De finetti's generalizations of exchangeability. In Richard C. Jeffrey, editor, Studies in Inductive Logic and Probability, Volume II, pages 233--249. University of California Press, 1980.
• 15: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 16: Wenliang Du , Zhouxuan Teng , Zutao Zhu, Privacy-MaxEnt: integrating background knowledge in privacy quantification, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376665]
• 17: Cynthia Dwork. Differential privacy. In ICALP, 2006.
• 18: Fernando Esponda , Elena S. Ackley , Paul Helman , Haixia Jia , Stephanie Forrest, Protecting data privacy through hard-to-reverse negative databases, International Journal of Information Security, v.6 n.6, p.403-415, October 2007 [doi>10.1007/s10207-007-0030-1]
• 19: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 20: Chengfang Fang , Ee-Chien Chang, Information Leakage in Optimal Anonymized and Diversified Data, Information Hiding: 10th International Workshop, IH 2008, Santa Barbara, CA, USA, May 19-21, 2008, Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-88961-8_3]
• 21: Srivatsava Ranjit Ganta, Shiva Prasad Kasiviswanathan, and Adam Smith. Composition attacks and auxiliary information in data privacy. In KDD, 2008.
• 22: Gabriel Ghinita , Panagiotis Karras , Panos Kalnis , Nikos Mamoulis, Fast data anonymization with low information loss, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 23: Michael Hay , Gerome Miklau , David Jensen , Don Towsley , Philipp Weis, Resisting structural re-identification in anonymized social networks, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453873]
• 24: Zhengli Huang , Wenliang Du , Biao Chen, Deriving private information from randomized data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066163]
• 25: George H. John and Pat Langley. Estimating continuous distributions in bayesian classifiers. In UAI, 1995.
• 26: Hillol Kargupta , Souptik Datta , Qi Wang , Krishnamoorthy Sivakumar, On the Privacy Preserving Properties of Random Data Perturbation Techniques, Proceedings of the Third IEEE International Conference on Data Mining, p.99, November 19-22, 2003
• 27: Daniel Kifer , Johannes Gehrke, Injecting utility into anonymized datasets, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142499]
• 28: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 29: Ravi Kumar , Jasmine Novak , Bo Pang , Andrew Tomkins, On anonymizing query logs via token-based hashing, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242657]
• 30: Laks V. S. Lakshmanan , Raymond T. Ng , Ganesh Ramesh, To do or not to do: the dilemma of disclosing anonymized data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066165]
• 31: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Incognito: efficient full-domain K-anonymity, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066164]
• 32: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 33: N. Li, T. Li, and S. Venkatasubramanian. t-Closeness: Privacy beyond k-anonymity and l-diversity. In ICDE, 2007.
• 34: Tiancheng Li , Ninghui Li, Injector: Mining Background Knowledge for Data Anonymization, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.446-455, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497453]
• 35: Ashwin Machanavajjhala , Daniel Kifer , Johannes Gehrke , Muthuramakrishnan Venkitasubramaniam, L-diversity: Privacy beyond k-anonymity, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.3-es, March 2007 [doi>10.1145/1217299.1217302]
• 36: David Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes Gehrke, and Joseph Halpern. Worst case background knowledge for privacy preserving data publishing. In ICDE, 2007.
• 37: Gerome Miklau , Dan Suciu, A formal analysis of information disclosure in data exchange, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007633]
• 38: Krishnamurty Muralidhar , Rathindra Sarathy, Security of random data perturbation methods, ACM Transactions on Database Systems (TODS), v.24 n.4, p.487-493, Dec. 1999 [doi>10.1145/331983.331986]
• 39: Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the net ix prize dataset. http://arxiv.org/abs/cs/0610105, 2006.
• 40: Arvind Narayanan , Vitaly Shmatikov, Robust De-anonymization of Large Sparse Datasets, Proceedings of the 2008 IEEE Symposium on Security and Privacy, p.111-125, May 18-21, 2008 [doi>10.1109/SP.2008.33]
• 41: Novi Quadrianto , Alex J. Smola , Tiberio S. Caetano , Quoc V. Le, Estimating labels from label proportions, Proceedings of the 25th international conference on Machine learning, p.776-783, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390254]
• 42: Vibhor Rastogi , Dan Suciu , Sungho Hong, The boundary between privacy and utility in data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 43: Jason Rennie, Lawrence Shih, Jaime Teevan, and David R. Karger. Tackling the poor assumptions of naive bayes text classifiers. In ICML, 2003.
• 44: Christian P. Robert , George Casella, Monte Carlo Statistical Methods (Springer Texts in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 45: Mark J. Schervish. Theory of Statistics. Springer, 1995.
• 46: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 47: L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 1979.
• 48: Raymond Chi-Wing Wong , Ada Wai-Chee Fu , Ke Wang , Jian Pei, Minimality attack in privacy preserving data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 49: Xiaokui Xiao , Yufei Tao, Anatomy: simple and effective privacy preservation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 50: Hui Xiong , Michael Steinbach , Vipin Kumar, Privacy leakage in multi-relational databases: a semi-supervised learning perspective, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.4, p.388-402, November 2006 [doi>10.1007/s00778-006-0011-4]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.m Miscellaneous

General Terms:
Security

Keywords:
privacy, random worlds