The Strong Secret Key Rate of Discrete Random Triples
Ueli Maurer
Three parties, Alice, Bob and Eve, know the sequences of random variables $X^N=[X_1,X_2,\ldots X_N]$, $Y^N=[Y_1,Y_2,\ldots Y^N]$ and $Z^N=[Z_1,Z_2,\ldots Z_N]$, respectively, where the triples $(X_iY_iZ_i)$, for $1\leq i\leq N$, are generated by a discrete memoryless source according to some probability distribution $P_{XYZ}$. Motivated by Wyner's and Csiszár and Körner's pioneering definition of, and work on, the secrecy capacity of a broadcast channel, the secret key rate of $P_{XYZ}$ was defined by Maurer as the maximal rate $M/N$ at which Alice and Bob can generate secret shared random key bits $S_1, \dots, S_M$ by exchanging messages over an insecure public channel accessible to Eve, such that the rate at which Eve obtains information about the key is arbitrarily small, i.e., such that $\lim_{N\to\infty}I(S_1, \dots, S_M;Z^N,C^t)/N=0$, where $C^t$ is the collection of messages exchanged between Alice and Bob over the public channel. However, this definition is not completely satisfactory because only the rate, but not the total amount of information about the key obtained by Eve is bounded. This paper introduces and investigates the strong secret key rate: it is required that the total amount of information about the key obtained by Eve be negligible, i.e. $\lim_{N\to\infty}I(S_1, \dots, S_M;Z^N,C^t)=0$, and that $[S_1, \dots, S_M]$ be arbitrarily close to uniformly distributed, i.e. $\lim_{N\to\infty}M-H([S_1, \dots, S_M])=0$. Using novel results on privacy amplification by Bennett, Brassard, Crépeau and Maurer we demonstrate that the known results for the secret key rate also hold for the stronger definition.
BibTeX Citation
@incollection{Maurer94a,
author = {Ueli Maurer},
title = {The Strong Secret Key Rate of Discrete Random Triples},
editor = {R. Blahut},
booktitle = {Communication and Cryptography --- Two Sides of One Tapestry},
pages = {271--285},
year = {1994},
publisher = {Kluwer Academic Publishers},
}