Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-067 | 21st April 2017 19:13

Garbled Circuits as Randomized Encodings of Functions: a Primer

RSS-Feed




TR17-067
Authors: Benny Applebaum
Publication: 22nd April 2017 04:08
Downloads: 1465
Keywords: 


Abstract:

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.

This is a survey that appeared in a book of surveys in honor of Oded Goldreich's 60th birthday.



ISSN 1433-8092 | Imprint