Abstract

Yao's Garbled Circuit (GC) technique is one of our many primitives for achieving secure multiparty computation (MPC), and it is particularly powerful in that it enables MPC protocols that consume only a constant number of rounds of communication. Traditionally, GC was limited in that it worked only for computations expressed as Boolean circuits. More recently, the literature has erupted with new asymptotically-efficient techniques that augment GC with efficient support for more expressive computational primitives, such as arithmetic gates, random access memory, and lookup tables.

In this talk, I will describe handling two of these primitives -- arithmetic gates and random access memory -- by showing how to compile these primitives to simple operations that are easily implemented inside GC.

My focus in this talk will be on those GC techniques that can be achieved from simple symmetric key cryptography, i.e. using only a random oracle.