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.
- 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]
April 17, 2016 21:46 Europe/Tallinn (GMT +03:00)
local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: http://cs.ioc.ee/ewscs/2015/