**New Protocols for Secure Linear Algebra: Pivoting-Free Elimination and Fast Block-Recursive Matrix Decomposition**

*Niek J. Bouman and Niels de Vreede*

**Abstract: **Cramer and Damgård were the first to propose a constant-rounds protocol for securely solving a linear system of unknown rank over a finite field in multiparty computation (MPC). For $m$ linear equations and $n$ unknowns, and for the case $m\leq n$, the computational complexity of their protocol is $O(n^5)$. Follow-up work (by Cramer, Kiltz, and Padró) proposes another constant-rounds protocol for solving this problem, which has complexity $O(m^4+n^2 m)$. For certain applications, such asymptotic complexities might be prohibitive. In this work, we improve the asymptotic computational complexity of solving a linear system over a finite field, thereby sacrificing the constant-rounds property. We propose two protocols: (1) a protocol based on pivoting-free Gaussian elimination with computational complexity $O(n^3)$ and linear round complexity, and (2) a protocol based on block-recursive matrix decomposition, having $O(n^2)$ computational complexity (assuming ``cheap'' secure inner products as in Shamir's secret-sharing scheme) and $O(n^{1.585})$ (super-linear) round complexity.

**Category / Keywords: **cryptographic protocols / secure linear algebra, multiparty computation

**Date: **received 25 Jul 2018, last revised 22 Aug 2018

**Contact author: **n j bouman at tue nl

**Available format(s): **PDF | BibTeX Citation

**Note: **Corrected a misleading typo in Protocol 2a

**Version: **20180822:100725 (All versions of this report)

**Short URL: **ia.cr/2018/703

[ Cryptology ePrint archive ]