Towards Efficiency-Preserving Round Compression in MPC Do Fewer Rounds Mean More Computation?

摘要

Reducing the rounds of interaction in secure multiparty computation (MPC) protocols has been the topic of study of many works. One popular approach to reduce rounds is to construct round compression compilers. A round compression compiler is one that takes a highly interactive protocol and transforms it into a protocol with far fewer rounds. The design of round compression compilers has traditionally focused on preserving the security properties of the underlying protocol and in particular, not much attention has been given towards preserving their computational and communication efficiency. Indeed, the recent round compression compilers that yield round-optimal MPC protocols incur large computational and communication overhead. In this work, we initiate the study of efficiency-preserving round compression compilers, i.e. compilers that translate the efficiency benefits of the underlying highly interactive protocols to the fewer round setting. Focusing on the honest majority setting (with near-optimal corruption threshold 1/2 - ε, for any ε ＞ 0), we devise a new compiler that yields two round (i.e., round optimal) semi-honest MPC with similar communication efficiency as the underlying (arbitrary round) protocol. By applying our compiler on the most efficient known MPC protocols, we obtain a two-round semi-honest protocol based on one-way functions, with total communication (and per-party computation) cost O(s + n~4) -a significant improvement over prior two-round protocols with cost O(n~τs + n~(τ+1)d), where r ≥ 2, s is the size of the circuit computing the function and d the corresponding depth. Our result can also be extended to handle malicious adversaries, either using stronger assumptions in the public key infrastructure (PKI) model, or in the plain model using an extra round. An artifact of our approach is that the resultant protocol is "unbalanced" in the amount of computation performed by different parties. We give evidence that this is necessary in our setting. Our impossibility result makes novel use of the "MPC-in-the-head" paradigm which has typically been used to demonstrate feasibility results.