Honest Majority Constant-Round MPC with Linear Communication from One-Way Functions

This chapter delves into the critical aspects of secure multiparty computation (MPC), focusing on the dual challenges of round complexity and communication complexity. It begins by reviewing the fundamental concepts of MPC, highlighting the tension between minimizing round complexity and optimizing communication overhead. The text explores the honest majority setting, where protocols can be constructed using one-way functions, and discusses recent advancements in reducing communication costs. A significant portion of the chapter is dedicated to constant-round MPC protocols based on garbled circuits, detailing breakthroughs that have significantly lowered communication costs. The chapter introduces novel techniques for computing garbled circuits via party virtualization, which leads to an efficient multiparty garbling process. It also addresses the challenges of achieving malicious security and presents solutions to verify the computation of virtual parties. The chapter concludes with a summary of the main protocol, which achieves a 26-round MPC protocol with linear communication complexity, assuming one-way functions. This comprehensive exploration provides valuable insights into the current state and future directions of MPC protocols, making it an essential read for professionals in the field.