Unbounded Subquadratic BA Sample Clauses

Unbounded Subquadratic BA. We now show how to achieve an unbounded number of subquadratic BA executions. We describe two solutions: one involving a trusted dealer who initializes the parties with a one-time setup, and the other a dealer-free solution that achieves expected subquadratic communication in an amortized sense. A trusted dealer can initially distribute a PKI (this is done only once and for all) and in addition initialize the parties with the setup for one instance of ΠBA and one instance of ΠMPC. Importantly, the setup for ΠMPC can be used to compute any no-input functionality; in particular, the size of the setup is fixed, independent of the size of the circuit for the functionality being computed, or its output length. For a BA execution, the parties run ΠBA and then use ΠMPC to refresh their setup by simulating the dealer algorithm. (We stress that they refresh the setup for both ΠBA and ΠMPC.) The expected communication complexity per BA execution 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. By proceeding in this way, the parties can run an unbounded number of BA executions while only involving a trusted dealer once. Alternately, we can avoid a trusted dealer altogether by having the parties simulate the dealer using an arbitrary (setup-free) MPC protocol. The communication complexity of the initial MPC protocol may be high, but all subsequent BA executions will have subquadratic (expected) com- munication complexity as above. In this way we achieve an unbounded number of BA executions with amortized (expected) subquadratic communication complexity.