Secure Multi-Party Linear Algebra with Perfect Correctness

ePrint Report: Secure Multi-Party Linear Algebra with Perfect Correctness

Jules Maire, Damien Vergnaud

We present new secure multi-party computation protocols for linear algebra over a finite field, which improve the state-of-the-art in terms of security. We look at the case of \emph{unconditional security with perfect correctness}, i.e., information-theoretic security without errors. We notably propose an expected constant-round protocol for solving systems of $m$ linear equations in $n$ variables over $\mathbb{F}_q$ with expected complexity $O(k(n^{2.5} + m^{2.5}+n^2m^{0.5}))$ where $k > m(m+n)+1$ …

algebra art case computation correctness eprint report errors information linear party perfect protocols report security state terms