|
In this work we present secure two-party protocols for various
core problems in linear algebra. \remove{One of our results -
ENAV} Our main result is a protocol to obliviously decide
singularity of an encrypted matrix: Bob holds an $n \times n$
matrix, encrypted with Alice's secret key, and wants to learn
whether or not the matrix is singular (while leaking nothing
further). We give an interactive protocol between Alice and Bob
that solves the above problem in $O(\log n)$ communication rounds
and with overall communication complexity of roughly $O(n^2)$
(note that the input size is $n^2$). Our techniques exploit
certain nice mathematical properties of linearly recurrent
sequences and their relation to the minimal and characteristic
polynomial of the input matrix, following [Wiedemann, 1986]. With
our new techniques we are able to improve the round complexity of
the communication efficient solution of [Nissim and Weinreb,
2006] from $O(n^{0.275})$ to $O(\log n)$.
At the core of our results we use a protocol that securely
computes the minimal polynomial of an encrypted matrix. Based on
this protocol we exploit certain algebraic reductions to further
extend our results to the problems of securely computing rank and
determinant, and to solving systems of linear equations (again
with low round and communication complexity).
|