Abstract: In the setting of secure multi-party computation (MPC), a set of parties want to jointly compute a function of their inputs while preserving the privacy of their inputs and ensuring the correctness of their outputs. It has been known since the mid-80s that, under standard cryptographic assumptions, secure computation is feasible whenever more than half the parties are honest. While this feasibility result is of great theoretical importance, designing efficient protocols for secure MPC remains a challenging task.

This talk surveys recent work aimed at improving the round complexity of protocols for secure MPC:

- I show that Byzantine agreement with an honest majority is possible in an expected constant number of rounds, answering a question that has been open since 1987. As a by-product, this gives the first (expected) constant-round protocols for secure MPC.

- A useful design methodology is to design protocols under the assumption that a broadcast channel exists, and then emulate the broadcast channel using a Byzantine agreement sub-protocol. I show that secure MPC is possible using only a single round of broadcast. (This is optimal.) This gives MPC protocols whose round complexity substantially improves on existing work.

Short Bio: Chiu-Yuen Koo is a Ph.D. candidate at the University of Maryland. His research interests include cryptography and distributed computing. He was a Fellow at the Institute for Pure and Applied Mathematics (IPAM) in Fall 2006.

The speaker is a faculty candidate.