Round Efficient Unconditionally Secure Multiparty Computation Protocol

In this paper, we propose a round efficient

unconditionally secure multiparty computation

(UMPC) protocol in

information theoretic

model with

n

 > 2

t

players, in the absence of any physical broadcast channel. Our protocol communicates

${\cal O}(n^4)$

field elements per multiplication and requires

${\cal O}(n \log(n) + {\cal D})$

rounds, even if up to

t

players are under the control of an active adversary having

unbounded computing power

, where

${\cal D}$

denotes the multiplicative depth of the circuit representing the function to be computed securely. In the absence of a physical broadcast channel and with

n

 > 2

t

players, the best known UMPC protocol with minimum number of rounds, requires

${\cal O}(n^2{\cal D})$

rounds and communicates

${\cal O}(n^6)$

field elements per multiplication. On the other hand, the best known UMPC protocol with minimum communication complexity requires communication overhead of

${\cal O}(n^2)$

field elements per multiplication, but has a round complexity of

${\cal O}(n^3 +{\cal D})$

rounds. Hence our UMPC protocol is the most round efficient protocol so far and ranks second according to communication complexity.