Privacy-Preserving Distributed Linear Regression on High-Dimensional Data

By Adrià Gascón, Phillipp Schoppmann, Borja Balle, Mariana Raykova, Jack Doerner, Samee Zahur, David E. Evans. 2017

228 citations recorded by the source corpus.

Abstract We propose privacy-preserving protocols for computing linear regression models, in the setting where the training dataset is vertically distributed among several parties. Our main contribution is a hybrid multi-party computation protocol that combines Yao’s garbled circuits with tailored protocols for computing inner products. Like many machine learning tasks, building a linear regression model involves solving a system of linear equations. We conduct a comprehensive evaluation and comparison of different techniques for securely performing this task, including a new Conjugate Gradient Descent (CGD) algorithm. This algorithm is suitable for secure computation because it uses an efficient fixed-point representation of real numbers while maintaining accuracy and convergence rates comparable to what can be obtained with a classical solution using floating point numbers. Our technique improves on Nikolaenko et al.’s method for privacy-preserving ridge regression (S&P 2013), and can be used as a building block in other analyses. We implement a complete system and demonstrate that our approach is highly scalable, solving data analysis problems with one million records and one hundred features in less than one hour of total running time.

Subfields: Artificial Intelligence, Federated & Distributed Learning, 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 Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “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].”
Federated Learning and Differential Privacy: Software tools analysis, the Sherpa.ai FL framework and methodological guidelines for preserving data privacy (2020, methodology): “Among such machine learning models we cite neural networks [31], linear [32, 33] and logistic [34] regression.”
QUOTIENT: Two-Party Secure Neural Network Training and Prediction (2019, methodology): “encryption and garbled circuits, while previous works [14, 41] rely in part on OT for the same functionality.”
Entity Resolution and Federated Learning get a Federated Resolution (2018, methodology): “1 Introduction With the ever-expanding collection of data, it is becoming common practice for organisations to cooperate with the objective of leveraging their joint collections of data [12, 13], with a wider The Australian National University & the University of Sydney Now with the University of Am”
Blind Justice: Fairness with Encrypted Sensitive Attributes (2018, methodology): “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 (Mo-hassel & Zhang, 2017; Gasc´on et al., 2017; Nikolaenko et al., 2013b; Al-Rubaie et al., 2017).”
Private Nearest Neighbors Classification in Federated Databases (2018, methodology): “The inner product of ã and b̃ can then be computed using a standard MPC protocol (Mohassel & Zhang, 2017; Gascón et al., 2017).”
Trustworthy AI: From Principles to Practices (2021, background): “, linear regression [128] and logistic regression [300], and generic model learning tasks [247].”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, background): “This is a very common assumption in the two-server model [45, 46, 48, 67, 80, 83, 84].”
ML-Leaks: Model and Data Independent Membership Inference Attacks and Defenses on Machine Learning Models (2018, background): “Another relevant line of work is privacy-preserving machine learning [6], [9]–[11], [13], [14], [17], [18], [25], [29].”
PrivEdge: From Local to Distributed Private Training and Prediction (2020, methodology): “To address these issues, the so-called 2-server MPC model can be used [24], [26]–[28].”
Privacy-Preserving Multiple Linear Regression of Vertically Partitioned Real Medical Datasets (2017, background): “scheme Nikolaenko [15] Gascon [14] Aono [16] Ours Partition holizontal virtical virtical virtical building Paillier enc.”
Language Models are Realistic Tabular Data Generators (2022, background): “…(Cao et al., 2019)), (ii) contain critical person-related information and cannot be shared due to privacy protection or socio-ethical principles (Gasc´on et al., 2017), and (iii) often come with impurity issues such as noisy or missing values which impede the application of modern ML algorithms…”
A Survey on federated learning* (2020, background): “Generally, scholars deal with this problem through taking out the same entities with various characteristics to get a joint training [14].”
A review of applications in federated learning (2020, background): “By contrast with horizontal FL, it is a more challenging work due to entity resolution(Gascón et al., 2017).”
DarKnight: A Data Privacy Scheme for Training and Inference of Deep Neural Networks (2020, background): “Such an approach limits their usage to integer arithmetic on quantized models (Mohassel & Zhang, 2017; Gascón et al., 2017; So et al., 2019).”
Secure Computation for Machine Learning With SPDZ (2019, methodology): “We also compared the root mean squared error (RMSE) of SGD on 9 UCI open-sourced datasets of ranging sizes to results in [2].”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “Instead, hybrid approaches have been designed that combine MPC with homomorphic encryption (Nikolaenko et al., 2013b; Gascón et al., 2017) or develop custom protocols to perform secure arithmetic operations efficiently (Mohassel and Zhang, 2017).”
SoK: General Purpose Compilers for Secure Multi-Party Computation (2019, methodology): “Several groups have used Obliv-C to implement secure functionalities, including linear regression [62], decentralized certificate authorities [83], aggregated private machine-learning models [119], classification of encrypted emails [70] and stable matching [49].”