Paper 2017/1130

Information-Theoretic Secret-Key Agreement: The Secret-Key Rate as a Function of the Channel Quality Ratio

Daniel Jost and Ueli Maurer and Joao L. Ribeiro

Abstract

Information theoretically secure secret-key exchange between two parties, Alice and Bob, is a well-studied problem that is provably impossible without additional assumptions. However, it has shown to be feasible in a model where -- in addition to an authenticated communication channel -- 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 eavesdropper, Eve, via antennas of different sizes, which is modeled as receiving the bits through independent binary symmetric channels with error probabilities $\epsilon_A$, $\epsilon_B$, and $\epsilon_E$, respectively, where typically $\epsilon_E\ll\epsilon_A\approx\epsilon_B$. The secret-key rate is then defined as the maximal rate, per random bit, at which Alice and Bob can agree on secret key bits about which Eve has arbitrarily little information. While in computational cryptography the relevant parameter in a security analysis is a bound on Eve's computing power, the corresponding quantity in the satellite setting is a bound on Eve's antenna size. In this work, we study the optimal secret-key rate in the satellite setting as a function of the ratio $Q$ of Eve's tolerable antenna size and the honest parties' antenna size. Technically, we consider the ratio $Q$ of the capacities of the corresponding binary symmetric channels, which corresponds roughly to the antenna size ratio, and we consider the satellite's sending signal strength as a system design parameter that can be optimized. This setting was first considered by Gander and Maurer (ISIT 1994), who conjectured based on numerical evidence that the secret-key rate of the parity-check protocol decreases like $1/Q^2$. As a first contribution, we prove that this is actually the case, and also prove that this rate is asymptotically optimal, i.e., no protocol can achieve an asymptotically better rate in a setting where $\epsilon_A \approx \epsilon_B$. As a second contribution, we consider the secret-key rate per second rather than per transmitted bit, which might be of higher practical interest, given that one particular way of adjusting the signal strength is to adjust the bit-rate at which the satellite broadcasts. To this end, we introduce a quantity that approximates the secret-key rate per second, prove that for the parity-check protocol this quantity decreases like $1/Q$, and prove again that this is optimal. The difference between quadratic and linear decrease is quite significant in the satellite setting because it is plausible for Eve's antenna to be orders of magnitude larger than Alice's and Bob's.