# Information Security and Cryptography Research Group

## Key Agreement from Weak Bit Agreement

### Thomas Holenstein

Proc. 37th ACM Symposium on Theory of Computing — STOC 2005, pp. 664–673, May 2005.

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.

## BibTeX Citation

@inproceedings{Holens05,
author       = {Thomas Holenstein},
title        = {Key Agreement from Weak Bit Agreement},
editor       = {Ronald Fagin},
booktitle    = {Proc.~37th ACM Symposium on Theory of Computing --- STOC 2005},
pages        = {664--673},
year         = {2005},
month        = {5},
}