September 12, 1995
Abstract -
It is often desirable that distant terminals have access to common
randomness/CR, i.e., to the outcome of the same random experiment. In
information theory, the role of CR is basic for identification via chan-
nels, for transmission using random codes, e.g., for arbitrarily varying
channels, and for secure communication, where CR secret from the eaves-
dropper is needed.
In this talk, two-terminal models will be considered that involve a block-length parameter n. One example is when the resources for genera- ting CR consist in the terminals' access to /correlated/ side informa- tion represented by the first resp. second components of n independent repetitions of a pair of random variables (X,Y), and to a noiseless channel over which nR bits may be transmitted, where R>0 is fixed. For models of this kind, the growth rate as n goes to infinity of the maximum amount of CR that can be generated for block-length n, is called the CR capacity, or the key-capacity if secrecy is also required.
Some exact results as well as bounds on such capacities
will be given. E.g., the key-capacity of the above model
equals the mutual information of X and Y, providing R
is sufficiently large. Here the eavesdropper is assumed
to "see" the communication between the terminals, hence
the secrecy of CR means its stochastic independence from
that communication. Models whose statistics depend on unknown
parameters will also be considered,
requiring CR of nearly uniform distribution no
matter what the unknown parameters are.