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.