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.