View article

We investigate the problem of multiparty computations in a fully connected, asynchronous network of n players, in which up to t Byzantine faults may occur. It was shown in [BCG93] that secure error-less multiparty computation is possible in this setting if and only if t< n/4. We show that when exponentially small probability of error is allowed, this task can be achieved even when the number of faults is in the range n/4~ t< n/3. From the lower bounds of [BCG93] for the asynchronous fail-stop model it follows that the resilience, t< n/3, of our protocol is optimal.

We describe an ([~ 1–I)-resilient protocol that securely computes any function F. With overwhelming probability all the non-faulty players complete the execution of the protocol. Given that all the honest players terminate the protocol, they do so in time polynomial in n, in the boolean complexity of 3, and in Pog-$1, where c is the error probability.