|
Abstract : |
It has recently been shown that executions of authenticated Byzantine Agreement protocols in which more than a third of the parties are faulty, cannot be composed concurrently, in parallel, or even sequentially (where the latter is true for deterministic protocols). This result puts into question any usage of authenticated Byzantine agreement in a setting where many executions take place. In particular, this is true for the whole body of work of secure multiparty protocols in the case that 1=3 or more of the parties are faulty. Such protocols strongly rely on the extensive use of a broadcast channel, which is in turn realized using authenticated Byzantine Agreement. Essentially, this use of Byzantine Agreement cannot be eliminated, since the standard definitions of secure multiparty computation actually imply Byzantine agreement. Moreover, it is accepted folklore that the use of a broadcast channel is essential for achieving any meaningful secure multiparty computation, when 1=3 or more of the parties are faulty. In this paper we show that this folklore is false. We mildly relax the definition of secure computation allowing abort, and show how this definition can be reached. In fact, we show that any protocol that is secure when run using a broadcast channel, can be transformed into a protocol that is secure under our relaxed definition and without a broadcast channel (or trusted preprocessing phase). We stress that our transformation holds for secure computation in both the information-theoretic and computational models. As a result we can securely compose multiple concurrent executions of multiparty protocols. The transformation replaces the use of Byzantine agreement by a weaker form of agreement which can be realized deterministically with O(1) round complexity, and furthermore composes concurrently. The agreement provided is mild indeed: each honest player is guaranteed to either abort or receive the value which was broadcasted by an honest broadcaster. If the broadcaster is faulty all honest player which do not abort, agree on the same value. Nevertheless, as we show, this is sufficient for achieving significant secure computation. 1, |
