One of the basic problems in cryptography is the generation of a common secret key between two parties, for instance in order to com- municate privately. In this paper we consider information-theoretically secure key agreement. Wyner and subsequently Csisz¶ar and KÄorner de- scribed and analyzed settings for secret-key agreement based on noisy communication channels. Maurer as well as Ahlswede and Csisz¶ar gen- eralized 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 de¯ned as the maximal achiev- able rates at which a highly-secret key can be generated by the legitimate partners. However, the privacy requirements were too weak in all these de¯nitions, requiring only the ratio between the adversary's information and the length of the key to be negligible, but hence tolerating her to ob- tain a possibly substantial amount of information about the resulting key in an absolute sense. We give natural stronger de¯nitions of secrecy ca- pacity and secret-key rate, requiring that the adversary obtains virtually no information about the entire key. We show that not only secret-key agreement satisfying the strong secrecy condition is possible, 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 de¯nitions can be completely replaced by the new ones. We prove these results by a generic reduction of strong to weak key agreement. The reduction makes use of extractors, which allow to keep the required amount of communication negligible as compared to the length of the resulting key.
Search
Reviews
[Write a review of this article]
Find related articles from these CiteULike users
