SaTC: CORE: Small: Collaborative: Exploring the Boundaries of Large-Scale Secure Computation

随着通信网络的能力和连通性的增强，现有的安全分布式协议需要采取节约使用其通信资源的方式来确保其可扩展性。安全多方计算（MPC）允许一组相互不信任的各方以安全的方式对他们的联合输入执行任意计算，即使存在恶意参与者和攻击者，也是这种安全分布式计算的缩影，尽管在过去十年中所有通信指标都有很大的改进，现有的解决方案在涉及大量参与者的环境中不能很好地扩展。原因之一是在标准MPC协议中，每一方都需要与所有其他方直接通信，从而产生具有高通信成本的协议。最近，为了解决这个问题进行了一些尝试，以实现具有较低通信成本的MPC。该项目的影响是提出一个系统的研究这种类型的MPC协议，我们称之为“通信节俭MPC”（CF-MPC），并推进其理论基础，以满足最先进的标准MPC。在大数据计算已成为主流应用的时代，这种探索在理论和实践上都具有核心重要性。该项目的创新之处包括：（1）开发用于捕获CF-MPC的严格和可组合的密码模型;（2）具有最佳弹性的CF-MPC的可行性研究（即，可以容忍的潜在恶意参与者的最大数量）;以及（3）对诸如消息、比特和轮复杂度之类的附加通信度量的改进的构造。这个奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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 will train graduate and undergraduate students.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.