Studies on fault-tolerant broadcast and secure computation
Jonathan I. Katz, Chiu‐Yuen Koo
In this dissertation, we consider the design of broadcast and secure multi-party computation (MPC) protocols in the presence of adversarial faults. Secure multi-party computation is the most generic problem in fault-tolerant distributed computing. In principle, a multi-party computation protocol can be used to solve any distributed cryptographic problem. Informally, the problem of multi-party computation is the following: suppose we have n parties P1, P2,..., Pn where each party Pi has a private input xi. Together, the parties want to compute a function of their inputs (y1, y2,...,yn) = f(x1, x2,...,xn). However, some parties can be corrupted and do not execute a prescribed protocol faithfully. Even worse, they may be controlled by an adversary and attack the protocol in a coordinated manner. Despite the presence of such an adversary, a secure MPC protocol should ensure that each (corrupted) party Pi learn only its output yi but nothing more. Broadcast in the presence of adversarial faults is one of the simplest special cases of multi-party computation and important component of larger protocols. In short, broadcast allows a party to send the same message to all parties, and all
•Jan 1, 2007•8 citations