A privacy-preserving collaborative filtering scheme with two-way communication

ABSTRACT

An important security concern with traditional recommendation systems is that users disclose information that may compromise their individual privacy when providing ratings. A randomization approach has been proposed to disguise user ratings while still producing accurate recommendations. However, recent research has suggested that a significant amount of original private information can be derived from perturbed data in a randomization scheme. We suggest that a main limitation of the existing randomization approach is that perturbation is item-invariant--each item has a same perturbation variance. Based on this observation, we introduce a two-way communication privacypreserving scheme in which users perturb their ratings for each item based on the server's guidance instead of using an item-invariant perturbation. Compared to the existing randomization approach, our new scheme can help users disclose much less private information at the same recommendation accuracy level.

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: Matthew Brand, Incremental Singular Value Decomposition of Uncertain Data with Missing Values, Proceedings of the 7th European Conference on Computer Vision-Part I, p.707-720, May 28-31, 2002
• 4: J. R. Bunch and C. P. Nielsen. Updating the singular value decomposition. Numerische Mathematik, 31(2):111--129, 1978.
• 5: John Canny, Collaborative Filtering with Privacy, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.45, May 12-15, 2002
• 6: 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]
• 7: L. F. Cranor, J. Reagle, and M. S. Ackerman. Beyond concern: Understanding net users' attitudes. Technical report, AT&T Research, available at http://www.research.att.com/projects/privacystudy/,1999.
• 8: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. of the Royal Statistical Society, series B, 39(1):1--38, 1977.
• 9: W. Du , M. Atallah, Privacy-Preserving Cooperative Statistical Analysis, Proceedings of the 17th Annual Computer Security Applications Conference, p.102, December 10-14, 2001
• 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: Jonathan L. Herlocker , Joseph A. Konstan , Al Borchers , John Riedl, An algorithmic framework for performing collaborative filtering, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.230-237, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312682]
• 13: Jonathan L. Herlocker , Joseph A. Konstan , Loren G. Terveen , John T. Riedl, Evaluating collaborative filtering recommender systems, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.5-53, January 2004 [doi>10.1145/963770.963772]
• 14: 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]
• 15: 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
• 16: 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
• 17: Huseyin Polat , Wenliang Du, SVD-based collaborative filtering with privacy, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066860]
• 18: 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]
• 19: B. M. Sarwar, G. Karypis, J. A. Konstan, and J. Riedl. Application of dimensionality reduction in recommender systems--a case study. In Proc. of the ACM WebKDD Workshop, 2000.
• 20: Nan Zhang , Shengquan Wang , Wei Zhao, A new scheme on privacy preserving association rule mining, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.484-495, September 20-24, 2004, Pisa, Italy
• 21: Nan Zhang , Shengquan Wang , Wei Zhao, A new scheme on privacy-preserving data classification, 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.1081913]
• 22: S. Zhang, J. Ford, and F. Makedon. Deriving private information from randomly perturbed ratings. To appear in SIAM-Data Mining Conf. 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Commercial services

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

General Terms:
Security

Keywords:
collaborative filtering, privacy, randomization, two-way communication