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:

• "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 will present fundamental improvements to GRAM. These improvements are concretely efficient and will 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.