Information-Theoretic Secret-Key Agreement: The Asymptotically Tight Relation Between the Secret-Key Rate and the Channel Quality Ratio

Daniel Jost , Ueli Maurer, and João L. Ribeiro

Theory of Cryptography — TCC 2018, LNCS, Springer International Publishing, vol. 11239, pp. 345–369, Nov 2018.

Information-theoretically secure secret-key agreement between two parties Alice and Bob is a well-studied problem that is provably impossible in a plain model with public (authenticated) communication, but is known to be possible in a model where the parties also have access to some correlated randomness. One particular type of such correlated randomness is the so-called satellite setting, where a source of uniform random bits (e.g., sent by a satellite) is received by the parties and the adversary Eve over inherently noisy channels. The antenna size determines the error probability, and the antenna is the adversary's limiting resource much as computing power is the limiting resource in traditional complexity-based security. The natural assumption about the adversary is that her antenna is at most $Q$ times larger than both Alice's and Bob's antenna, where, to be realistic, $Q$ can be very large.

The goal of this paper is to characterize the secret-key rate per transmitted bit in terms of $Q$ . Traditional results in this so-called satellite setting are phrased in terms of the error probabilities $ϵ_{A}$ , $ϵ_{B}$ , and $ϵ_{E}$ , of the binary symmetric channels through which the parties receive the bits and, quite surprisingly, the secret-key rate has been shown to be strictly positive unless Eve's channel is perfect ( $ϵ_{E} = 0$ ) or either Alice's or Bob's channel output is independent of the transmitted bit (i.e., $ϵ_{A} = 0.5$ or $ϵ_{B} = 0.5$ ). However, the best proven lower bound, if interpreted in terms of the channel quality ratio $Q$ , is only exponentially small in $Q$ . The main result of this paper is that the secret-key rate decreases asymptotically only like $1 / Q^{2}$ if the per-bit signal energy, affecting the quality of all channels, is treated as a system parameter that can be optimized. Moreover, this bound is tight if Alice and Bob have the same antenna sizes.

Motivated by considering a fixed sending signal power, in which case the per-bit energy is inversely proportional to the bit-rate, we also propose a definition of the secret-key rate per second (rather than per transmitted bit) and prove that it decreases asymptotically only like $1 / Q$ .

BibTeX Citation

@inproceedings{JoMaRi18,
    author       = {Daniel Jost  and Ueli Maurer and João L. Ribeiro},
    title        = {Information-Theoretic Secret-Key Agreement: The Asymptotically Tight Relation Between the Secret-Key Rate and the Channel Quality Ratio},
    editor       = {Beimel, Amos and Dziembowski, Stefan},
    booktitle    = {Theory of Cryptography --- TCC 2018},
    pages        = {345--369},
    series       = {LNCS},
    volume       = {11239},
    year         = {2018},
    month        = {11},
    publisher    = {Springer International Publishing},
}