Exploring the Boundaries of Large-Scale Secure Computation

As the capability and connectivity of communication networks scale up, existing secure distributed protocols need to resort to a frugal use of their communication resources to ensure their scalability. Secure multi-party computation (MPC), which allows a set of mutually distrustful parties to perform arbitrary computations on their joint inputs in a secure way, even in the presence of malicious participants and attackers, epitomizes such kind of secure distributed computation, and despite great improvements in all communication metrics over the last decade, existing solutions do not scale well in settings where a large number of participants are involved. One of the reasons is that in standard MPC protocols every party needs to directly communicate will all other parties, yielding protocols with high communication costs. Recently, some attempts to address this issue were made to carry out MPC with lower communication costs. The project's impacts are to put forth a systematic study of this type of MPC protocols, which we call "Communication-Frugal MPC" (CF-MPC), and to advance its theoretical foundations to meet the state of the art comparable to standard MPC. In an era where computation on large data has become a dominant application, such exploration is of central importance in both theory and practice.

The project's novelties include: (1) Development of a rigorous and composable cryptographic model for capturing CF-MPC; (2) feasibility study of CF-MPC with optimal resiliency (i.e., the maximal number of potentially malicious participants that can be tolerated) across all standard communication and adversary models (synchronous vs asynchronous, and static vs adaptive); and (3) improved constructions on additional communication metrics such as message, bit, and round complexity.

The project, which is in collaboration with UCLA and Texas A&M, is supported by the National Science Foundation.