Collaborative Research: SaTC: CORE: Medium: New Constructions for Garbled Computation

Secure multi-party computation (MPC) is a large and growing subfield of cryptography that enables mutually untrusting parties to jointly evaluate functions on their private data. One exciting promise of MPC is the ability to write such functions as general programs and then evaluate them securely. This would enable even non-crypto-specialists to automatically augment ordinary software with powerful security properties. Tools for achieving this goal have proven elusive, due to barriers to efficiently executing ordinary programs inside MPC. The critical barrier is in efficiently handling random access memory (RAM). RAM is ubiquitous in computing, but efficient MPC handling of RAM is well known as a stubborn challenge. This project will significantly improve MPC handling of RAM, thus enabling far more efficient general-purpose MPC tools. Garbled RAM (GRAM) is a powerful MPC primitive that removes interactivity (and hence costly latency) from MPC of programs with RAM accesses. Recent GRAM techniques overcame several long-standing obstacles to GRAM efficiency and restored hope for significant further improvement. The investigators will seize the opportunity, and will explore and implement novel GRAM techniques. The project’s scope is broad, and includes improving GRAM efficiency, bringing GRAM to richer settings, understanding GRAM’s theoretical and practical limitations, improving the cryptographic assumptions needed to construct efficient GRAM, and implementing software prototypes. 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.