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.
|Number of pages||16|
|Journal||IEEE Transactions on Information Forensics and Security|
|State||Published - Apr 2017|
Bibliographical notePublisher 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