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.
