R. Cramer, E. Kiltz, C.
Padró
A Note on Secure Computation of the
Moore-Penrose Pseudoinverse and Its Application to Secure Linear Algebra
Advances in Cryptology, Crypto 2007.
Lecture Notes in Computer Science 4622 (2007) 613-630
Abstract
This work deals with the communication complexity of secure
multi-party protocols for linear algebra problems. In our model,
complexity is measured in terms of the number of secure multiplications
required and protocols terminate within a constant number of rounds of
communication.
Previous work by Cramer and Damgård proposes secure protocols for
solving systems $Ax = b$ of $m$ linear equations in $n$ variables over
a finite field, with $m \leq n$. The complexity of those protocols is
$n^5$.
We show a new upper bound of $m^4 + n^2 m$ secure multiplications for
this problem, which is clearly asymptotically smaller. Our main point,
however, is that the advantage can be substantial in case $m$ is much
smaller than $n$. Indeed, if $m={\sqrt{n}}$ , for example, the
complexity goes down from $n^5$ to $n^2.5$.
Our secure protocols rely on some recent advances concerning the
computation of the Moore-Penrose pseudo-inverse of matrices over fields
of positive characteristic. These computations are based on the
evaluation of a certain characteristic polynomial, in combination with
variations on a well-known technique due to Mulmuley that helps to
control the effects of non-zero characteristic. We also introduce a new
method for secure polynomial evaluation that exploits properties of
Chebychev polynomials, as well as a new secure protocol for computing
the characteristic polynomial of a matrix based on Leverrier’s lemma
that exploits this new method.