Minimally-Interactive Protocols for Privacy-Preserving Set and Multiset Operations Between Multiple Parties

Abstract

In our increasingly digital society, we are making a growing amount of data available to computers, networks and third parties. As a consequence, our sensitive data is in danger of getting exposed. The field of multi-party computation attempts to mitigate this by studying protocols that enable parties to perform their operations digitally, without the risk of privacy-violating data leaks. Among those operations are multi-party private set and multiset operations. In such a scenario, multiple parties, each with their own input set or multiset, want to collectively find the result of an operation over their inputs, without revealing these original inputs. Such operations are the cornerstone of many complex privacy-preserving protocols. For example, a two-party private set intersection forms the key to several privacy-preserving contact tracing protocols.

While multi-party private set and multiset operations have been studied for almost two decades, these privacy-preserving alternatives are often impractical: one limitation is that, to the best of our knowledge, all known protocols require several interactions between the cooperating parties. This means that rather than simply submitting their input, each party must actively take part in the protocol. In this thesis, we propose the first non-interactive protocols for privately computing set and multiset operations between multiple parties,
which rely on two constructions for non-interactive secret sharing. In addition, for operations that cannot be trivially performed using our non-interactive primitives, we propose minimally-interactive alternatives that instead rely on a homomorphic cryptosystem over elliptic curves. By using elliptic curves, this cryptosystem is faster and requires less bandwidth than the commonly used cryptosystems over integers, while retaining the same level of security. We provide proof-of-concept implementations of exact and more efficient approximate protocols that take on the order of seconds to minutes to compute, depending on the number of parties and possible inputs. Finally, we give formal proofs for the security of these protocols, so as to offer practical and provably privacy-preserving alternatives to otherwise sensitive operations.