Cryptology ePrint Archive: Report 2018/703

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 ]