Information-Theoretic Secure Multi-Party Computation with Collusion Deterrence

Zhaohong Wang, Sen Ching S. Cheung, Ying Luo

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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.

Original languageEnglish
Article number7536175
Pages (from-to)980-995
Number of pages16
JournalIEEE Transactions on Information Forensics and Security
Issue number4
StatePublished - Apr 2017

Bibliographical note

Publisher Copyright:
© 2016 IEEE.


  • Game-Theoretic mechanism design
  • Outsource computing
  • Shamir's secret sharing
  • collusion attacks
  • multi-party computation

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications


Dive into the research topics of 'Information-Theoretic Secure Multi-Party Computation with Collusion Deterrence'. Together they form a unique fingerprint.

Cite this