*********************************
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
Georgia Institute of Technology
Date: Wednesday, Nov 17, 2021
Time: 2:30pm-4:00pm (ET)
Location: Coda C0908 "Home Park"
Proposal 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)
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, the parties cannot compute the desired functions. 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 will present several fundamental GC improvements that lift GC's expressive power to the level of end-user programs for the first time:
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.
