Foundations of Garbled Circuits

Duration: 1 hour 5 mins 55 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1246903/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Rogaway, P (UC, Davis) Wednesday 11 April 2012, 09:00-10:00


Created:	2012-04-23 13:47
Collection:	Semantics and Syntax: A Legacy of Alan Turing
Publisher:	Isaac Newton Institute
Copyright:	Rogaway, P
Language:	eng (English)


Abstract:	Garbled circuits, a classical idea rooted in the work of A. Yao, have generally been understood as a cryptographic technique, not a cryptographic goal. Here we treat garbled circuits as a proper cryptographic primitive, giving a syntax for a "garbling scheme" and formalizing several security notions for such schemes. The most basic of our notions, "privacy", suffices for the classical goals of two-party secure function evaluation (SFE) and private function evaluation (PFE). We provide a simple and efficient garbling scheme achieving privacy, this built from a block cipher, and we analyze its concrete security. We next consider the "authenticity" and "obliviousness" of a garbling scheme, extending the blockcipher-based protocol to achieve these ends, too. Our treatment of garbling schemes solidifies notions that have been swirling around the literature for years, and promises a more modular approach to designing and using garbling schemes in the future.

Abstract:

Garbled circuits, a classical idea rooted in the work of A. Yao, have generally been understood as a cryptographic *technique*, not a cryptographic *goal*. Here we treat garbled circuits as a proper cryptographic primitive, giving a syntax for a "garbling scheme" and formalizing several security notions for such schemes. The most basic of our notions, "privacy", suffices for the classical goals of two-party secure function evaluation (SFE) and private function evaluation (PFE). We provide a simple and efficient garbling scheme achieving privacy, this built from a block cipher, and we analyze its concrete security. We next consider the "authenticity" and "obliviousness" of a garbling scheme, extending the blockcipher-based protocol to achieve these ends, too. Our treatment of garbling schemes solidifies notions that have been swirling around the literature for years, and promises a more modular approach to designing and using garbling schemes in the future.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.84 Mbits/sec	913.81 MB	View	Download
WebM	640x360	610.73 kbits/sec	290.75 MB	View	Download
Flash Video	484x272	568.66 kbits/sec	274.55 MB	View	Download
iPod Video	480x270	506.18 kbits/sec	244.38 MB	View	Download
MP3	44100 Hz	125.02 kbits/sec	60.22 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)