# Strengthening Key Agreement using Hard-Core Sets

## Thomas Holenstein

```
```Given an authentic communication channel, a key agreement protocol
enables two parties to obtain a common bit string, such that a
computationally bounded eavesdropper does not get any information
about it, even if he observes the whole communication. Many such
protocols are used in practice today, and they all base their security
on an unproven assumption.

The goal of this thesis is to base such a protocol on an assumption
which is as weak as possible. The assumption we use is the existence
of a weak key agreement protocol. Such a protocol works partially: in
some executions the honest parties get the same key, but sometimes
their respective keys differ. Furthermore, in some cases the
resulting key is secret, while sometimes information about the key is
leaked. We then strengthen such a protocol; i.e., we make it both
secret and correct.

Our proof relies on a powerful lemma about hard-core sets. Roughly
speaking, the lemma shows that any computational problem which is
mildly hard has a set of instances for which it is very hard. In our
setting this implies that for a weak key agreement protocol, if the
randomness of Alice and Bob is restricted to a certain subset, finding
the key from the communication is a very hard problem.