Privacy-Preserving Ridge Regression on Hundreds of Millions of Records

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

Abstract

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.
BibTeX
@inproceedings{nikolaenko2013privacy,
  author = {Valeria Nikolaenko and Udi Weinsberg and Stratis Ioannidis and Marc Joye and Dan Boneh and Nina Taft},
  title = {{Privacy-Preserving Ridge Regression on Hundreds of Millions of Records}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2013},
  doi = {10.1109/sp.2013.30},
}

Loading related content...

Figure