Catching MPC Cheaters

Our paper (with Rob Cunningham and Sophia Yakoubov) on augmenting security of MPC will be published at ICITS 2017.  Abstract below:

Abstract: Secure multi-party computation (MPC) protocols do not completely prevent malicious parties from cheating and disrupting the computation. A coalition of malicious parties can repeatedly cause the computation to abort or provide an input that does not correspond to reality. 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, even if there are more cheaters than honest parties. The second is completely identifiable auditability, which means that a third party can, given the computation output and its additive share decomposition, determine whether the computation was performed correctly (and who cheated if it was not) by looking at a transcript of the computation.  The third is openability, which means that a distinguished coalition of parties can recover the MPC inputs in the extreme setting when the parties are discovered to have lied about their inputs (e.g. by a real-world event contradicting the output of the MPC).

We construct the first (efficient) MPC protocol achieving these properties.  Our scheme is built on 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: it has the same communication and computation complexity in the online phase as SPDZ when no parties cheat. 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. Each CESS share contains an additive share (as in SPDZ), and additionally includes linearly homomorphic commitments to every additive share. Each CESS share also contains the decommitment value for the commitment to the corresponding additive share. These commitments enable local identification during reconstruction; by the binding property of the commitment scheme, no party should be able to convince any other party of the validity of an altered additive share.  CESS enables MPC with completely identifiable abort; all parties whose claimed output shares do not match their output share commitments are identified as cheaters.

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 of Baum, Damg{\aa}rd, and Orlandi with CESS. We add openability through the use of verifiable encryption and specialized zero-knowledge proofs.