Selected Topics in Multi-Party Computation

Selected Topics in Multi-Party Computation
Daniel Tschudi
PhD thesis, ETH Zurich, February 2018.

Abstract. Secure multi-party computation (MPC) allows a set of n parties to evaluate a function f in the presence of an adversary who corrupts a subset of the parties. In this work we investigate three selected topics in the area of MPC. Most MPC protocols require that parties are pair-wise connected by means of secure channels. To run an MPC over an incomplete network, secure message transfer protocols (SMTP) can be used. However, classic SMTP leaks information about the topology of the underlying network. In the first part of this thesis, we present the first topology-hiding communication protocol for incomplete networks which makes black-box use of the underlying cryptographic assumptions. The protocol tolerates any adversary who passively corrupts arbitrarily many network nodes. This protocol allows to make any MPC protocol with passive security topology-hiding. We further show how to construct anonymous broadcast without using expensive MPC to setup the original pseudonyms. Broadcast channels are an important primitive used in many MPC protocols. It is well-known that broadcast channels can be achieved with perfect security if and only if the fraction of active cheaters is less than a third. A natural question initially raised by Lamport, is whether there are weaker, still useful primitives achievable from authenticated channels. In the second part of the thesis we investigate generalizations of the broadcast setting in two directions: weaker forms of consistency guarantees are considered, and other resources than merely bilateral channels are assumed to be available. The ultimate goal of this line of work is to arrive at a complete classification of consistency specifications. In the third part of the thesis, we consider active, general adversaries which are characterized by a so-called adversary structure Z. The adversary structure enumerates all possible subsets of corrupted parties. Protocols for general adversaries are “efficient” in the sense that they require |Z|^O(1) bits of communication. However, as |Z| is usually very large (even exponential in n), the exact exponent is very relevant. For the setting with perfect security we present a protocol which requires O(|Z|^2) bits of communication. For the setting with statistical security we present a protocol which requires O(|Z|^3) bits of communication. Both protocols have a better communication complexity than previous protocols.