Information-Theoretic Secure Multi-Party Computation with Collusion Deterrence

Secure multi-party computation (MPC) has been established as the de facto paradigm for protecting privacy in distributed computation. Among many secure MPC primitives, Shamir's secret sharing (SSS) has the advantages of having low complexity and information-theoretic security. However, SSS requires multiple honest participants and is susceptible to collusion attacks. In this paper, we provide a detailed analysis of different types of collusion attacks and propose novel mechanisms to deter such attacks in a fully distributed manner. Focusing on outsourced computing environments where secret data owners can collaborate on a public computing platform, we study collusion attacks using game theory. For those attacks where the thefts are detectable, we show that they can be effectively deterred by an explicit retaliation mechanism between data owners. The result is based on a comprehensive analysis that takes into account the cost of collusion, the privacy preference, and the associated uncertainty. For those attacks where the thefts cannot be detected, we expand the analysis to include the computing platform and provide deterrence through deceptive collusion requests as well as a novel cryptographic censorship protocol. The correctness and the privacy of the protocols are proved under the rational adversarial model. Our SSS-based protocols are shown to outperform the state-of-the-art garbled circuit systems, while our simulation results validate the proposed mechanism designs in deterring collusion.