20th Estonian Winter School in Computer Science (EWSCS)
XX Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 1 - 6, 2015

Abhi Shelat

Dept. of Computer Science
University of Virginia
Charlottesville, VA

Secure two-party computation


Secure two-party computation allows Alice with private input x and Bob, with input y, to jointly compute f(x,y) without revealing any information other than the output f(x,y).

We will introduce Yao's garbled circuits framework for constructing such secure two-party protocols. We will start with an overview of the basic honest-but-curious protocol, which guarantees that when Alice and Bob both follow the protocol, they learn nothing more than the output. We will introduce the oblivious transfer protocol and the basic garbling methods for circuits. We will also discuss all recent algorithmic improvements to garbling, including garbled row-reduction, free xor, secret-sharing, and half-gate garbling.

We then describe the cut-and-choose paradigm for transforming an honest-but-curious protocol into a maliciously-secure protocol. We will consider several approaches to the cut-and-choose technique, starting with the SS13 protocol. We will then highlight the recent technique of Lindell13 that achieves security 2-s but only requires roughly s garbled circuits. This course will serve as a basic introduction to practical secure 2-party computation in both honest-but-curious and malicious models.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed April 17, 2016 21:46 Europe/Tallinn (GMT +03:00) by local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: http://cs.ioc.ee/ewscs/2015/