Welcome to the resource topic for
**2018/703**

**Title:**

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

**Authors:**
Niek J. Bouman, Niels de Vreede

**Abstract:**

Cramer and Damg\aa{}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.

**ePrint:**
https://eprint.iacr.org/2018/703

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .