SaTC: CORE: Small: Secure Computation on Large Data

本项目重点研究能够有效处理大数据的安全计算协议。安全计算是密码学中一个基本和非常普遍的概念，它捕获了对来自多个来源的数据进行任何算法的隐私保护计算，这些数据应该保持私有，除了计算输出显示的内容。安全计算的可能应用包括公共政策，利用不同公共或私人实体持有的数据来检测财务欺诈或其他紧急情况；医学，寻找药物和患者病史之间的匹配，同时保持两者的私密性；融资，使私人拍卖成为可能；网络安全，识别利用来自不同组织的网络数据的大规模病毒攻击；或保护隐私的互联网服务，例如允许保护隐私的数据库搜索。安全计算在使可行性结果更接近实际方面取得了很大进展。然而，直到最近，高效的安全计算才可能用于短输入计算的程序。将安全计算扩展到大输入情况的一个关键工具是随机存取存储器（SC-RAM）的安全计算协议，即在不泄漏访问位置地址的情况下将秘密共享数据读写到大型秘密共享数组中的选定位置的协议。高效的SC-RAM实现将使安全计算能够扩展到任意大数据，本项目旨在开发有效执行此任务的SC-RAM协议。这项工作的重点是由三方执行共享计算的情况，为此将开发通用和特殊用途的低延迟和高吞吐量协议，根据数据记录的数量和大小、网络拓扑、读与写访问、批处理读取的支持以及其他考虑因素，优化SC-RAM的各种设置。该项目的一部分工作还将包括原型实现，这些实现将被公开，并集成到一个开发环境中，以便安全计算协议应用程序的开发人员可以轻松地采用它们。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project focuses on secure computation protocols that can efficiently compute on large data. Secure computation is a fundamental and very general notion in cryptography that captures privacy-preserving computation of any algorithm on data which originates from multiple sources and should be kept private except for what is revealed by the computation output. Possible applications of secure computation include public policy, to detect financial fraud or other emergency markers using data held by different public or private entities; medicine, to find matches between drugs and patients' medical histories while keeping both private; finance, to enable private auctions; network security, to identify large-scale virus attacks using network data from different organizations; or privacy-protecting internet services, e.g. to allow privacy-protecting database search.Secure computation has seen great progress in bringing feasibility results closer to practice. However, until very recently efficient secure computation was possible only for programs which compute on short inputs. A key tool for extending secure computation to the case of large inputs is a protocol for Secure Computation for Random Access Memory (SC-RAM), i.e., a protocol that reads or writes secret-shared data to a chosen location in a large secret-shared array without leaking the address of the accessed location. Efficient SC-RAM implementations will enable secure computation to scale to arbitrarily large data, and this project seeks to develop SC-RAM protocols which perform this task efficiently. The focus of this work is on the case where the shared computation is performed by three parties, for which both generic and special-purpose low-latency and high-throughput protocols will be developed, optimizing SC-RAM for a variety of settings, depending on the number and size of data records, network topology, read vs. write access, support for batch reads, and other considerations. The work as part of this project will also include prototype implementations which will be made public, integrated in a development environment so that they can be easily adopted by developers of secure computation protocol applications.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.