International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

João L. Ribeiro

Publications

Year
Venue
Title
2018
TCC
Information-Theoretic Secret-Key Agreement: The Asymptotically Tight Relation Between the Secret-Key Rate and the Channel Quality Ratio
Daniel Jost Ueli Maurer João L. Ribeiro
Information-theoretic 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 uniform random bits (e.g., sent by a satellite) are 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 $$\epsilon _A$$ϵA, $$\epsilon _B$$ϵB, and $$\epsilon _E$$ϵ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 ($$\epsilon _E=0$$ϵE=0) or either Alice’s or Bob’s channel output is independent of the transmitted bit (i.e., $$\epsilon _A=0.5$$ϵA=0.5 or $$\epsilon _B=0.5$$ϵ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$$1/Q2 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.

Coauthors

Daniel Jost (1)
Ueli Maurer (1)