Efficient Secure Ridge Regression from Randomized Gaussian Elimination

In this paper we present practical protocols for secure ridge regression. We develop the necessary secure linear algebra tools, using only basic arithmetic over prime fields. In particular, we will show how to solve linear systems of equations and compute matrix inverses efficiently, using appropriate secure random self-reductions of these problems. The distinguishing feature of our approach is that the use of secure fixed-point arithmetic is avoided entirely, while circumventing the need for secure rational reconstruction at any stage as well. In fact, in recent follow-up works, our results have already been applied and extended to several other settings. We demonstrate the potential of our protocols in a standard setting for information-theoretically secure multiparty computation, tolerating a dishonest minority of passively corrupt parties. Using the MPyC framework, which is based on threshold secret sharing over finite fields, we show how to handle large datasets efficiently, achieving practically the same root-mean-square errors as Scikit-learn. Moreover, our protocols are designed with the outsourcing scenario in mind, which makes our protocols much more versatile than existing solutions. In the outsourcing scenario one does not assume that (any part of) the dataset is held privately by any of the parties performing the multiparty computation—in contrast to federated learning, for instance, where the dataset is partitioned either horizontally or vertically between these parties.