News

Colloquia

Round-Efficient Secure Computation

Chiu Yuen Koo
University of Maryland

Monday, March 12, 2007

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.