Information-Theoretic Key Agreement: From Weak to Strong Secrecy for Free
Ueli Maurer and Stefan Wolf
One of the basic problems in cryptography is the generation of a common secret key between two parties, e.g., in order to communicate privately. In this paper we consider information-theoretically secure key agreement. Wyner and subsequently Csiszár and Körner described and analyzed settings for secret-key agreement based on noisy communication channels. Maurer as well as Ahlswede and Csiszár generalized these models to a scenario based on correlated randomness and public discussion. In all these settings, the secrecy capacity and the secret-key rate, respectively, have been defined as the maximal achievable rates at which a highly-secret key can be generated by the legitimate partners. However, the privacy requirements were too weak in all these definitions, requiring only the adversary's ratio of information to be negligible, but hence tolerating her to obtain a possibly substantial amount of information about the resulting key. It has been unknown previously how to generate keys about which the adversary has virtually no information. We give natural new definitions of secrecy capacity and secret-key rate satisfying this stronger requirement and show that not only secret-key agreement is possible with respect to the strong secrecy condition, but even that the achievable key-generation rates are equal to the previous weak notions of secrecy capacity and secret-key rate. Hence the unsatisfactory old definitions can be completely replaced by the new ones. The proofs require novel privacy-amplification techniques based on extractor functions.
BibTeX Citation
@inproceedings{MauWol00b,
author = {Ueli Maurer and Stefan Wolf},
title = {Information-Theoretic Key Agreement: From Weak to Strong Secrecy for Free},
editor = {Bart Preneel},
booktitle = {Advances in Cryptology --- EUROCRYPT 2000},
pages = 351--368,
series = {Lecture Notes in Computer Science},
volume = 1807,
year = 2000,
month = 5,
publisher = {Springer-Verlag},
}