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
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 data-oblivious 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 Moore-Penrose pseudoinverse, using finite-field arithmetic. I.e., 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.
While we have designed the algorithm with an MPC context in mind, it could be valuable also in other contexts where data-obliviousness is required, like secure enclaves in CPUs.
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
Note: Minor revision
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. ACNS 2020
- Keywords
- secure multiparty computationsecure linear algebraMoore-Penrose pseudoinverseoblivious algorithms
- Contact author(s)
-
niek bouman @ rosemanlabs com
n d vreede @ tue nl - History
- 2020-04-23: last of 3 revisions
- 2019-05-10: 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 Moore-Penrose Pseudoinverse over the Rationals}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/470}, year = {2019}, url = {https://eprint.iacr.org/2019/470} }