Essentially all work optimizing the round complexity of secure computation focuses on minimizing the number of rounds assuming a broadcast channel is available. Unfortunately, such protocols tend to have very poor round complexity when compiled for a point-to-point network due to the high overhead of emulating each invocation of broadcast.
We argue that if the goal is to optimize round complexity
in point-to-point networks, then it is preferable to
design protocols --- assuming a broadcast channel --- that minimize the number of rounds in which broadcast is used rather than protocols that minimize the total number of rounds. With this in mind, we present
protocols for secure computation in a number of settings that use only a
(minimal) single round of broadcast. In all cases, we achieve optimal
security threshold for adaptive adversaries, and obtain protocols whose
round complexity
(in a point-to-point network) substantially improves on prior work.
This is joint work with Jonathan Katz.
Copyright. All Rights Reserved.