Multi-party Computation with Hybrid Security
Matthias Fitzi, 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”.
BibTeX Citation
@inproceedings{FiHoWu04,
author = {Matthias Fitzi and Thomas Holenstein and Jürg Wullschleger},
title = {Multi-party Computation with Hybrid Security},
editor = {Christian Cachin and Jan Camenisch},
booktitle = {Advances in Cryptology --- EUROCRYPT 2004},
pages = {419--438},
series = {Lecture Notes in Computer Science},
volume = {3027},
year = {2004},
month = {5},
publisher = {Springer-Verlag},
}