International Association for Cryptologic Research

International Association
for Cryptologic Research


Secure Multi-Party Linear Algebra with Perfect Correctness

Jules Maire , Sorbonne Université, CNRS, LIP6
Damien Vergnaud , Sorbonne Université, CNRS, LIP6
DOI: 10.62056/avzojbkrz
Search ePrint
Search Google

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 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 Fq with expected complexity O(k n^2.5 + k m) (where complexity is measured in terms of the number of secure multiplications required) with k > m(m+n)+1. The previous proposals were not error-free: known protocols can indeed fail and thus reveal information with probability Omega(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.

  title={Secure Multi-Party Linear Algebra with Perfect Correctness},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 1},
  author={Jules Maire and Damien Vergnaud},