*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: New Directions in Garbled Circuits
David Heath
Ph.D. Student in Computer Science
Georgia Institute of Technology
Date: Friday, April 22, 2022
Time: 4:00pm-5:30pm (ET)
Location (in person): Coda C0915 "Atlantic"
Location (virtual): https://gatech.zoom.us/j/92424356806
Committee:
Dr. Vladimir Kolesnikov (Advisor, Georgia Institute of Technology)
Dr. Mustaque Ahamad (Georgia Institute of Technology)
Dr. Alexandra Boldyreva (Georgia Institute of Technology)
Dr. Daniel Genkin (Georgia Institute of Technology)
Dr. Rafail Ostrovsky (The University of California, Los Angeles)
Abstract:
Today, individuals and organizations often wish to run computations on sensitive private data, but if this private data is deemed too valuable or is legally protected, then the parties cannot safely compute. Secure Multiparty Computation (MPC) is a subfield of cryptography that allows users to compute on encrypted data. Since the data remains encrypted, MPC circumvents the privacy problem: the parties can operate on highly sensitive data while retaining privacy, so MPC enables many useful applications.
Yao's Garbled Circuit (GC) is a foundational approach for achieving secure computation. MPC-based approaches consume three resources: computation, network bandwidth, and network latency (rounds of interaction). GC’s tradeoffs between these costs are extremely attractive, as it uses only constant rounds of interaction and relies primarily on fast symmetric-key primitives.
Thus, new and improved GC techniques are highly valued. However, all prior practical GC techniques required that the desired computation be encoded as a circuit with fan-in two gates. This encoding is problematic: end-user programs often use complex programming features such as vector operations, conditional branching statements, and array accesses. Encoding these features as a circuit is often prohibitively expensive, so circuits are insufficient to efficiently capture end-user programs.
In this dissertation, I present several fundamental GC improvements that for the first time lift GC's expressive power to the level of end-user programs:
The cryptographic techniques underlying each of these improvements are significantly different, but the improvements can nevertheless be used in composition to greatly accelerate GC-based computation.
For almost 40 years, GC research has focused on the cost of Boolean gates. Each of our improvements breaks from this tradition and gives a result previously believed to be either impossible or impractical. Our work for the first time enables a qualitative paradigm shift whereby GCs will no longer evaluate circuits, but will instead evaluate expressive RAM-machine programs. This will enable secure computation of programs written in common programming languages, such as C, which will greatly improve MPC applicability, ease of use, and adoption.
