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 .