Multi-party Computation with Hybrid Security

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, ort<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 t _p , t _σ , 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.”