Cryptology ePrint Archive: Report 2017/385

Garbled Circuits as Randomized Encodings of Functions: a Primer

Benny Applebaum

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 randomized encoding (RE) of Functions. We review old and new constructions of REs, present some lower-bounds, and describe some applications. We will 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.

Category / Keywords: foundations / randomized encoding, garbled circuits

Original Publication (in the same form): Tutorials on the Foundations of Cryptography, Dedicated to Oded Goldreich

Date: received 2 May 2017

Contact author: benny applebaum at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170504:115916 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]