Paper 2024/503

Weakly Super-Invertible Matrices and Constant Communication Dishonest Majority MPC

Abstract

In recent years, there has been tremendous progress in improving the concrete communication complexity of dishonest majority MPC. In the sub-optimal corruption threshold setting where $t<(1-\epsilon )\cdot n$ for some constant $0<\epsilon \le 1/2$, Sharing Transformation (Goyal $\mathit{\text{et al.}}$, CRYPTO'22) and SuperPack (Escudero $\mathit{\text{et al.}}$, EUROCRYPT'23) presented protocols with information-theoretic online phases requiring $O(1)$ field elements of total communication per multiplication gate. However, Sharing Transformation assumes that their offline phase is instantiated by a trusted party, while SuperPack instantiates their offline phase with large communication of $\mathrm{\Omega }(n)$ per multiplication gate assuming oblivious linear evaluation (OLE) correlations. The main bottleneck in instantiating the offline phases of both protocols is generating random packed beaver triples of the form $$, for random $$, and $$, where $$ is the $$. To address this bottleneck, our main technical contribution is introducing and constructing $$ super-invertible matrices, a relaxation of super-invertible matrices in which sub-matrices have high (but not necessarily full) rank. This relaxation allows for matrices with only $$ non-zero entries, enabling a first step towards generating packed beaver triples with $$ total communication per underlying triple, assuming OLE correlations. As the second (and final) step, we use the efficient $$ protocol of (Choudhury and Patra, Trans. Inform. Theory '17). We also implement our packed beaver triple protocol and provide experimental results. Our new protocol obtains up to 38% smaller communication and 9% reduction in runtime compared to SuperPack's triple protocol. Additionally, by instantiating SuperPack's offline phase with our new protocol, we obtain up to 16% communication reductions. Finally, we use our packed beaver triple protocol to instantiate the offline phase of Sharing Transformation, yielding a dishonest majority MPC protocol with $$ total communication across both the offline and online phases.

Note: Added concrete instantiations and experiments as well as some minor revisions.