Probabilistic Privacy-Reasoning ProtocolsCopyright: Martin Braun
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.
Meyer’s group develops such protocols for the semi-honest and the malicious attacker model a the DFG-project. 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. The covert adversary model is not considered as part of the already funded project. In this 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: for example the quantities in 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. The DFG-project 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.