Channel upgrading for semantically-secure encryption on wiretap channels

Bellare and Tessaro recently introduced a new coding scheme, based on cryptographic principles, that guarantees strong security for a wide range of symmetric wiretap channels. This scheme has numerous advantages over alternative constructions, including constructions based on polar codes. However, it achieves secrecy capacity only under a certain restrictive condition. Specifically, let V be the main channel (from Alice to Bob) and let W be wiretap channel (from Alice to Eve). Suppose that W has a finite output alphabet y, and let X and Y denote the input and output of W, respectively. Then the rate of the Bellare-Tessaro coding scheme is at most I(V) - Ψ(W), where I(V) is the capacity of V and Ψ(W) is given by Ψ(W) = log
₂
|y|-H(Y|X). For symmetric channels, it is clear that Ψ(ΨW) ≥ I(W) with equality if and only if uniform input to W produces uniform output. Unfortunately, few symmetric DMCs satisfy this condition. In this paper, we show how the Bellare-Tessaro coding scheme can be extended to achieve secrecy capacity in the case where W is an arbitrary symmetric DMC. To this end, we solve the following problem. Given W and ε > 0, we construct another channel Q such that W is degraded with respect to Q while the difference between Ψ(<;3) and I(W) is at most ε. We also solve a closely related problem, where the output alphabet of Q is required to be of a given size M. In this case, we construct a channel Q that is equivalent to W, such that Ψ(<;3) is a small as possible. We furthermore extend these results, and thereby the applicability of the Bellare-Tessaro coding scheme, to channels with binary input and continuous output.