Wiretap Codes and Key-Efficient One-Time-Pad
Alice wants to send a message to Bob over a channel that is eavesdropped by a computationally unbounded adversary. She wants the message to remain perfectly private. Shannon and Wyner gave two ingenious solutions to this problem, both with provable security: Shannon’s solution assumes a reliable communication channel and a shared secret key, and Wyner’s solution assumes a noisy communication channel and Eve’s view of the ciphertext being cluttered by the channel “noise”.
We give a shared key construction that allows Alice and Bob to take advantage of the channel noise when present, to reduce the length of the shared secret key. When the channel is perfectly reliable, the construction reduces to a one-time-pad, and when it is sufficiently noisy, it becomes a Wyner’s wiretap code, providing perfect security without a shared key.