Welcome to the resource topic for 2024/508
Title:
Secure Multi-Party Linear Algebra with Perfect Correctness
Authors: Jules Maire, Damien Vergnaud
Abstract:We present new secure multi-party computation protocols for linear algebra over a finite field, which improve the state-of-the-art in terms of security. We look at the case of \emph{unconditional security with perfect correctness}, i.e., information-theoretic security without errors. We notably propose an expected constant-round protocol for solving systems of m linear equations in n variables over \mathbb{F}_q with expected complexity O(k(n^{2.5} + m^{2.5}+n^2m^{0.5})) where k > m(m+n)+1 (complexity is measured in terms of the number of secure multiplications required). The previous proposals were not error-free: known protocols can indeed fail and thus reveal information with probability \Omega(\textsf{poly}(m)/q).
Our protocols are simple and rely on existing computer-algebra techniques, notably the Preparata-Sarwate algorithm, a simple but poorly known ``baby-step giant-step’’ method for computing the characteristic polynomial of a matrix, and techniques due to Mulmuley for error-free linear algebra in positive characteristic.
ePrint: https://eprint.iacr.org/2024/508
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 .