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:

• 'One Hot Garbling' substantially improves the performance of vector operations, such as matrix multiplication. The technique also accelerates other common primitives, such as the multiplication of two n-bit integers.
• 'Stacked Garbling' augments GC with efficient conditional branching. Without this improvement, GC evaluation of a program IF or SWITCH statements consumes bandwidth proportional to each program branch. Stacked Garbling introduces fundamentally new techniques that demonstrate it is sufficient to use bandwidth proportional to only the single longest program branch.
• 'Garbled RAM' (GRAM) is a known technique that augments GC with an efficient random access memory. While prior works demonstrate GRAM feasibility, existing techniques have prohibitively high concrete parameters. This dissertation presents fundamental improvements to GRAM. These improvements are concretely efficient and allow for real-world implementations of GRAM.

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.