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-\varepsilon)\cdot n$ for some constant $0<\varepsilon\leq 1/2$, Sharing Transformation (Goyal $\textit{et al.}$, CRYPTO'22) and SuperPack (Escudero $\textit{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 $\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 $[\mathbf{a}],[\mathbf{b}],[\mathbf{c}]$, for random $\mathbf{a},\mathbf{b}\in\mathbb{F}^k$, and $\mathbf{c}=\mathbf{a}*\mathbf{b}\in\mathbb{F}^k$, where $k=\Omega(n)$ is the $\textit{packing parameter}$. To address this bottleneck, our main technical contribution is introducing and constructing $\textit{weakly}$ 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 $\widetilde{O}(n)$ non-zero entries, enabling a first step towards generating packed beaver triples with $\widetilde{O}(1)$ total communication per underlying triple, assuming OLE correlations. As the second (and final) step, we use the efficient $\textit{triple extraction}$ 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 $\widetilde{O}(|C|)$ total communication across both the offline and online phases.

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