The DOI matches its Crossref record; 57 of the 57 references it cites were found in a registry or an index.
Privacy-preserving matrix factorization
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Elements of Statistical Learning
Hastie, T., Tibshirani, R., & Friedman, J. (2009) · Springer Series in Statistics · doi:10.1007/978-0-387-84858-7 · Cited by 25,970
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
Matrix Factorization Techniques for Recommender Systems
Koren, Y., Bell, R., & Volinsky, C. (2009) · Computer · doi:10.1109/mc.2009.263 · Cited by 11,673
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Paillier, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_16 · Cited by 7,250
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806 · cited 1×
“Non-linear computation through fully homomorphic encryption [16] may be used to reduce the workload on the CSP compared to garbled circuits, but current FHE schemes [39, 20] for simpler algebraic computations are not as efficient as garbled circuit approaches [50].”
MethodDwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
The Art of Computer Programming: Volume 3: Sorting and Searching
Knuth, D. E. (1973) · Cited by 3,955
How to generate and exchange secrets
Yao, A. C.-C. (1986) · 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) · doi:10.1109/sfcs.1986.25 · Cited by 3,733
Protocols for secure computations
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.88 · Cited by 2,661
Sorting networks and their applications
Batcher, K. E. (1968) · Proceedings of the April 30--May 2, 1968, spring joint computer conference on - AFIPS '68 (Spring) · doi:10.1145/1468075.1468121 · Cited by 2,417
Robust De-anonymization of Large Sparse Datasets
Narayanan, A., & Shmatikov, V. (2008) · 2008 IEEE Symposium on Security and Privacy (sp 2008) · doi:10.1109/sp.2008.33 · Cited by 2,372
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315
A Randomized Protocol for Signing Contracts
Even, S., Goldreich, O., & Lempel, A. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_19 · Cited by 1,450
The art of computer programming, volume 3: (2nd ed.) sorting and searching
Knuth, D. E. (1998) · Addison-Wesley Longman Publishing Co., Inc. eBooks · Cited by 1,421
Can homomorphic encryption be practical?
Naehrig, M., Lauter, K., & Vaikuntanathan, V. (2011) · Proceedings of the 3rd ACM workshop on Cloud computing security workshop · doi:10.1145/2046660.2046682 · Cited by 1,004
Fairplay—a secure two-party computation system
Malkhi, D., Nisan, N., Pinkas, B., & Sella, Y. (2004) · USENIX Security Symposium · Cited by 846
Privacy preserving auctions and mechanism design
Naor, M., Pinkas, B., & Sumner, R. (1999) · Proceedings of the 1st ACM conference on Electronic commerce · doi:10.1145/336992.337028 · Cited by 753
Extending Oblivious Transfers Efficiently
Ishai, Y., Kilian, J., Nissim, K., & Petrank, E. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_9 · Cited by 746
Improved Garbled Circuit: Free XOR Gates and Applications
Kolesnikov, V., & Schneider, T. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70583-3_40 · Cited by 743
Secure Two-Party Computation Is Practical
Pinkas, B., Schneider, T., Smart, N. P., & Williams, S. C. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10366-7_15 · Cited by 711
Privacy Preserving Data Mining
Lindell, & Pinkas (2002) · Journal of Cryptology · doi:10.1007/s00145-001-0019-2 · Cited by 668
Differentially private recommender systems: Building privacy into the Netflix Prize contenders
McSherry, F., & Mironov, I. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557090 · Cited by 664
A Proof of Security of Yao’s Protocol for Two-Party Computation
Lindell, Y., & Pinkas, B. (2009) · Journal of Cryptology · doi:10.1007/s00145-008-9036-8 · Cited by 651
Shilling recommender systems for fun and profit
Lam, S. K., & Riedl, J. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988726 · Cited by 635
Faster Secure Two-Party Computation Using Garbled Circuits
Huang, Y., Evans, D., Katz, J. I., & Malka, L. (2011) · doi:10.18130/v3hj5c · Cited by 532
Toward trustworthy recommender systems: An analysis of attack models and algorithm robustness
Mobasher, B., Burke, R., Bhaumik, R., & Williams, C. (2007) · ACM Transactions on Internet Technology · doi:10.1145/1278366.1278372 · Cited by 458
Secure multi-party computation problems and their applications: a review and open problems
Du, W., & Atallah, M. J. (2001) · Proceedings of the 2001 workshop on New security paradigms · doi:10.1145/508171.508174 · Cited by 453
Collaborative filtering with privacy
Canny, J. (2005) · Proceedings 2002 IEEE Symposium on Security and Privacy · doi:10.1109/secpri.2002.1004361 · Cited by 442
Privacy-Preserving Ridge Regression on Hundreds of Millions of Records
Nikolaenko, V., Weinsberg, U., Ioannidis, S., Joye, M., Boneh, D., & Taft, N. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.30 · Cited by 439
Self-citationML Confidential: Machine Learning on Encrypted Data
Graepel, T., Lauter, K., & Naehrig, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-37682-5_1 · Cited by 423
Relations Among Complexity Measures
Pippenger, N., & Fischer, M. J. (1979) · Journal of the ACM · doi:10.1145/322123.322138 · Cited by 387
On the security of ElGamal based encryption
Tsiounis, Y., & Yung, M. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054019 · Cited by 380
Efficient Privacy-Preserving Face Recognition
Sadeghi, A.-R., Schneider, T., & Wehrenberg, I. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14423-3_16 · Cited by 363
TASTY: tool for automating secure two-party computations
Henecka, W., K ögl, S., Sadeghi, A.-R., Schneider, T., & Wehrenberg, I. (2010) · Proceedings of the 17th ACM conference on Computer and communications security · doi:10.1145/1866307.1866358 · Cited by 356
Non-Interactive Oblivious Transfer and Applications
Bellare, M., & Micali, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_48 · Cited by 297
Goldwasser, S., & Bellare, M. (1996) · Cited by 266
Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima
Kolesnikov, V., Sadeghi, A.-R., & Schneider, T. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10433-6_1 · Cited by 263
Efficient Privacy-Preserving Biometric Identification
Huang, Y., Malka, L., Evans, D., & Katz, J. I. (2011) · Cited by 181
Lam, S. K. “., Frankowski, D., & Riedl, J. (2006) · Lecture Notes in Computer Science · doi:10.1007/11766155_2 · Cited by 176
(2012) · doi:10.1145/2365952.2365989 · Cited by 170 · cited 1×
“This requirement is key: earlier studies [61] show that even knowing which movie a user has rated can be used to infer, e.”
BackgroundSelf-citationFast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries
Lindell, Y. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40084-1_1 · Cited by 147
Privacy Preserving Analysis of Vertically Partitioned Data Using Secure Matrix Products
Karr, A. F., Karr, A. F., Lin, X., Lin, X., Reiter, J. P., & Sanil, A. P. (2004) · Cited by 144
Implementing Two-Party Computation Efficiently with Security Against Malicious Adversaries
Lindell, Y., Benny Pinkas, B., & Smart, N. P. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85855-3_2 · Cited by 142
Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer
Lindell, Y., & Benny Pinkas, B. (2011) · Journal of Cryptology · doi:10.1007/s00145-011-9107-0 · Cited by 128
Alambic: a privacy-preserving recommender system for electronic commerce
Aïmeur, E., Brassard, G., Fernandez, J. M., & Onana, F. S. M. (2008) · International Journal of Information Security · doi:10.1007/s10207-007-0049-3 · Cited by 122
Secure multiple linear regression based on homomorphic encryption
Hall, R., Fienberg, S. E., & Nardi, Y. (2011) · Cited by 109
Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution
Huang, Y., Katz, J., & Evans, D. (2012) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2012.43 · Cited by 102
Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms
Hamada, K., Kikuchi, R., Ikarashi, D., Chida, K., & Takahashi, K. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-37682-5_15 · Cited by 88
Secure, Privacy-Preserving Analysis of Distributed Databases
Karr, A. F., Fulp, W. J., Vera, F., et al. (2007) · Technometrics · doi:10.1198/004017007000000209 · Cited by 70
Secure Multi-Party Sorting and Applications
Jónsson, K. V., Kreitz, G., & Uddin, M. (2011) · Cited by 59
Goodrich, M. T. (2011) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1989493.1989555 · Cited by 57
Bureaucratic protocols for secure two-party sorting, selection, and permuting
Wang, G., Luo, T., Goodrich, M. T., Du, W. K., & Zhu, Z. (2010) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/1755688.1755716 · Cited by 37
Encoding-Free ElGamal Encryption Without Random Oracles
Chevallier-Mames, B., Paillier, P., & Pointcheval, D. (2006) · Lecture notes in computer science · doi:10.1007/11745853_7 · Cited by 35
Communication Efficient Secure Linear Algebra
Kobbi Nissim, B., & Weinreb, E. (2006) · Lecture notes in computer science · doi:10.1007/11681878_27 · Cited by 26
Cited by
SecureML: A System for Scalable Privacy-Preserving Machine Learning
Mohassel, P., & Zhang, Y. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.12 · Cited by 1,936
“It has also been utilized in prior work on privacy-preserving machine learning [37], [36], [21].”
MethodABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation
Demmler, D., Schneider, T., & Zohner, M. (2015) · Proceedings 2015 Network and Distributed System Security Symposium · doi:10.14722/ndss.2015.23113 · Cited by 827
Secure Federated Matrix Factorization
Chai, D., Wang, L., Chen, K., & Yang, Q. (2021) · IEEE Intelligent Systems · doi:10.1109/mis.2020.3014880 · Cited by 449
SecureNN: 3-Party Secure Computation for Neural Network Training
Wagh, S., Gupta, D., & Chandran, N. (2019) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2019-0035 · Cited by 413
A Pragmatic Introduction to Secure Multi-Party Computation
Evans, D., Kolesnikov, V., & Rosulek, M. (2018) · Foundations and Trends® in Privacy and Security · doi:10.1561/3300000019 · Cited by 321
Metadata
- Authors
- Nikolaenko, V., Ioannidis, S., Weinsberg, U., Joye, M., Taft, N., & Boneh, D.
- Venue
- Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13
- Publisher
- ACM Press
- Published
- 2013
- Pages
- 801-812
- OpenAlex
- W2167094273
- Cited by
- 271
- References
- 57
- FWCI
- 11.06
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.