Paper 2022/944

Two-Round MPC without Round Collapsing Revisited -- Towards Efficient Malicious Protocols

Huijia Lin, University of Washington
Tianren Liu, Peking University

Recent works have made exciting progress on the construction of round optimal, *two-round*, Multi-Party Computation (MPC) protocols. However, most proposals so far are still complex and inefficient. In this work, we improve the simplicity and efficiency of two-round MPC in the setting with dishonest majority and malicious security. Our protocols make use of the Random Oracle (RO) and a generalization of the Oblivious Linear Evaluation (OLE) correlated randomness, called tensor OLE, over a finite field $\mathbb{F}$, and achieve the following: - MPC for Boolean Circuits: Our two-round, maliciously secure MPC protocols for computing Boolean circuits, has overall (asymptotic) computational cost $O(S\cdot n^3 \cdot \log |\mathbb{F}|)$, where $S$ is the size of the circuit computed, $n$ the number of parties, and $\mathbb{F}$ a field of characteristic two. The protocols also make black-box calls to a Pseudo-Random Function (PRF). - MPC for Arithmetic Branching Programs (ABPs): Our two-round, information theoretically and maliciously secure protocols for computing ABPs over a general field $\mathbb{F}$ has overall computational cost $O(S^{1.5}\cdot n^3\cdot \log |\mathbb{F}|)$, where $S$ is the size of ABP computed. Both protocols achieve security levels inverse proportional to the size of the field $|\mathbb{F}|$. Our construction is built upon the simple two-round MPC protocols of [Lin-Liu-Wee TCC'20], which are only semi-honest secure. Our main technical contribution lies in ensuring malicious security using simple and lightweight checks, which incur only a constant overhead over the complexity of the protocols by Lin, Liu, and Wee. In particular, in the case of computing Boolean circuits, our malicious MPC protocols have the same complexity (up to a constant overhead) as (insecurely) computing Yao's garbled circuits in a distributed fashion. Finally, as an additional contribution, we show how to efficiently generate tensor OLE correlation in fields of characteristic two using OT.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
Multiparty Computation
Contact author(s)
rachel @ cs washington edu
trl @ pku edu cn
2022-07-20: approved
2022-07-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Huijia Lin and Tianren Liu},
      title = {Two-Round MPC without Round Collapsing Revisited -- Towards Efficient Malicious Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2022/944},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.