# Key Agreement from Weak Bit Agreement

## Thomas Holenstein

```
```Assume that Alice and Bob, given an authentic channel, have a protocol
where they end up with a bit S_A and S_B, respectively, such that with
probability (1+eps)/2 these bits are equal. Further assume that
conditioned on the event S_A = S_B no polynomial time bounded
algorithm can predict the bit better than with probability 1-delta/2.
Is it possible to obtain key agreement from such a primitive? We show
that for constant delta and eps the answer is yes if and only if delta
> (1-eps)/(1+eps), both for uniform and non-uniform adversaries.

The main computational technique used in this paper is a strengthening
of Impagliazzo's hard-core lemma to the uniform case and to a set size
parameter which is tight (i.e., twice the original size). This may be
of independent interest.