AP1: Probabilistic privacy-preserving protocols

In secure multi-party computation several parties aim to jointly compute a (potentially probabilistic) function on their private inputs in a distributed fashion in a way such that no party learns more about the other parties’ private inputs than what can be inferred from the output of the function and the party’s own private input. Bartering is an important application of secure multi-party computation. Here, each party specifies its offers and demands consisting of commodities and (if the commodities are divisible) minimal and maximal quantities of them. The goal of a privacy-preserving protocol is then to determine a trade cycle in a distributed fashion such that the offers and demands of each party are kept private and each party only learns how much of which commodity it has to give to which other party and from which party to receive which quantity of which commodity.

Such protocols are developed for the semi-honest and the malicious attacker model. The former assumes that all parties follow the protocol but potentially carry out additional computations on information gained during protocol execution. The latter allows the attacker to deviate from the protocol almost arbitrarily—typically resulting in protocols with a high complexity. In the covert adversary model, parties are considered to actively deviate from the protocol but refrain from deviating if the probability of being detected while cheating is high.

The privacy-preserving protocols designed so far are probabilistic rather than deterministic for privacy, efficiency and/or application specific reasons: e.g., the quantities are drawn uniformly at random from the range of possible quantities in order to ensure that no party is preferred over another. Also, if several potential trade cycles exist that could be selected but that are not executable in parallel, one has to select one according to some optimisation criteria such as trying to find a trade cycle involving as many parties as possible or trying to find cycles that do not involve more than three parties. Finally, selecting a trade cycle from the set of potential but conflicting trade cycles uniformly at random may be the only acceptable way forward for efficiency reasons. Existing research focuses on developing privacy-preserving protocols and their efficiency. However, due to the fact that the protocols are probabilistic, they do not necessarily find an optimal solution for the trade cycle problem. It is therefore an open question to determine the quality of the solution and compare it to the optimal solution, to deterministic non-privacy preserving protocols, as well as to non-privacy preserving probabilistic protocols proposed in the past.

This dissertation project aims to (1) develop privacy-preserving bartering protocols in the covert adversary model, (2) comparatively analyse the quality of the newly developed as well as the probabilistic privacy-preserving protocols, (3) explore the trade-off between the conflicting goals of efficiency and quality of such protocols.