Privacy-Preserving Ridge Regression on Hundreds of Millions of Records

By Valeria Nikolaenko, Udi Weinsberg, Stratis Ioannidis, Marc Joye, Dan Boneh, Nina Taft. 2013

490 citations recorded by the source corpus.

Ridge regression is an algorithm that takes as input a large number of data points and finds the best-fit linear curve through these points. The algorithm is a building block for many machine-learning operations. We present a system for privacy-preserving ridge regression. The system outputs the best-fit curve in the clear, but exposes no other information about the input data. Our approach combines both homomorphic encryption and Yao garbled circuits, where each is used in a different part of the algorithm to obtain the best performance. We implement the complete system and experiment with it on real data-sets, and show that it significantly outperforms pure implementations based only on homomorphic encryption or Yao circuits.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Optimization & Training, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Optimization & Training

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “As such a noticeable trend in research has consisted in designing custom protocols for applications such as linear and logistic regression [309, 172, 302] and neural network training and inference [302, 14, 46].”
QUOTIENT: Two-Party Secure Neural Network Training and Prediction (2019, neutral): “[44] propose a protocol for secure distributed ridge regression that combines additive homomorphic”
Federated Machine Learning (2019, methodology): “ssion and classification. Ref [68] proposed secure multi-party gradient descent methods. The above works all used secure multi-party computation (SMC) [25,72] for privacy guarantees. Nikolaenko et al.[48] implemented a privacy-preserving protocol for linear regression on horizontally partitioned dat”
Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware (2018, background): “, in the latter two where the computation is performed locally by the data owner), the need for integrity is a common denominator, and this is the property we primarily focus on in this paper (and for which we obtain the best results!) Cryptography can address some of these problems [17, 32, 3, 38, ”
Privacy-Preserving Distributed Linear Regression on High-Dimensional Data (2017, methodology): “’s work [59] on secure computation for linear regression is the one most similar to ours.”
Federated Learning: Challenges, Methods, and Future Directions (2019, methodology): “Beyond differential privacy, homomorphic encryption can be used to secure the learning process by computing on encrypted data, although it has currently been applied in limited settings, e.g., training linear models [82] or involving only a few entities [133].”
Crypto-Nets: Neural Networks over Encrypted Data (2014, methodology): “…studied how to do HE-based privacy-preserving training or prediction of linear regression (Nikolaenko et al., 2013b; Wu & Haven, 2012), linear classiﬁers (Bos et al., 2014; Bost et al., 2014; Graepel et al., 2013), decision trees (Bost et al., 2014), matrix factorization (Nikolaenko et al., 2013a).”
Making AI Forget You: Data Deletion in Machine Learning (2019, background): “cryptography [63, 16, 14, 13, 62, 31], and differential privacy [30, 21, 20, 64, 1] — do not lead to efficient data deletion, but rather attempt to make data private or non-identifiable.”
Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications (2018, methodology): “Y [46] is a compiler that can generate mixed protocols based on GC and homomorphic encryption. Several applications have been built that use mixed protocols, e.g., privacy-preserving ridge-regression [74], matrix factorization [74], iris and finger-code authentication [17], and medical diagnostics [”
Entity Resolution and Federated Learning get a Federated Resolution (2018, methodology): “The interest in focusing on Ridge-regularized Taylor losses is three-folds: (i) we are trivially able to compute the optimum of such losses given the constraints imposed on Theorem 3; we thus get access to a fine-grained analysis of θ∗T ; (ii) our fine-grained bounds are directly relevant to the num”
Blind Justice: Fairness with Encrypted Sensitive Attributes (2018, methodology): “(cid:104) (cid:105) (cid:104) (cid:105) The idea of privately outsourcing computation to two non-colluding parties in this way is recurrent in MPC, and often referred to as the two-server model (Mohassel & Zhang, 2017; Gasc´on et al., 2017; Nikolaenko et al., 2013b; Al-Rubaie et al., 2017).”
Verifying computations with state (2013, methodology): “The third application is regression analysis (again inspired by prior work that requires a custom protocol [56]); the prover holds a set of patient files, the verifier is an analyst seeking to fit a model to this data, and the computation returns the best-fit parameters.”
GraphSC: Parallel Secure Computation Made Easy (2015, unknown): “In this work, we follow the second approach to enable parallel oblivious versions for a range of data mining algorithms.”
Privacy-Preserving Classification on Deep Neural Network (2017, background): “They may be classified according to the learning algorithms which are involved: linear regression training or prediction [35], [47], linear classifiers [7], [8], [22], decision trees [8] or neural networks”
Fast, Privacy Preserving Linear Regression over Distributed Datasets based on Pre-Distributed Data (2015, background): “The online phase is orders of magnitude faster when compared to previous solutions in the literature [26, 19].”
CrypTFlow: Secure TensorFlow Inference (2019, background): “Although the use of fixed-point for secure computations is well-known [68], prior works on secure inference have addressed the float-to-fixed problem by either generating a fixed-point model by hand ([62], [55], [49], [60], [79], [58], [72]), or by using non-standard training algorithms that output ”
Secure SVM Training Over Vertically-Partitioned Datasets Using Consortium Blockchain for Vehicular Social Networks (2020, methodology): “[24] design a privacy-preserving ridge regression algorithm which can be divided into two phases and each phase uses homomorphic encryption and Yao garbled circuits separately.”
Distributed Learning without Distress: Privacy-Preserving Empirical Risk Minimization (2018, background): “A recent focus has been to achieve practical and efficient distributed machine learning using MPC protocols [12, 52, 34], and in certain settings such methods have been shown to scale to learning tasks with hundreds of millions of records [39, 21].”