Valeria Nikolaenko
Dan Boneh
ABSTRACT
Recommender systems typically require users to reveal their ratings to a recommender service, which subsequently uses them to provide relevant recommendations. Revealing ratings has been shown to make users susceptible to a broad set of inference attacks, allowing the recommender to learn private user attributes, such as gender, age, etc. In this work, we show that a recommender can profile items without ever learning the ratings users provide, or even which items they have rated. We show this by designing a system that performs matrix factorization, a popular method used in a variety of modern recommendation systems, through a cryptographic technique known as garbled circuits. Our design uses oblivious sorting networks in a novel way to leverage sparsity in the data. This yields an efficient implementation, whose running time is O(Mlog^2M) in the number of ratings M. Crucially, our design is also highly parallelizable, giving a linear speedup with the number of available processors. We further fully implement our system, and demonstrate that even on commodity hardware with 16 cores, our privacy-preserving implementation can factorize a matrix with 10K ratings within a few hours.
- E. Aimeur, G. Brassard, J. M. Fernandez, and F. S. M. Onana. ALAMBIC: A privacy-preserving recommender system for electronic commerce. Int. J. Inf. Sec., 7(5), 2008. Google Scholar
Digital Library
- M. Ajtai, J. Komlos, and E. Szemeredi. An O(n log n) sorting network. In STOC, 1983. Google ScholarDigital Library
- K. E. Batcher. Sorting networks and their applications. In Proc. AFIPS Spring Joint Computer Conference, 1968. Google ScholarDigital Library
- M. Bellare and S. Micali. Non-interactive oblivious transfer and applications. In CRYPTO, 1990. Google ScholarDigital Library
- E. J. Candes and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 2009. Google ScholarDigital Library
- J. F. Canny. Collaborative filtering with privacy. In IEEE S&P, 2002. Google ScholarDigital Library
- B. Chevallier-Mames, P. Paillier, and D. Pointcheval. Encoding-free ElGamal encryption without random oracles. In PKC, 2006. Google ScholarDigital Library
- S. A. Cook and R. A. Reckhow. Time bounded random access machines. J. Computer and System Sciences, 1973. Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2nd edition, 2001. Google ScholarDigital Library
- I. Damgard and T. Toft. Trading sugar beet quotas - secure multiparty computation in practice. ERCIM News, 2008.Google Scholar
- W. Du and M. J. Atallah. Secure multi-party computation problems and their applications: A review and open problems. In New Security Paradigms Workshop, 2001. Google ScholarDigital Library
- C. Dwork. Differential privacy. In ICALP, 2006. Google ScholarDigital Library
- D. Eppstein, M. T. Goodrich, and R. Tamassia. Privacy-preserving data-oblivious geometric algorithms for geographic data. In 18th SIGSPATIAL, 2010. Google ScholarDigital Library
- S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Commun. ACM, 28(6), 1985. Google ScholarDigital Library
- J. Friedman, T. Hastie, and R. Tibshirani. The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer, 2nd edition, 2009.Google Scholar
- C. Gentry. Fully homomorphic encryption using ideal lattices. In STOC, 2009. Google ScholarDigital Library
- S. Goldwasser and M. Bellare. Lecture Notes on Cryptography. MIT, 2001.Google Scholar
- M. T. Goodrich. Randomized shellsort: A simple oblivious sorting algorithm. In SODA, 2010. Google ScholarDigital Library
- M. T. Goodrich. Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data. In SPAA, 2011. Google ScholarDigital Library
- T. Graepel, K. Lauter, and M. Naehrig. ML confidential: Machine learning on encrypted data. Cryptology ePrint Archive, Report 2012/323, 2012.Google Scholar
- R. Hall, S. E. Fienberg, and Y. Nardi. Secure multiple linear regression based on homomorphic encryption. J. Official Statistics, 2011.Google Scholar
- K. Hamada, R. Kikuchi, D. Ikarashi, K. Chida, and K. Takahashi. Practically efficient multi-party sorting protocols from comparison sort algorithms. In ICISC, 2013. Google ScholarDigital Library
- W. Henecka, S. Kogl, A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. TASTY: Tool for automating secure two-party computations. In CCS, 2010. Google ScholarDigital Library
- Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In USENIX Security, 2011. Google ScholarDigital Library
- Y. Huang, J. Katz, and D. Evans. Quid-pro-quo-tocols: Strengthening semi-honest protocols with dual execution. In IEEE S&P, 2012. Google ScholarDigital Library
- Y. Huang, L. Malka, D. Evans, and J. Katz. Efficient privacy-preserving biometric identification. In NDSS, 2011.Google Scholar
- Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In CRYPTO, 2003.Google ScholarCross Ref
- K. V. Jonsson, G. Kreitz, and M. Uddin. Secure multi-party sorting and applications. Cryptology ePrint Archive, Report 2011/122, 2011.Google Scholar
- A. F. Karr, W. J. Fulp, F. Vera, S. S. Young, X. Lin, and J. P. Reiter. Secure, privacy-preserving analysis of distributed databases. Technometrics, 2007.Google ScholarCross Ref
- A. F. Karr, X. Lin, A. P. Sanil, and J. P. Reiter. Privacy-preserving analysis of vertically partitioned data using secure matrix products. J. Official Statistics, 2009.Google Scholar
- R. H. Keshavan, A. Montanari, and S. Oh. Learning low rank matrices from O(n) entries. In Allerton, 2008.Google ScholarCross Ref
- D. E. Knuth. The Art Of Computer Programming | Volume 3 / Sorting and Searching. Addison-Wesley, 2nd edition, 1998. Google ScholarDigital Library
- V. Kolesnikov, A.-R. Sadeghi, and T. Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In CANS, 2009. Google ScholarDigital Library
- V. Kolesnikov and T. Schneider. Improved garbled circuit: Free XOR gates and applications. In ICALP, 2008. Google ScholarDigital Library
- Y. Koren, R. M. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. IEEE Computer, 2009. Google ScholarDigital Library
- B. Kreuter, A. Shelat, and C.-H. Shen. Billion-gate secure computation with malicious adversaries. In USENIX Security, 2012. Google ScholarDigital Library
- S. K. Lam, D. Frankowski, and J. Riedl. Do you trust your recommendations? An exploration of security and privacy issues in recommender systems. In ETRICS 2006, 2006. Google ScholarDigital Library
- S. K. Lam and J. Riedl. Shilling recommender systems for fun and profit. In WWW, 2004. Google ScholarDigital Library
- K. Lauter, M. Naehrig, and V. Vaikuntanathan. Can homomorphic encryption be practical? In CCSW, 2011. Google ScholarDigital Library
- Y. Lindell. Fast cut-and-choose based protocols for malicious and covert adversaries. IACR Cryptology ePrint Archive, 2013.Google Scholar
- Y. Lindell and B. Pinkas. Privacy preserving data mining. J. Cryptology, 2002.Google Scholar
- Y. Lindell and B. Pinkas. A proof of security of Yao's protocol for two-party computation. J. Cryptology, 2009. Google ScholarDigital Library
- Y. Lindell and B. Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. J. Cryptology, 2012.Google Scholar
- Y. Lindell, B. Pinkas, and N. P. Smart. Implementing two-party computation efficiently with security against malicious adversaries. In SCN, 2008. Google ScholarDigital Library
- D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay -- Secure two-party computation system. In USENIX Security, 2004. Google ScholarDigital Library
- F. McSherry and I. Mironov. Differentially private recommender systems: Building privacy into the Netfix prize contenders. In KDD, 2009. Google ScholarDigital Library
- B. Mobasher, R. Burke, R. Bhaumik, and C. Williams. Toward trustworthy recommender systems: An analysis of attack models and algorithm robustness. ACM Trans. Internet Techn., 7(4), 2007. Google ScholarDigital Library
- M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design. In 1st ACM Conference on Electronic Commerce, 1999. Google ScholarDigital Library
- A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparse datasets. In IEEE S&P, 2008. Google ScholarDigital Library
- V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft. Privacy-preserving ridge regression on hundreds of millions of records. In IEEE S&P, 2013. Google ScholarDigital Library
- K. Nissim and E. Weinreb. Communication efficient secure linear algebra. In TCC, 2006. Google ScholarDigital Library
- P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, 1999. Google ScholarDigital Library
- B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams. Secure two-party computation is practical. In ASIACRYPT, 2009. Google ScholarDigital Library
- N. Pippenger and M. J. Fischer. Relations among complexity measures. J. ACM, 26(2), 1979. Google ScholarDigital Library
- M. O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.Google Scholar
- O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. Google ScholarDigital Library
- A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Efficient privacy-preserving face recognition. In ICISC, 2009. Google ScholarDigital Library
- E. Shi, T.-H. H. Chan, E. G. Rieffel, R. Chow, and D. Song. Privacy-preserving aggregation of time-series data. In NDSS, 2011.Google Scholar
- Y. Tsiounis and M. Yung. On the security of ElGamal based encryption. In PKC, 1998. Google ScholarDigital Library
- G. Wang, T. Luo, M. T. Goodrich, W. Du, and Z. Zhu. Bureaucratic protocols for secure two-party sorting, selection, and permuting. In CCS, 2010. Google ScholarDigital Library
- U. Weinsberg, S. Bhagat, S. Ioannidis, and N. Taft. BlurMe: Inferring and obfuscating user gender based on ratings. In RecSys, 2012. Google ScholarDigital Library
- A. C.-C. Yao. Protocols for secure computations. In FOCS, 1982. Google ScholarDigital Library
- A. C.-C. Yao. How to generate and exchange secrets. In FOCS, 1986. Google ScholarDigital Library
Index Terms
- Privacy-preserving matrix factorization
Recommendations
Efficient Privacy-Preserving Matrix Factorization via Fully Homomorphic Encryption: Extended Abstract
ASIA CCS '16: Proceedings of the 11th ACM on Asia Conference on Computer and Communications SecurityRecommendation systems become popular in our daily life. It is well known that the more the release of users' personal data, the better the quality of recommendation. However, such services raise serious privacy concerns for users. In this paper, ...
Multi-linear interactive matrix factorization
A multi-linear interactive matrix factorization algorithm is introduced.The interactions between users and factors are empirically analyzed.Results show interactive factors significantly enhance recommendation performance. Recommender systems, which can ...
Attributes coupling based matrix factorization for item recommendation
Recommender systems have attracted lots of attention since they alleviate the information overload problem for users. Matrix factorization is one of the most widely employed collaborative filtering techniques in the research of recommender systems due ...
Comments