Nudge: A Private Recommendations Engine

Nudge is a recommender system with cryptographic privacy. A Nudge deployment consists of three infrastructure servers and many users, who retrieve/rate items from a large data set (e.g., videos, posts, businesses). Periodically, the Nudge servers collect ratings from users in secret-shared form, then run a three-party computation to train a lightweight recommender model on users' private ratings. Finally, the servers deliver personalized recommendations to each user. At every step, Nudge reveals nothing to the servers about any user's preferences beyond the aggregate model itself. User privacy holds against an adversary that compromises the entire secret state of one server. The technical core of Nudge is a new, three-party protocol for matrix factorization. On the Netflix data set with half a million users and ten thousand items, Nudge (running on three 192-core servers on a local-area network) privately learns a recommender model in 50 mins with 40 GB of server-to-server communication. On a standard quality benchmark (nDCG@20), Nudge scores 0.29 out of 1.0, on par with non-private matrix factorization and just shy of non-private neural recommenders, which score 0.31. This is because it alternates between two steps: (a) applying a secret-shared matrix to a secret-shared vector and (b) evaluating simple, non-linear functions on the intermediate results. Replicated secret sharing [20, 134] lets three parties execute step (a) non-interactively and at high speed, while function secret sharing [36, 37] makes it possible to run step (b) with low communication costs. By casting matrix factorization in this high-level framework, we ensure that the communication between servers scales linearly with the number of users and items-unlike prior cryptographic recommender protocols with up to three parties [111, 139, 142] . Along the way, we contribute special-purpose three-party protocols for the non-linear functions that Nudge relies on: truncation and normalization. Building on a rich literature in privacy-preserving machine learning [34, 42, 104, 150, 163, 167, 169] , we improve the efficiency of these protocols in Nudge's three-party setting: e.g., reducing the communication by 6× over state-of-the-art truncation [104]. Evaluation. We implement Nudge in Go and C. Nudge runs faster than prior recommender systems with cryptographic privacy: it outperforms two-party approaches based on garbled circuits by four orders of magnitude in communication and compute [139, 142] , and runs faster than a bespoke fourparty computation while using 8× less communication and one fewer non-colluding party [166] . We evaluate both Nudge's performance and quality on the Netflix prize data set with half a million users and tens of thousands of items [7] . Running on three 192-core machines on a local-area network, Nudge privately learns a recommender model in 50 min and 40 GB of server-to-server communication. After learning the recommendation model, each Nudge server can serve secret-shared recommendations to a user in hundreds of kilobytes of communication (298 KB on Netflix) and seconds of latency (0.38 s on Netflix). Nudge's resulting recommendations match those of cleartext matrix factorization in recall and rank-based metrics: on a standard quality benchmark (nDCG@20), Nudge and non-private matrixfactorization systems both score 0.29 out of 1.0, just shy of non-private deep neural recommenders, which score 0.31. Moreover, Nudge can scale larger yet: on a Criteo data set with millions of users and hundreds of ad campaigns [6], Nudge's private matrix factorization takes 1.5 h and 124 GB of server-to-server communication. On a Yelp data set with hundreds of thousands of users and hundreds of thousands of businesses [8], Nudge takes 8 h and 250 GB. Extensions. Finally, we propose a number of extensions that enhance Nudge's performance, security guarantees, and functionality. To scale larger yet, we show how to compose Nudge with classic dimensionality-reduction techniques [105, 145] . To complement its privacy protections, Nudge integrates with well-studied mechanisms that make the model and the recommendations that it outputs differentially private [67, 131] . To defend against disruptions by malicious users, the Nudge servers run a lightweight, one-time well-formedness check on all user submissions, in a way that is almost free in our three-party setting [10, 55] . Lastly, while we present Nudge as a recommender system, algorithms for computing the top eigenvectors of a matrix form the backbone of a wide array of unsupervised learning and data-mining tasks [96] . Our new private poweriteration routine can extend to these same applications: principal component analysis [83] , learning low-dimensional embeddings [33, 62, 145] , link analysis using PageRank [90, 144] , graph analysis and spectral clustering [120] , and data compression [102, 107] . Nudge shows the possibility of performing these tasks on large secret-shared matrices, da