Collusion-resistant anonymous data collection method

ABSTRACT

The availability and the accuracy of the data dictate the success of a data mining application. Increasingly, there is a need to resort to on-line data collection to address the problem of data availability. However, participants in on-line data collection applications are naturally distrustful of the data collector as well as their peer respondents, resulting in inaccurate data collected as the respondents refuse to provide truthful data in fear of collusion attacks. The current anonymity-preserving solutions for on-line data collection are unable to adequately resist such attacks in a scalable fashion. In this paper, we present an efficient anonymous data collection protocol for a malicious environment such as the Internet. The protocol employs cryptographic and random shuffling techniques to preserve participants' anonymity. The proposed method is collusion-resistant and guarantees that an attacker will be unable to breach an honest participant's anonymity unless she controls all N-1 participants. In addition, our method is efficient and achieved 15-42% communication overhead reduction in comparison to the prior state-of-the-art methods.

REFERENCES

• 1: Rakesh Agrawal , Alexandre Evfimievski , Ramakrishnan Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872771]
• 2: Justin Brickell , Vitaly Shmatikov, Efficient anonymity-preserving data collection, 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.1150415]
• 3: Zhiqiang Yang , Sheng Zhong , Rebecca N. Wright, Anonymity-preserving data collection, Proceedings 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]
• 4: Philippe Golle , Frank McSherry , Ilya Mironov, Data collection with self-enforcing privacy, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180416]
• 5: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 6: D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
• 7: S. L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. The American Statistical Association, 60 p.63--69, 1965.
• 8: B. Schneier, Applied Cryptography, 2nd Edition, John Wiley&Sons.
• 9: O. Golderich. Foundation of Cryptography. Cambridge University Press.
• 10: 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]
• 11: 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]
• 12: A. Ambainis, M. Jakobsson, and H. Lipmaa. Cryptographic randomized response techniques. In Proc. of the Public Key Cryptography, p. 425--438, 2004.
• 13: Luis von Ahn , Andrew Bortz , Nicholas J. Hopper, k-anonymous message transmission, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948128]
• 14: Brian Neil Levine , Clay Shields, Hordes: a multicast based protocol for anonymity, Journal of Computer Security, v.10 n.3, p.213-240, 2002
• 15: Michael K. Reiter , Aviel D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security (TISSEC), v.1 n.1, p.66-92, Nov. 1998 [doi>10.1145/290163.290168]
• 16: 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
• 17: Andreas Pfitzmann , Marit Köhntopp, Anonymity, unobservability, and pseudeonymity — a proposal for terminology, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.1-9, January 2001, Berkeley, California, United States
• 18: 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
• 19: T. ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. on Info. Theory, 31(4), p. 469 -- 472, 1985.
• 20: G, Oded (2002). Secure multi-party computation. Final (incomplete) draft, version 1.4.
• 21: Michael Waidner, Unconditional sender and recipient untraceability in spite of active attacks, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.302-319, November 1990, Houthalen, Belgium
• 22: P. Golle and A. Juels. Dining cryptographers revisited. In proc. of the EUROCRYPT, p. 456--473, 2004.
• 23: Y. Li, J. D. Tygar, and J. M. Hellerstein. Private matching. In Computer Security in the 21st Century. D. T. Lee, S. P. Shieh and J. D. Tygar (Eds) p. 25--50, Springer.

INDEX TERMS

Primary 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