Paper 2022/944
TwoRound MPC without Round Collapsing Revisited  Towards Efficient Malicious Protocols
Abstract
Recent works have made exciting progress on the construction of round optimal, *tworound*, MultiParty Computation (MPC) protocols. However, most proposals so far are still complex and inefficient. In this work, we improve the simplicity and efficiency of tworound 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 tworound, 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 blackbox calls to a PseudoRandom Function (PRF).  MPC for Arithmetic Branching Programs (ABPs): Our tworound, 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 tworound MPC protocols of [LinLiuWee TCC'20], which are only semihonest 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.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in CRYPTO 2022
 Keywords
 Multiparty Computation
 Contact author(s)

rachel @ cs washington edu
trl @ pku edu cn  History
 20220720: approved
 20220720: received
 See all versions
 Short URL
 https://ia.cr/2022/944
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/944, author = {Huijia Lin and Tianren Liu}, title = {TwoRound {MPC} without Round Collapsing Revisited  Towards Efficient Malicious Protocols}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/944}, year = {2022}, url = {https://eprint.iacr.org/2022/944} }