Wire-Tap Channel II

TLDR

The study examines a communication scenario where K data bits are encoded into N > K bits over a noiseless channel. The goal is to design an encoder that maximizes an intruder’s uncertainty about the data given μ intercepted bits while ensuring the intended receiver can perfectly recover the K data bits from the N channel bits. The authors encode K data bits into N channel bits, allowing an intruder to observe any μ < N bits, and design the encoding to satisfy the recovery and uncertainty constraints. They derived optimal trade‑offs among K, N, μ and the intruder’s conditional entropy H, showing that when μ = N−K a system exists with H ≈ K−ℓ, and for N = 2K, μ = K the intruder learns at most one bit.

Abstract

Consider the following situation. K data bits are to be encoded into N> K bits and transmitted over a noiseless channel. An intruder can observe a subset of his choice of size μ < N. The encoder is to be designed to maximize the intruder's uncertainty about the data given his μ intercepted channel bits, subject to the condition that the intended receiver can recover the K data bits perfectly from the N channel bits. The optimal trade-offs among the parameters K, N, and μ and the intruder's uncertainty H (H is the "conditional entropy" of the data given the μ intercepted channel bits) were found. In particular, it was shown that for μ = N − K, a system exists with H ≈ K − l. Thus, for example, when N = 2K and μ = K, it is possible to encode the K data bits into 2K channel bits, so that by looking at any K channel bits, the intruder obtains no more than one bit of the data.