Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.

In the current chapter, as in the previous chapter, we consider multiparty computation (MPC) with full security — i.e., with guaranteed output delivery. Further, this setting considers information-theoretic (i.t.) security, in which the security of protocols is guaranteed independent of computational assumptions, and no restriction on the adversary's computing power is assumed, which is why i.t. security is often referred to as unconditional security. As we shall see, this strong type of security can be achieved only when the choice of the sets of parties that can be corrupted at the same time is restricted, e.g., when a strict minority of the parties might be corrupted. Because of this limitation, this type of full security is interesting only in the setting of three or more parties.

This chapter offers an overview of the main results in feasibility of information-theoretically secure multi-party computation.