Abstract: Consider a set of parties who do not trust each other, nor the channels by which they communicate. Still, the parties wish to correctly compute some common function of their local inputs, while keeping their local data as private as possible. This, in a nutshell, is the problem of secure multiparty computation. We study several aspects of secure multiparty computation. We first present new definitions of this problem in various settings. Our definitions draw from previous ideas and formalizations, and incorporate aspects that were previously overlooked.
Next we study the problem of dealing with adaptive adversaries. We show how to construct adaptively secure protocols for computing any function in a computational setting, where the communication channels can be tapped by the adversary, and secure communication is achieved by cryptographic primitives based on the computational limitations of the adversary. We remark that this was considered to be a hard open problem.
Next, we initiate a study of secure multiparty computation in asynchronous networks. We present appropriate definitions and construct protocols for securely computing any function.
In the same asynchronous setting, we apply ideas and techniques of secure multiparty computation to a classical problem in the field of distributed computing, namely the problem of reaching agreement in the presence of Byzantine faults. We present the first asynchronous Byzantine Agreement protocol with optimal resilience (i.e., an adversary may corrupt up to n/3-1 of the n parties) and polynomial complexity.
Finally we address the problem of maintaining the security of computer systems in the presence of repeated, however transient break-ins. We present a new approach for dealing with this problem. Using our approach, we show how systems can automatically recover from transient break-ins. We use secure multiparty computation as a formal setting for developing and analyzing our mechanisms.
Organization: The thesis is available either in one compressed file (~570KB), or in several uncompressed parts: