Approaches to Efficient and Robust Cryptographic Protocols

The growing influence of the Internet and other communication networks on our daily lives and on the global economy shows clearly that the security issues in such networks are of the uttermost importance. Motivated both by the theoretical questions and by the potential real-world applications, in this dissertation we study problems of secure cooperation in communication networks. In particular we focus on constructing efficient and robust protocols for various cryptographic tasks.In the first part of this thesis we study the problem of secure multiparty computation (MPC), which allows a set of n players to evaluate an agreed function of their inputs in a secure way, i.e., so that an adversary corrupting some of the players cannot achieve more than controlling the inputs and outputs of these players. The concept of MPC is very general and powerful, since it allows to realize essentially any distributed computational task in a secure way. For that reason the MPC problem has been studied extensively since its introduction by Yao in 1982. A major goal of these studies is to design protocols with low communication complexity, and two main research directions emerged over the time, with focus on reducing round-, resp. bit-complexity. In this thesis we focus on the bitcomplexity, i.e., the number of bits communicated between the parties during the computation, and we consider this problem in asynchronous networks, which model pretty closely real-world networks. We propose an MPC protocol, which is secure with respect to an active adversary corrupting up to t < n/3 players (this is optimal in an asynchronous network), and which is the most efficient protocol currently known. For our constructions we develop several novel techniques, which were used also in subsequent works on efficient MPC protocols. In the second part of this thesis we turn to a problem which is common to all cryptographic research based on computational assumptions.In spite of considerable advances in theoretical computer science and specifically in complexity theory, it is still not known whether there exist provably hard problems that could form a solid foundation for the complexity-based cryptography. In particular, it is not clear which assumptions are the best, and which are the most likely to hold in 10 or 20 years from now. Therefore, when implementing a cryptographic system in a real-world setting we are confronted with the difficult problem of choosing the most trustworthy assumptions. One way of dealing with this problem is offered by the so-called robust combiners, i.e., constructions which in a certain sense allow to build cryptographic systems based on the best assumption possible, without actually being able to tell which assumption is the best one. Roughly speaking, a robust combiner combines several implementations of a primitive based on various assumptions, to yield an implementation guaranteed to be secure if at least some of the underlying assumptions (i.e. sufficiently many but not necessarily all) are valid. We generalize the notion of robust combiners in several ways, and propose constructions of combiners for various fundamental primitives, like private information retrieval (PIR), oblivious transfer (OT) and oblivious linear function evaluation (OLFE). Our constructions offer tradeoffs between applicability and efficiency, and are strictly stronger and/or more efficient than the constructions known before. Moreover, we introduce cross-primitive combiners, which can be viewed as a generalization of reductions and combiners. Using this more general view we show a separation between PIR and OT, ruling out certain types of reductions of PIR to OT