Universally Verifiable Multiparty Computation from Threshold Homomorphic Cryptosystems

Abstract

Abstract. Multiparty computation can be used for privacy-friendly out-sourcing of computations on private inputs of multiple parties. A com-putation is outsourced to several computation parties; if not too many are corrupted (e.g., no more than half), then they cannot determine the inputs or produce an incorrect output. However, in many cases, these guarantees are not enough: we need correctness even if all computation parties may be corrupted; and we need that correctness can be verified even by parties that did not participate in the computation. Protocols satisfying these additional properties are called “universally verifiable”. In this paper, we propose a new security model for universally verifi-able multiparty computation, and we present a practical construction, based on a threshold homomorphic cryptosystem. We also develop a multiparty protocol for jointly producing non-interactive zero-knowledge proofs, which may be of independent interest.