Privacy Amplification by Public Discussion

TLDR

Alice and Bob seek to share a secret bit string using an imperfect private channel that can be corrupted or eavesdropped on, and a perfect public channel that is fully observable by an eavesdropper. The paper investigates how a perfectly authentic but non‑private channel can be used to repair the defects of an imperfectly private channel. The authors propose interactive public‑channel protocols that first evaluate the corruption of the private‑channel transmission and then, when corruption is limited, distill a shorter, perfectly secret string from the transmitted and received versions. These protocols are proven secure even against adversaries with unlimited computational power.

Abstract

In this paper, we investigate how the use of a channel with perfect authenticity but no privacy can be used to repair the defects of a channel with imperfect privacy but no authenticity. More precisely, let us assume that 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. The private channel is imperfect in various ways: 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. On the other hand, the public channel transmits information accurately, and these transmissions cannot be modified or suppressed by Eve, but their entire contents becomes known to her. We consider the situation in which a random bit string x has already been transmitted from Alice to Bob over the private channel, and we describe interactive public channel protocols that allow them, 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, while Eve has nearly no information (or in some cases exactly none), except for its length. These protocols remain secure against unlimited computing power.