Efficient anonymity-preserving data collection

ABSTRACT

The output of a data mining algorithm is only as good as its inputs, and individuals are often unwilling to provide accurate data about sensitive topics such as medical history and personal finance. Individuals maybe willing to share their data, but only if they are assured that it will be used in an aggregate study and that it cannot be linked back to them. Protocols for anonymity-preserving data collection provide this assurance, in the absence of trusted parties, by allowing a set of mutually distrustful respondents to anonymously contribute data to an untrusted data miner.To effectively provide anonymity, a data collection protocol must be collusion resistant, which means that even if all dishonest respondents collude with a dishonest data miner in an attempt to learn the associations between honest respondents and their responses, they will be unable to do so. To achieve collusion resistance, previously proposed protocols for anonymity-preserving data collection have quadratically many communication rounds in the number of respondents, and employ (sometimes incorrectly) complicated cryptographic techniques such as zero-knowledge proofs.We describe a new protocol for anonymity-preserving, collusion resistant data collection. Our protocol has linearly many communication rounds, and achieves collusion resistance without relying on zero-knowledge proofs. This makes it especially suitable for data mining scenarios with a large number of respondents.

REFERENCES

• 1: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 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: M. Bellare and P. Rogaway. Introduction to modern cryptography, 2005. http://www-cse.ucsd.edu/users/mihir/cse207/classnotes.html.
• 4: Xavier Boyen , Qixiang Mei , Brent Waters, Direct chosen ciphertext security from identity-based techniques, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102162]
• 5: Chris Clifton , Murat Kantarcioglu , Jaideep Vaidya , Xiaodong Lin , Michael Y. Zhu, Tools for privacy preserving distributed data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.28-34, December 2002 [doi>10.1145/772862.772867]
• 6: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 7: R. Dingledine, N. Mathewson, and P. Syverson. Tor: the second-generation onion router. In Proc. 13th USENIX Security Symposium, pages 303--320, 2004.
• 8: Wenliang Du , Zhijun Zhan, Using randomized response techniques for privacy-preserving data mining, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956810]
• 9: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 10: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 11: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 12: Philippe Golle , Sheng Zhong , Dan Boneh , Markus Jakobsson , Ari Juels, Optimistic Mixing for Exit-Polls, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.451-465, December 01-05, 2002
• 13: Jens Groth, A Verifiable Secret Shuffle of Homomorphic Encryptions, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.145-160, January 06-08, 2003
• 14: Y. Lindell and B. Pinkas. Privacy preserving data mining. J. Cryptology, 15(3):177--206, 2002.
• 15: A. Neff. Verifiable mixing (shuffling) of ElGamal pairs. url http://www.votehere.net/vhti/documentation/egshuf.pdf.
• 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: Paul F. Syverson , David M. Goldschlag , Michael G. Reed, Anonymous Connections and Onion Routing, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.44, May 04-07, 1997
• 19: D. Wikström. Four practical attacks for "optimistic mixing for exit-polls". Technical Report T2003-04, Swedish Institute of Computer Sciences (SICS), 2003.
• 20: Rebecca Wright , Zhiqiang Yang, Privacy-preserving Bayesian network structure computation on distributed heterogeneous data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014145]
• 21: Zhiqiang Yang , Sheng Zhong , Rebecca N. Wright, Anonymity-preserving data collection, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081909]
• 22: A. Yao. How to generate and exchange secrets. In FOCS '86: Proc. of the 27th IEEE Annual Symposium on Foundations of Computer Science, pages 162--167, 1986.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Security

Keywords:
anonymity, data mining, privacy