Paper 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\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.

Note: Corrected a misleading typo in Protocol 2a

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
secure linear algebramultiparty computation
Contact author(s)
n j bouman @ tue nl
History
2018-08-22: revised
2018-08-01: received
See all versions
Short URL
https://ia.cr/2018/703
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/703,
      author = {Niek J.  Bouman and Niels de Vreede},
      title = {New Protocols for Secure Linear Algebra: Pivoting-Free Elimination and Fast Block-Recursive Matrix Decomposition},
      howpublished = {Cryptology ePrint Archive, Paper 2018/703},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/703}},
      url = {https://eprint.iacr.org/2018/703}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.