ETH Series in Information Security and Cryptography
edited by Ueli Maurer
Volume 7

Thomas Holenstein
Strengthening Key Agreement
using Hard-Core Sets

1^st edition/ 1. Auflage 2006, 168 pages/Seiten, € 65,00. ISBN 3-86628-088-2

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.

Keywords: Cryptograhpy, Key-agreement, Hard-Core Sets.

Bookorders at / Buchbestellungen in Ihrer Buchhandlung oder direkt:

Hartung-Gorre Verlag D-78465 Konstanz // Germany

Telefon: +49 (0) 7533 97227 // Telefax: +49 (0) 7533 97228

http://www.hartung-gorre.de

eMail: verlag@hartung-gorre.de
Hartung.Gorre@t-online.de

ETH Series in Information Security and Cryptography