Efficient Secure Multiparty Computation Protocol in Asynchronous Network

摘要

This paper proposes an efficient secure multiparty computation protocol among n players resilient to t < n/4 players in asynchronous model. We use Batch Secret Sharing [9] as building blocks. The construction of our protocol is along the line of [7] and [2] which work in synchronous model. The execution of our protocol can be divided into two phases: Pre-computation phase and the Circuit evaluation phase. The pre-computation phase needs to communicate O(n~4 lg |F| + mn~2 log |F|) bits and Broadcast O(n~2 lg |F|) bits, where m is the number of multiplication gates in the circuit and the circuit is over a finite field F. The circuit evaluation phase needs to communicate O(n~3 lg |F| +n~4 lg n+mn~2 lg |F|) bits and Broadcast O(n~2 lg n) bits. Compared with the well-known secure multiparty computation protocol in asynchronous model [4] which needs to communicate O(mn~4 lg |F| + mn~4 lgn) bits and broadcast O(mn~4 lgn) bits, our protocol is quite efficient.