Paper 2019/470
A Practical Approach to the Secure Computation of the MoorePenrose Pseudoinverse over the Rationals
Niek J. Bouman and Niels de Vreede
Abstract
Solving linear systems of equations is a universal problem. In the context of secure multiparty computation (MPC), a method to solve such systems, especially for the case in which the rank of the system is unknown and should remain private, is an important building block. We devise an efficient and dataoblivious algorithm (meaning that the algorithm's execution time and branching behavior are independent of all secrets) for solving a bounded integral linear system of unknown rank over the rational numbers via the MoorePenrose pseudoinverse, using finitefield arithmetic. I.e., we compute the MoorePenrose inverse over a finite field of sufficiently large order, so that we can recover the rational solution from the solution over the finite field. While we have designed the algorithm with an MPC context in mind, it could be valuable also in other contexts where dataobliviousness is required, like secure enclaves in CPUs. Previous work by Cramer, Kiltz and Padró (CRYPTO 2007) proposes a constantrounds protocol for computing the MoorePenrose 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 constantrounds property and propose a protocol for computing the MoorePenrose 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 integerrepresentation of the pseudoinverse, we generalize a result by BenIsrael 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.
Note: Minor revision
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. MINOR revision.ACNS 2020
 Keywords
 secure multiparty computationsecure linear algebraMoorePenrose pseudoinverseoblivious algorithms
 Contact author(s)

niek bouman @ rosemanlabs com
n d vreede @ tue nl  History
 20200423: last of 3 revisions
 20190510: received
 See all versions
 Short URL
 https://ia.cr/2019/470
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/470, author = {Niek J. Bouman and Niels de Vreede}, title = {A Practical Approach to the Secure Computation of the MoorePenrose Pseudoinverse over the Rationals}, howpublished = {Cryptology ePrint Archive, Paper 2019/470}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/470}}, url = {https://eprint.iacr.org/2019/470} }