Paper 2016/611

Catching MPC Cheaters: Identification and Openability

Robert Cunningham, Benjamin Fuller, and Sophia Yakoubov

Abstract

Secure multi-party computation (MPC) protocols do not completely prevent malicious parties from cheating or disrupting the computation. We augment MPC with three new properties to discourage cheating. First is a strengthening of identifiable abort, called completely identifiable abort, where all parties who do not follow the protocol will be identified as cheaters by each honest party. The second is completely identifiable auditability, which means that a third party can determine whether the computation was performed correctly (and who cheated if it was not). The third is openability, which means that a distinguished coalition of parties can recover the MPC inputs. We construct the first (efficient) MPC protocol achieving these properties. Our scheme is built on top of the SPDZ protocol (Damgard et al., Crypto 2012), which leverages an offline (computation-independent) pre-processing phase to speed up the online computation. Our protocol is optimistic, retaining online SPDZ efficiency when no one cheats. If cheating does occur, each honest party performs only local computation to identify cheaters. Our main technical tool is a new locally identifiable secret sharing scheme (as defined by Ishai, Ostrovsky, and Zikas (TCC 2012)) which we call commitment enhanced secret sharing or CESS. The work of Baum, Damgard, and Orlandi (SCN 2014) introduces the concept of auditability, which allows a third party to verify that the computation was executed correctly, but not to identify the cheaters if it was not. We enable the third party to identify the cheaters by augmenting the scheme with CESS. We add openability through the use of verifiable encryption and specialized zero-knowledge proofs.