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

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.
  • Lecture 1 [mp4]
  • Lecture 2 [mp4]
  • Lecture 3 [mp4]
  • Lecture 4 [mp4]


• 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/Helsinki (GMT +03:00) by local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: //cs.ioc.ee/ewscs/2015/