On anonymizing query logs via token-based hashing

ABSTRACT

In this paper we study the privacy preservation properties of aspecific technique for query log anonymization: token-based hashing. In this approach, each query is tokenized, and then a secure hash function is applied to each token. We show that statistical techniques may be applied to partially compromise the anonymization. We then analyze the specific risks that arise from these partial compromises, focused on revelation of identity from unambiguous names, addresses, and so forth, and the revelation of facts associated with an identity that are deemed to be highly sensitive. Our goal in this work is two fold: to show that token-based hashing is unsuitable for anonymization, and to present a concrete analysis of specific techniques that may be effective in breaching privacy, against which other anonymization schemes should be measured.

REFERENCES

• 1: Regina Barzilay , Kathleen R. McKeown, Extracting paraphrases from a parallel corpus, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.50-57, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073020]
• 2: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 3: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 4: Bernard J. Jansen , Amanda Spink , Judy Bateman , Tefko Saracevic, Real life information retrieval: a study of user queries on the Web, ACM SIGIR Forum, v.32 n.1, p.5-17, Spring 1998 [doi>10.1145/281250.281253]
• 5: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 6: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 7: Jon Kleinberg , Eva Tardos, Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 8: Lillian Lee, Measures of distributional similarity, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.25-32, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034693]
• 9: Ronny Lempel , Shlomo Moran, Optimizing result prefetching in web search engines with segmented indices, ACM Transactions on Internet Technology (TOIT), v.4 n.1, p.31-59, February 2004 [doi>10.1145/967030.967032]
• 10: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 11: 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]
• 12: Ruoming Pang , Vern Paxson, A high-level programming environment for packet trace anonymization and transformation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863994]
• 13: Fernando Pereira , Naftali Tishby , Lillian Lee, Distributional clustering of English words, Proceedings of the 31st annual meeting on Association for Computational Linguistics, p.183-190, June 22-26, 1993, Columbus, Ohio [doi>10.3115/981574.981598]
• 14: Daniel E. Rose , Danny Levinson, Understanding user goals in web search, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988675]
• 15: Nancy C. M. Ross, End user searching on the Internet: an analysis of term pair topics submitted to the excite search engine, Journal of the American Society for Information Science, v.51 n.10, p.949-958, Aug. 2000 [doi>10.1002/1097-4571(2000)51:10<949::AID-ASI70>3.0.CO;2-5]
• 16: Pierangela Samarati , Latanya Sweeney, Generalizing data to provide anonymity when disclosing information (abstract), Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.188, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275508]
• 17: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 18: A. Slagell and W. Yurcik. Sharing computer network logs for security and privacy: A motivation for new methodologies of anonymization. In Workshop of the 1st International Conference on Security and Privacy for Emerging Areas in Communication Networks, pages 80--89, 2005.
• 19: Amanda Spink, A user-centered approach to evaluating human interaction with web search engines: an exploratory study, Information Processing and Management: an International Journal, v.38 n.3, p.401-426, May 2002 [doi>10.1016/S0306-4573(01)00036-X]
• 20: Amanda Spink , Bernard J. Jansen , Dietmar Wolfram , Tefko Saracevic, From E-Sex to E-Commerce: Web Search Changes, Computer, v.35 n.3, p.107-109, March 2002 [doi>10.1109/2.989940]
• 21: Amanda Spink , H. Cenk Ozmultu, Characteristics of question format web queries: an exploratory study, Information Processing and Management: an International Journal, v.38 n.4, p.453-471, July 2002 [doi>10.1016/S0306-4573(01)00042-5]
• 22: Sheng Zhong , Zhiqiang Yang , Rebecca N. Wright, Privacy-enhancing k-anonymization of customer data, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065185]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
hash-based anonymization, privacy, query logs