Garbled Circuits as Randomized Encodings of Functions: a Primer

摘要

Yao's garbled circuit construction is a central cryptographic tool with numerous applications. In this tutorial, we study garbled circuits from a foundational point of view under the framework of emph{randomized encoding} (RE) of functions. We review old and new constructions of REs, present some lower bounds, and describe some applications. We also discuss new directions and open problems in the foundations of REs.