Paper 2026/1948

Honest Majority MPC Achieving GOD with $O(|C|)$ Communication From Pairwise Random OLE Correlations

Abstract

In this work, we study the communication complexity of information-theoretic MPC with guaranteed output delivery (GOD) in the honest majority setting $(t<n/2)$. The recent work by Song and Ye (EUROCRYPT 2025) gives an honest majority MPC in the random oblivious linear evaluation (OLE) preprocessing model that computes an arithmetic circuit of size $|C|$ with malicious security with abort at the cost of $O(|C|)$ of both communication in field elements and total number of random OLE correlations. We explore the possibility of deriving a similar result for the stronger security notion of GOD. Specifically, we ask the question: `` Is it possible to construct an information-theoretic honest majority MPC in the random OLE preprocessing model that computes an arithmetic circuit of size $|C|$ and achieves GOD with $O(|C|)$ field elements of communication and $O(|C|)$ amount of random OLE correlations in total? '' We resolve the above question in the affirmative by providing a concrete construction. To achieve our result, we mainly rely on two techniques. First, we propose a new secret sharing scheme which we refer to as detectable secret sharing. It is a packed secret sharing scheme with an authentication mechanism. Second, to efficiently verify the computation and locate an error when faults occur, we extensively make use of the virtual transcript technique introduced in the work by Goyal, Song, and Zhu (CRYPTO 2020). Our construction is in the random OLE preprocessing model where we assume random OLEs between each pair of parties. By instantiating the random OLEs from various assumptions, we obtain three honest majority MPC protocols with GOD with the following security and communication: (1) the first one achieves information-theoretic security with offline communication of $O(|C|n)$ elements and online communication of $O(|C|)$ elements, (2) the second one achieves computational security with $\tilde{O}(|C|)$ elements of communication only from a random oracle, and (3) the third one achieves computational security with $O(|C|)$ elements of communication from pseudorandom correlation generators (PCG).