Paper 2019/470

A Practical Approach to the Secure Computation of the Moore-Penrose Pseudoinverse over the Rationals

Niek J. Bouman and Niels de Vreede

Abstract

We devise an efficient and data-oblivious algorithm for solving a bounded integral linear system of arbitrary rank over the rational numbers via the Moore-Penrose pseudoinverse, using finite-field arithmetic. This particular problem setting stems from our goal to run the algorithm as a secure multiparty computation (MPC). Beyond MPC, our algorithm could be valuable in other scenarios, like secure enclaves in CPUs, where data-obliviousness is crucial for protecting secrets. We compute the Moore-Penrose inverse over a finite field of sufficiently large order, so that we can recover the rational solution from the solution over the finite field. Previous work by Cramer, Kiltz and Padró (CRYPTO 2007) proposes a constant-rounds protocol for computing the Moore-Penrose pseudoinverse over a finite field. The asymptotic complexity (counted as the number of secure multiplications) of their solution is $O(m^4 + n^2 m)$, where $m$ and $n$, $m\leq n$, are the dimensions of the linear system. To reduce the number of secure multiplications, we sacrifice the constant-rounds property and propose a protocol for computing the Moore-Penrose pseudoinverse over the rational numbers in a linear number of rounds, requiring only $O(m^2n)$ secure multiplications. To obtain the common denominator of the pseudoinverse, required for constructing an integer-representation of the pseudoinverse, we generalize a result by Ben-Israel for computing the squared volume of a matrix. Also, we show how to precondition a symmetric matrix to achieve generic rank profile while preserving symmetry and being able to remove the preconditioner after it has served its purpose. These results may be of independent interest.