Unbounded Byzantine Agreement with Subquadratic Communica Sample Clauses

Unbounded Byzantine Agreement with Subquadratic Communica tion We now show how to use the ideas from the previous section to achieve an unbounded number of BA executions with subquadratic communication. We describe two solutions: one involving a trusted dealer who initializes the parties with a one-time setup, and another that does not require a dealer (but does assume a PKI) and achieves expected subquadratic communication in an amortized sense. For the first solution, we assume a trusted dealer who initializes the parties with the setup for one instance of ΠBA and one instance of ΠMPC. (We also assume a PKI, which could be provided by the dealer as well; however, when we refer to the setup for ΠMPC we do not include the PKI since it does not need to be refreshed.) Importantly, the setup for ΠMPC allows the parties to compute any no-input functionality; the size of the setup is fixed, independent of the size of the circuit for the functionality being computed or its output length. For an execution of Byzantine agreement, the parties run ΠBA using their inputs and then use ΠMPC to refresh their setup by simulating the dealer algorithm. (We stress that the parties refresh the setup for both ΠBA and ΠMPC.) The expected communication complexity per execution of Byzantine agreement is the sum of the communication complexities of ΠBA and ΠMPC. The former is subquadratic; the latter is subquadratic if we follow the approach described in the previous section. Thus, the parties can run an unbounded number of subquadratic BA executions while only involving a trusted dealer once. Alternately, we can avoid a trusted dealer by having the parties simulate the dealer using an arbitrary adaptively secure MPC protocol. (We still assume a PKI.) The commu- nication complexity of the initial MPC protocol may be arbitrarily high, but all subsequent BA executions will have subquadratic (expected) communication complexity as above. In this way we achieve an unbounded number of BA executions with amortized (expected) subquadratic communication complexity.