Paper 2014/060

Verifiable Computation in Multiparty Protocols with Honest Majority

Peeter Laud and Alisa Pankova

Abstract

A lot of cryptographic protocols have been proposed for semi-honest model. In general, they are much more efficient than those proposed for the malicious model. In this paper, we propose a method that allows to detect the parties that have violated the protocol rules after the computation has ended, thus making the protocol secure against covert attacks. This approach can be useful in the settings where for any party it is fatal to be accused in violating protocol rules. In this way, up to the verification, all the computation can be performed in semi-honest model, which makes it very efficient in practice. The verification is statistical zero-knowledge, and it is based on linear probabilistically checkable proofs ($\PCP$) for verifiable computation. Each malicious party is detected with probability $1 - \varepsilon$ for a negligible $\varepsilon$ that is defined by the failure of the corresponding linear $\PCP$. The initial protocol has to be executed only once, and the verification requires in total $3$ additional rounds (if some parties act dishonestly, in the worst case they may force the protocol to substitute each round with $4$ rounds, due to the transmission functionality that prevents the protocol from stopping). The verification also ensures that all the parties have sampled all the randomness from an appropriate distribution. Its efficiency does not depend on whether the inputs of the parties have been shared, or each party uses its own private input. The major drawback of the proposed scheme is that the number of values sent before and after the protocol is exponential in the number of parties. Nevertheless, the settings make the verification very efficient for a small number of parties.