### Abhi Shelat

Dept. of Computer Science

University of Virginia

Charlottesville, VA

USA

## Secure two-party computation

#### Abstract

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

- A. Shelat. Secure two-party computation. Slides from the EWSCS 2015 course. [pdf]
- Videos from the lectures.
- Y. Lindell, B. Pinkas. An efficient protocol for secure two-party
computation in the presence of malicious adversaries. In M. Naor, ed.,
*Proc. of 26th Ann. Int. Conf. on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2007*, v. 4515 of*Lect. Notes in Comput. Sci.*, pp. 52-78. Springer, 2007. [doi link] - Y. Lindell, B. Pinkas. Secure two-party computation via
cut-and-choose oblivious transfer.
*J. of Cryptol.*, v. 25, n. 4, pp. 680-722, 2012. [doi link] - A. Shelat, C.-H. Shen. Two-output secure computation with
malicious adversaries. In K. G. Paterson, ed.,
*Proc. of 30th Ann. Int. Conf. on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2011*, v. 6632 of*Lect. Notes in Comput. Sci.*, pp. 386-405. Springer, 2011. [doi link] - B. Kreuter, A. Shelat, C.-H. Shen. Billion-gate secure computation
with malicious adversaries. In
*Proc. of 21th USENIX Security Symp.*, pp. 285-300. USENIX, 2012. [copy on USENIX website] - A. Shelat, C.-H. Shen. Fast two-party secure computation with
minimal assumptions. In
*Proc. of 2013 ACM SIGSAC Conf. on Computer & Communications Security, CCS '13*, pp. 523-534. ACM, 2013. [doi link] - Y. Lindell. Fast cut-and-choose based protocols for malicious and
covert adversaries. In R. Canetti, Y. A. Garay, eds.,
*Proc. of 33rd Ann. Cryptology Conf., CRYPTO 2013, Part II*, v. 8043 of*Lect. Notes in Comput. Sci.*, pp. 1-17. Springer, 2013. [doi link]

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/