In this paper, we propose a new player elimination technique and use it to design an efficient protocol for unconditionally
secure multiparty computation tolerating generalized adversaries. Our protocol requires broadcast of O(nL
2 log(∣F∣) bits (broadcast is simulated using Byzantine agreement) while the non-cryptographic linear secret sharing based
protocols, without player elimination, invoke Byzantine agreement sub-protocol for O(mL
3 log(∣F∣) bits, where m is the number of multiplication gates in the arithmetic circuit, over the finite field F, that describes the functionality of the protocol and L is the size of the underlying linear secret sharing scheme tolerating the given adversary structure.
Keywords secure multiparty computation - generalized adversaries
This work was supported by Defence Research and Development Organization, India under project CSE01-02044DRDOHODX.
Financial support from Infosys Technologies Limited, India is acknowledged.
Throughout the paper we work only with maximal basis of the adversary structure.