Privacy amplification by public discussion

Abstract

Alice and Bob wish to agree on a secret random bit string, and have at their disposal an imperfect private channel and a perfect public channel. On the private channel transmission errors can occur, and partial information can leak to an eavesdropper, Eve, who also has the power to suppress, inject, and modify transmissions arbitrarily. The public channel transmits information accurately, and these transmissions cannot be modified or suppressed by Eve, but their entire contents become known to her. We describe interactive public channel protocols that allow Alice and Bob with high probability: (1) to assess the extent to which the private channel transmission has been corrupted by tampering and channel noise; and (2) if this corruption is not too severe, to repair Bob's partial ignorance of the transmitted string and Eve's partial knowledge of it by distilling from the transmitted and received versions of the string another string, in general shorter than x, upon which Alice and Bob have perfect information.