Privacy Amplification Secure Against Active Adversaries
Ueli Maurer and Stefan Wolf
Privacy amplification allows two parties Alice and Bob knowing a partially secret string $S$ to extract, by communication over a public channel, a shorter, highly secret string $S'$. Bennett, Brassard, Cré}peau, and Maurer showed that the length of $S'$ can be almost equal to the conditional Renyi entropy of $S$ given an opponent Eve's knowledge. All previous results on privacy amplification assumed that Eve has access to the public channel but is passive or, equivalently, that messages inserted by Eve can be detected by Alice and Bob. In this paper we consider privacy amplification secure even against active opponents. First it is analyzed under what conditions information-theoretically secure authentication is possible even though the common key is only partially secret. This result is used to prove that privacy amplification can be secure against an active opponent and that the size of $S'$ can be almost equal to Eve's min-entropy about $S$ minus $2n/3$ if $S$ is an $n$-bit string. Moreover, it is shown that for sufficiently large $n$ privacy amplification is possible when Eve's min-entropy about $S$ exceeds only $n/2$ rather than $2n/3$.