You are what you say: privacy risks of public mentions

ABSTRACT

In today's data-rich networked world, people express many aspects of their lives online. It is common to segregate different aspects in different places: you might write opinionated rants about movies in your blog under a pseudonym while participating in a forum or web site for scholarly discussion of medical ethics under your real name. However, it may be possible to link these separate identities, because the movies, journal articles, or authors you mention are from a sparse relation space whose properties (e.g., many items related to by only a few users) allow re-identification. This re-identification violates people's intentions to separate aspects of their life and can have negative consequences; it also may allow other privacy violations, such as obtaining a stronger identifier like name and address.This paper examines this general problem in a specific setting: re-identification of users from a public web movie forum in a private movie ratings dataset. We present three major results. First, we develop algorithms that can re-identify a large proportion of public users in a sparse relation space. Second, we evaluate whether private dataset owners can protect user privacy by hiding data; we show that this requires extensive and undesirable changes to the dataset, making it impractical. Third, we evaluate two methods for users in a public forum to protect their own privacy, suppression and misdirection. Suppression doesn't work here either. However, we show that a simple misdirection strategy works well: mention a few popular items that you haven't rated.

REFERENCES

• 1: Mark S. Ackerman , Lorrie Faith Cranor , Joseph Reagle, Privacy in e-commerce: examining user scenarios and privacy preferences, Proceedings of the 1st ACM conference on Electronic commerce, p.1-8, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.336995]
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 3: Berkovsky, S., Eytani, Y., Kuflik, T., and Ricci, R. 2005. Privacy-Enhanced Collaborative Filtering. In Proc. User Modeling Workshop on Privacy-Enhanced Personalization.
• 4: John Canny, Collaborative filtering with privacy via factor analysis, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564419]
• 5: Kushal Dave , Steve Lawrence , David M. Pennock, Mining the peanut gallery: opinion extraction and semantic classification of product reviews, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775226]
• 6: Sara Drenner , Max Harper , Dan Frankowski , John Riedl , Loren Terveen, Insert movie reference here: a system to bridge conversation and item-oriented web sites, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124914]
• 7: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775080]
• 8: Jason I. Hong , James A. Landay, An architecture for privacy-sensitive ubiquitous computing, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990087]
• 9: Shyong K. Lam , John Riedl, Shilling recommender systems for fun and profit, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988726]
• 10: Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, Anti-aliasing on the web, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988678]
• 11: Bo Pang , Lillian Lee , Shivakumar Vaithyanathan, Thumbs up?: sentiment classification using machine learning techniques, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.79-86, July 06, 2002 [doi>10.3115/1118693.1118704]
• 12: Huseyin Polat , Wenliang Du, Privacy-Preserving Collaborative Filtering Using Randomized Perturbation Techniques, Proceedings of the Third IEEE International Conference on Data Mining, p.625, November 19-22, 2003
• 13: Naren Ramakrishnan , Benjamin J. Keller , Batul J. Mirza , Ananth Y. Grama , George Karypis, Privacy Risks in Recommender Systems, IEEE Internet Computing, v.5 n.6, p.54-62, November 2001 [doi>10.1109/4236.968832]
• 14: Rizvi, S., and Haritsa, J. 2002. Maintaining Privacy in Association Rule Mining. In Proc. VLDB02, pp. 682--693.
• 15: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 16: Latanya Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.571-588, October 2002 [doi>10.1142/S021848850200165X]
• 17: 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]
• 18: Taylor, H. 2003. Most People Are "Privacy Pragmatists." The Harris Poll #17. Harris Interactive (March 19, 2003).
• 19: Loren Terveen , Will Hill , Brian Amento , David McDonald , Josh Creter, PHOAKS: a system for sharing recommendations, Communications of the ACM, v.40 n.3, p.59-62, March 1997 [doi>10.1145/245108.245122]
• 20: Vassilios S. Verykios , Elisa Bertino , Igor Nai Fovino , Loredana Parasiliti Provenza , Yucel Saygin , Yannis Theodoridis, State-of-the-art in privacy preserving data mining, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974131]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Keywords:
k-anonymity, k-identification, datasets, mentions, privacy, re-identification, sparse relation space