# Approaches to Efficient and Robust Cryptographic Protocols

## Bartosz Przydatek

```
```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.