Paper 2011/063

Secret Keys from Channel Noise

Hadi Ahmadi and Reihaneh Safavi-Naini

Abstract

We study the problem of unconditionally secure Secret Key Establishment (SKE) when Alice and Bob are connected by two noisy channels in opposite directions, and the channels are eavesdropped by Eve. We consider the case that Alice and Bob do not have any sources of initial randomness at their disposal. We start by discussing special cases of interest where SKE is impossible, and then provide a simple SKE construction over a binary symmetric channel that achieves some rates of secret key. We next focus on the Secret Key (SK) capacity, i.e., the highest rate of secure and reliable key establishment (in bits per channel use) that the parties can achieve. Relying on the existence of capacity-achieving coding schemes, we propose a multi-round SKE protocol, called the \emph{main protocol}, that proves a lower bound on the SK capacity. The main protocol consists of an initialization round, followed by repeated use of a two-round SKE protocol, called the \emph{basic protocol}. We also provide an upper bound on the SK capacity and show that the two bounds coincide when channels do not leak information to the adversary. We apply the results to the case that communicants are connected by binary symmetric channels.

Note: The full version includes more details and proofs in the appendix.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. This is the full version of a paper accepted to Eurocrypt 2011
Keywords
Secret key capacityKey establishmentDiscrete memoryless broadcast channel
Contact author(s)
hahmadi @ ucalgary ca
History
2011-03-08: revised
2011-02-08: received
See all versions
Short URL
https://ia.cr/2011/063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/063,
      author = {Hadi Ahmadi and Reihaneh Safavi-Naini},
      title = {Secret Keys from Channel Noise},
      howpublished = {Cryptology ePrint Archive, Paper 2011/063},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/063}},
      url = {https://eprint.iacr.org/2011/063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.