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.