ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Multi-party Computation with Hybrid Security

Matthias Fitzi and Thomas Holenstein and J{ü}rg Wullschleger

It is well-known that n players connected only by pairwise secure channels can achieve multi-party computation secure against an active adversary if and only if t < n/2 of the players are corrupted with respect to computational security, or t < n/3 of the players are corrupted with respect to unconditional security.

In this paper we examine to what extent it is possible to achieve conditional (such as computational) security based on a given intractability assumption with respect to some number T of corrupted players while simultaneously achieving unconditional security with respect to a smaller threshold t <= T. In such a model, given that the intractability assumption cannot be broken by the adversary, the protocol is secure against T corrupted players. But even if it is able to break it, the adversary is still required to corrupt more than t players in order to make the protocol fail.

For an even more general model involving three different thresholds tp, ts, and T, we give tight bounds for the achievability of multi-party computation. As one particular implication of this general result, we show that multi-party computation computationally secure against T < n/2 actively corrupted players (which is optimal) can additionally guarantee unconditional security against t <= n/4 actively corrupted players ``for free''.