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.
BibTeX Citation
@phdthesis{Holens06b,
author = {Thomas Holenstein},
title = {Strengthening Key Agreement using Hard-Core Sets},
year = {2006},
month = {5},
note = {Reprint as vol.~7 of {ETH Series in Information Security and Cryptography}, {ISBN 3-86626-088-2}, {H}artung-{G}orre {V}erlag, {K}onstanz, 2006},
school = {{ETH Zurich}},
}