Paper 2020/636

Mixed-Technique, Maliciously-Secure, and Composed Multi-Party Computations

Erik-Oliver Blass and Florian Kerschbaum

Abstract

Efficient multi-party protocols are commonly composed of different sub-protocols, combining techniques such as homomorphic encryption, secret or Boolean sharing, and garbled circuits. To ensure security of the composed protocol against malicious adversaries, one needs to prove in zero-knowledge that conversions between individual techniques are correct. However, efficient ZK proofs for conversion between fully homomorphic encryption and garbled circuits are still an open problem. In this paper, we design new efficient proofs and apply them to a new class of multi-party protocols which themselves are composed out of two-party protocols. We integrate both types of compositions, compositions of fully homomorphic encryption with garbled circuits and compositions of multi-party protocols from two-party protocols. As a result, we can construct communication-efficient protocols for special problems with malicious security. To show the usefulness of this approach, we give an example scheme for private set analytics, i.e., private set disjointness. This scheme enjoys lower communication complexity than a solution based on generic multi-party protocols and lower computation cost than fully homomorphic encryption. So, our design is more suitable for deployments in wide-area networks, such as the Internet, with many participants or problems with circuits of moderate or high multiplicative depth.