LINKING INFORMATION RECONCILIATION AND PRIVACY AMPLIFICATION

Information reconciliation allows two parties knowing correlated rando m variables, such as a noisy version of the partner's random bit strin g, to agree ori a shared string. Privacy amplification allows two part ies sharing a partially secret string about which an opponent has some partial information, to distill a shorter but almost completely secre t key by communicating only over an insecure channel, as long as an up per bound on the opponent's knowledge about the string is known. The r elation between these two techniques has not been well understood. In particular, it is important to understand the effect of side-informati on, obtained by the opponent through an initial reconciliation step, o n the size of the secret key that can be distilled safely by subsequen t privacy amplification. The purpose of this paper is to provide the m issing link between these techniques by presenting bounds on the reduc tion of the Renyi entropy of a random variable induced by side-informa tion. We show that, except with negligible probability, each bit of si de-information reduces the size of the key that can be safely distille d by at most two bits. Moreover, in the important special case of side -information and raw key data generated by many independent repetition s of a random experiment, each bit of side-information reduces the siz e of the secret key by only about one bit. The results have applicatio ns in unconditionally secure key agreement protocols and in quantum cr yptography.