Linking information reconciliation and privacy amplification

Information reconciliation allows two parties knowing correlated random variables, such as a noisy version of the partner's random bit string, to agree on a shared string. Privacy amplification allows two parties sharing a partially secret string about which an opponent has some partial information, to distill a shorter but almost completely secret key by communicating only over an insecure channel, as long as an upper bound on the opponent’s knowledge about the string is known. The relation between these two techniques has not been well understood. In particular, it is important to understand the effect of side-information, obtained by the opponent through an initial reconciliation step, on the size of the secret key that can be distilled safely by subsequent privacy amplification. The purpose of this paper is to provide the missing link between these techniques by presenting bounds on the reduction of the Rényi entropy of a random variable induced by side-information. We show that, except with negligible probability, each bit of side-information reduces the size of the key that can be safely distilled by at most two bits. Moreover, in the important special case of side-information and raw key data generated by many independent repetitions of a random experiment, each bit of side-information reduces the size of the secret key by only about one bit. The results have applications in unconditionally secure key agreement protocols and in quantum cryptography. This research was supported by the Swiss National Science Foundation. A preliminary version of this paper was presented at Eurocrypt '94, May 9–12, Perugia, Italy.