Beyond the Csiszár–Körner Bound: Best-Possible Wiretap Coding via Obfuscation

Yuval Ishai¹,
Alexis Korb²,
Paul Lou² &
…
Amit Sahai²

1305 Accesses
Explore all metrics

Abstract

A wiretap coding scheme (Wyner in Bell Syst Tech J 54(8):1355–1387, 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel $\textsf{ChB}$, while at the same time hiding m from Eve who receives c over another noisy channel $\textsf{ChE}$. Wiretap coding is clearly impossible when $\textsf{ChB}$ is a degraded version of $\textsf{ChE}$, in the sense that the output of $\textsf{ChB}$ can be simulated using only the output of $\textsf{ChE}$. A classic work of Csiszár and Korner (IEEE Trans Inf Theory 24(3):339–348, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs $(\textsf{ChB},\textsf{ChE})$ that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does hold when considering computational security; that is, wiretap coding against a computationally bounded Eve is possible if and only if $\textsf{ChB}$ is not a degraded version of $\textsf{ChE}$. Our construction assumes the existence of virtual black-box obfuscation of specific classes of “evasive” functions that generalize fuzzy point functions and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice’s algorithm depends only on $\textsf{ChB}$ and not on $\textsf{ChE}$.

Beyond the Csiszár-Korner Bound: Best-Possible Wiretap Coding via Obfuscation

Hash-then-Encode: A Modular Semantically Secure Wiretap Code

A Virtual Wiretap Channel for Secure Message Transmission

Use our pre-submission checklist

Avoid common mistakes on your manuscript.

1 Introduction

The wiretap channel, first introduced by Wyner [30], captures a unidirectional communication setting in which Alice transmits an encoding of a message across two discrete memoryless channels over constant-sized alphabets: a main channel (Bob’s channel) for the intended receiver Bob and an eavesdropping channel (Eve’s channel) for an adversarial receiver Eve. Two conditions are desired: correctness and security. Informally, correctness guarantees that Bob can decode the message with overwhelming probability, and security requires that Eve learn essentially nothing about the message. The wiretap coding problem is then to find a (randomized) encoding algorithm that satisfies both conditions. The wiretap coding question represents a basic and fundamental question regarding secure transmission over noisy channels, and indeed Wyner’s work has been incredibly influential: Google Scholar reports that the literature citing [30] surpasses 7000 papers, and Wyner’s work is considered the foundational work on using noisy channels for cryptography. Much of the interest in this question comes from its relevance to physical layer security, a large area of research that exploits physical properties of communication channels to enhance communication security through coding and signal processing. See, e.g., [28] for a survey.

The classic work of Csiszár and Korner [10] completely characterized the pairs of channels for which wiretap coding is possible information theoretically. Roughly speaking, their work defined a notion of one channel being less noisy than the other (see Definition 3.7), and they proved that wiretap coding is possible information theoretically if and only if Eve’s channel is not less noisy than Bob’s channel.

To illustrate this, let’s consider a specific case: suppose that Bob’s channel is a binary symmetric channel, flipping each bit that Alice sends with probability $p=0.1$; at the same time, suppose Eve’s channel is a binary erasure channel, erasing each bit that Alice sends (i.e., replacing it with $\bot $) with probability $\epsilon $. Then, it turns out [27] that Eve’s channel is not less noisy than Bob’s channel if and only if $\epsilon > 0.36 = 4p(1-p)$, and thus by [10], information-theoretic wiretap coding is only possible under this condition.

A new feasibility result for wiretap coding In cryptography, we often take for granted that assuming adversaries to be computationally bounded should lead to improved feasibility results. Indeed, we have seen this many times especially in the early history of cryptography: from re-usable secret keys for encryption [6, 31] to the feasibility of secure multi-party computation with a dishonest majority [14]. However, despite the popularity of Wyner’s work, no improvement over [10] in terms of feasibility against computationally bounded adversaries has been obtained in over 40 years.

Nevertheless, in this work, we ask: is it possible to obtain new feasibility results for wiretap coding for computationally bounded eavesdroppers?

Taking a fresh look at this scenario, we observe that if $\epsilon \le 0.2 = 2p$, then wiretap coding is completely impossible: If $\epsilon \le 0.2=2p$, then Eve can simulate Bob’s channel. For example, if $\epsilon = 0.2=2p$, then Eve can assign each $\bot $ that she receives a uniform value in $\{0,1\}$, and this would exactly yield a binary symmetric channel with flip probability $p=0.1$, thus exactly simulating the distribution received by Bob. Since wiretap coding is non-interactive, if Bob can recover the message with high probability, then so can Eve, violating security. Indeed, whenever Eve can efficiently simulate Bob’s channel, we say that Bob’s channel is a degraded version of Eve’s channel [9]. When this is true, wiretap coding is clearly impossible, even for efficient eavesdroppers Eve.

In our main result, we show that assuming secure program obfuscation for simple specific classes of functionalities (as we describe in more detail below), the above limitation presents the only obstacle to feasibility of wiretap coding against computationally bounded eavesdroppers. In particular, for the scenario described above, we show that wiretap coding is possible whenever $\epsilon > 0.2 = 2p$, even though [10, 27] showed that information-theoretic wiretap coding is impossible for $\epsilon <0.36=4p(1-p)$. More generally, we show that wiretap coding is possible whenever Bob’s channel is not a degraded version of Eve’s channel. We now describe our results in more detail.

1.1 Our Contributions

Let $\textsf{ChB}$ represent Bob’s channel, and let $\textsf{ChE}$ represent Eve’s channel. Observe that the input alphabets for the channels $\textsf{ChB}$ and $\textsf{ChE}$ must be identical; we will denote this input alphabet by ${{\mathcal {X}}}$, and consider 1-bit messages for simplicity.^{Footnote 1}

We first consider an oracle-based model in which a wiretap coding scheme consists of two algorithms:

${{\,\textrm{Enc}\,}}(1^\lambda , m)$: The (randomized) encoder takes as input a security parameter $\lambda $ and a message bit $m \in \{0, 1\}$. The output of ${{\,\textrm{Enc}\,}}$ consists of: (1) a string $c \in {{{\mathcal {X}}}}^*$, and (2) a circuit describing a function f. The string c is transmitted over channels $\textsf{ChB}$ and $\textsf{ChE}$ to Bob and Eve respectively. However, both Bob and Eve are granted oracle access to f.
${{\,\textrm{Dec}\,}}^{f}(y)$: The deterministic decoder is a polynomial-time oracle algorithm with oracle access to f. ${{\,\textrm{Dec}\,}}^{f}$ takes as input the string y received by Bob over his channel.

We obtain our main result in two steps. In our first and primary step, we prove:

Theorem 1.1

(Informal) For any pair of discrete memoryless channels $(\textsf{ChB}, \textsf{ChE})$ where $\textsf{ChB}$ is not a degraded version of $\textsf{ChE}$, there exist PPT encoding and decoding algorithms $({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}}^{(\cdot )})$ which achieve:

Correctness: For all messages $m \in \{0,1\}$,
$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}^{f}(1^\lambda , \textsf{ChB}(c)) = m \mid (f, c) \leftarrow {{\,\textrm{Enc}\,}}(1^\lambda , m)] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$
Security: For all computationally unbounded adversaries $\mathcal A^{(\cdot )}$ that are allowed to make polynomially many queries to their oracle,
$$\begin{aligned}\Pr [\mathcal A^{f_b}(1^\lambda , \textsf{ChE}(c_b)) = b \mid (f_b, c_b) \leftarrow {{\,\textrm{Enc}\,}}(1^\lambda , b)] \le \frac{1}{2} + \textsf{negl}(\lambda )\end{aligned}$$
where b is uniformly distributed over $\{0,1\}$.

Theorem 1.1 can be viewed as an unconditional construction using an ideal obfuscation of the oracle f. Our use of obfuscation in this context was inspired by the recent work of Agrawal et al. [1], which used ideal obfuscation to obtain a new feasibility result for secure computation using unidirectional communication over noisy channels (see Sect. 1.2 for comparison and more related work).

In our second step, we show how to bootstrap from Theorem 1.1 to obtain wiretap coding in the plain model secure against computationally bounded adversaries, via a suitable form of cryptographic program obfuscation. More concretely, we use the notion of virtual black-box (VBB) obfuscation for evasive circuits [3] for a specific class of evasive circuits that we call generalized fuzzy point functions and with a very simple kind of auxiliary information that corresponds to the message that Eve receives when Alice transmits a uniformly random message across Eve’s channel (see Sect. 7 for details). Using this kind of obfuscation, we obtain the following result in the plain model:

Theorem 1.2

(Informal) Assume that $\mathcal O$ is a secure evasive function obfuscation scheme for the class of generalized fuzzy point functions. Then, for any pair of discrete memoryless channels $(\textsf{ChB}, \textsf{ChE})$ where $\textsf{ChB}$ is not a degraded version of $\textsf{ChE}$, there exist PPT encoding and decoding algorithms $({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ which achieve:

Correctness: For all messages $m \in \{0,1\}$,
$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}(1^\lambda , \mathcal O(f),\textsf{ChB}(c)) = m \mid (f, c) \leftarrow {{\,\textrm{Enc}\,}}(1^\lambda , m)] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$
Security: For all computationally bounded adversaries $\mathcal A$,
$$\begin{aligned}\Pr [\mathcal A(1^\lambda , \mathcal O(f_b), \textsf{ChE}(c_b)) = b \mid (f_b, c_b) \leftarrow {{\,\textrm{Enc}\,}}(1^\lambda , b)] \le \frac{1}{2} + \textsf{negl}(\lambda )\end{aligned}$$
where b is uniformly distributed over $\{0,1\}$.

Note that since $\mathcal O(f)$ can be made public to both Bob and Eve, it can be communicated by using a standard encoding scheme for $\textsf{ChB}$, with no security requirements.

On instantiating obfuscation We conjecture that indistinguishability obfuscation (iO) provides a secure realization of the obfuscation needed in our wiretap coding scheme. The recent work of [20] provides a construction of iO from well-studied hardness assumptions, and thus gives a conservative and explicit candidate realization. We provide several arguments in favor of our conjecture (see Sect. 7 for details regarding all the points below):

First, we stress that VBB obfuscation for evasive circuit families is not known to be subject to any impossibility results, under any hardness assumptions, even wildly speculative ones. This is because the notion of evasiveness that we consider is statistical in the following sense: even a computationally unbounded Eve, that can make any polynomially bounded number of queries to our oracle, cannot find an input z to the oracle f such that $f(z)=1$. This property rules out all known techniques for proving impossibility of obfuscation that we are aware of (c.f. [4, 15]). But in fact, our situation is even further away from impossibility results because we obfuscate simple distributions of evasive functions that generalize random fuzzy point functions and only need to leak simple auxiliary information about the obfuscated function.
Furthermore, in fact, the work of [2] gives a construction of VBB obfuscation for evasive circuits from multilinear maps, which is designed to be immune to all known attacks on multilinear map candidates, and has never been successfully attacked.
Finally, indistinguishability obfuscation is a “best-possible obfuscation" [17], and therefore, roughly speaking, if any way exists to securely realize the ideal oracle in our construction to achieve wiretap coding, then using iO must also yield secure wiretap coding.

Optimal-rate wiretap coding We stress that the problem of achieving asymptotically optimal rate follows almost immediately from our solution to the feasibility question above. This is because the feasibility solution can be used to transmit a secret key, and then the encrypted message can be transmitted using any reliable coding scheme to Bob. The security of encryption will ensure that even if Eve learns the ciphertext, because she is guaranteed not to learn the encryption key due to our solution to the feasibility problem above, the (computationally bounded) Eve cannot learn anything about the message. Using standard Rate 1 symmetric key encryption, therefore, we achieve asymptotic wiretap coding rate equal to the capacity of Bob’s channel, regardless of the quality of Eve’s channel.

Universal wiretap coding An appealing feature of our solution to the wiretap problem is that it gives a universal encoding, meaning that $({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ depend only on the main channel $\textsf{ChB}$ and not on the eavesdropper’s channel $\textsf{ChE}$. This is not possible in the information-theoretic regime.

1.2 Related Works

Our work was inspired by the recent work of Agrawal et al. [1], who proposed a similar obfuscation-based approach for establishing a feasibility result for secure computation over unidirectional noisy channels. In contrast to our work, the use of ideal obfuscation in [1] applies to more complex functions that are not even “evasive” in the standard sense. We stress that beyond inspiration and a common use of obfuscation, there is no other technical overlap between [1] and our work.

Another closely related line of work studies the notion of fuzzy extractors, introduced by Dodis et al. [11]. A fuzzy extractor can be used to encode a message m in a way that: (1) any message $m'$ which is “close” to m (with respect to some metric) can be used to decode m, and (2) if m has sufficiently high min-entropy, its encoding hides m. The possibility of constructing strong forms of computational fuzzy extractors from strong forms of fuzzy point function obfuscation was discussed by Canetti et al. [7] and Fuller et al. [12]. The wiretap coding problem can be loosely cast as a variant of fuzzy extractors where the metric is induced by the main channel $\textsf{ChB}$ and security should hold with respect to a specific entropic source defined by the eavesdropper’s channel $\textsf{ChE}$. The latter relaxation makes the notion of obfuscation we need qualitatively weaker.

Various extensions to the wiretap setting have been studied in the information theoretic setting, and we discuss a very limited subset here that relate most closely to our work. Further generalizations were made by Liang et al’s [23] introduction of the compound wiretap channel, in which there are finitely many honest receiver and finitely many eavesdroppers, modeling a transmitter’s uncertainty about the receiver’s channel and the eavesdropper’s channel. The upper and lower bounds on secrecy capacity of the compound wiretap channel suggest the impossibility of positive rate universal encodings. Maurer [26] showed that a public channel and interaction between the transmitter and honest receiver circumvent the necessity of $\textsf{ChE}$ being not less noisy than $\textsf{ChB}$ for security.^{Footnote 2} We stress that the focus of our paper is the non-interactive case, without any feedback channels. Nair [27] studied information-theoretic relationships between $\textsf{BSC}$ and $\textsf{BEC}$ channels.

Bellare et al. [5] introduced stronger security notions for wiretap coding than the notions that existed within the information theoretic community. In particular, they introduced an information theoretic notion of semantic security, which we also achieve in our work. They also provided an efficient information-theoretic encoding and decoding scheme for many channels that achieves correctness, semantic security, and rate achieving the Csiszár–Korner bound. Previously, most works on wiretap coding had only proven the existence of wiretap encoding and decoding schemes, and not provided explicit constructions.

Finally, the wiretap problem we study is also related to other fuzzy cryptographic primitives, including fuzzy vaults [21] and fuzzy commitments [22]. However, our work is technically incomparable because they use different definitions of noise and study security in different regimes. In both cases, the achieved parameters are not optimal (certainly not in a computational setting), whereas our construction achieves the best possible parameters.

2 Technical Overview

In the wiretap setting, we consider two discrete memoryless channels (DMCs): $\textsf{ChB}:\mathcal X\rightarrow \mathcal Y$ from Alice to the intended receiver Bob, and $\textsf{ChE}:\mathcal X\rightarrow \mathcal Z$ from Alice to an eavesdropper Eve. Alice’s goal is to transmit an encoding of a message $m \in \mathcal M= \{0,1\}$ across both channels so that Bob can decode m with high probability and Eve learns negligible information about m. Our goal is to build an encoder and a decoder that satisfies these requirements.

Definition 2.1

(Discrete memoryless channel (DMC)) We define a discrete memoryless channel (DMC) $\textsf{ChW}:\mathcal X\rightarrow \mathcal Y$ to be a randomized function from input alphabet $\mathcal X$ to output alphabet $\mathcal Y$. We associate $\textsf{ChW}$ with its stochastic matrix ${P_W}= [p_W(y|x)]_{x \in \mathcal X, y \in \mathcal Y}$.

Warmup: The $\textsf{BSC}_{0.1}$-$\textsf{BEC}_{0.3}$ Wiretap Setting We first consider a simple example. Consider a wiretap setting in which Alice has a $\textsf{BSC}_{0.1}$ between her and Bob and a $\textsf{BEC}_{0.3}$ between her and Eve. Alice wishes to send $m \in \{0,1\}$ to Bob, but not to Eve. First observe that on a uniform random input distribution, Eve’s information about the input is greater than Bob’s information. Indeed, Eve’s $\textsf{BEC}_{0.3}$ channel has greater capacity than Bob’s $\textsf{BSC}_{0.1}$ channel. In fact, it can be proven [10, 27] that in the information theoretic setting with these channel parameters, then there does not exist any encoding scheme that Alice can use to encode her message so that Bob can decode with high probability but Eve cannot.

Acknowledging this obstacle, how can we favor Bob’s decoding probability and disadvantage Eve in the computational setting? A simple observation is that on a uniform random input $r \in \{0,1\}^n$ to the channels, then Bob’s output distribution is different from Eve’s output distribution. Indeed, for large enough n, Bob’s $\textsf{BSC}_{0.1}$’s output ${r_B}$ should contain approximately 10% bit flips relative to r, whereas Eve’s $\textsf{BEC}_{0.3}$ output ${r_E}$ should contain approximately 30% erasures.

Now, suppose Bob and Eve both had access to an oracle that outputs m on binary inputs containing approximately 10% bit flips relative to r and outputs $\bot $ on all other inputs. Then, Bob can decode m by simply sending his received output ${r_B}$ to the oracle. However, in order to learn m, Eve must be able to guess a ${\widehat{r}_B}{}$ that has 10% bit flips relative to r. It is simple to observe that Eve’s best strategy for guessing such an ${\widehat{r}_B}{}$ is to generate it from her channel output ${r_E}$ by replacing each erasure in ${r_E}$ with a uniformly random bit. But observe that with high probability this ${\widehat{r}_B}{}$ will contain roughly 15% bit flips relatives to r. Thus, with high probability, Eve cannot generate a ${\widehat{r}_B}{}$ with only 10% bit flips, so she cannot learn m.

This motivates our use of the ideal obfuscation model in which Alice, in addition to specifying a string r to send across both channels can also specify an oracle f which is perfectly transmitted to Bob and Eve who get bounded access to the oracle. In this model, we can achieve secure wiretap coding schemes. To encode $m \in \{0,1\}$, Alice picks a random string r that will be sent across both channels and specifies the oracle mentioned above which is perfectly transmitted to Bob and Eve. By the above argument, this encoding satisfies both correctness and security.

Handling all Non-degraded Channels Now, consider the case where Bob’s channel $\textsf{ChB}: \mathcal X\rightarrow \mathcal Y$ and Eve’s channel $\textsf{ChE}: \mathcal X\rightarrow \mathcal Z$ are arbitrary channels with the same input domain $\mathcal X$ with the sole restriction that $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$. We first build intuition about channel degradation.

Definition 2.2

(Channel degradation) We say that channel $\textsf{ChB}$ is a degradation of channel $\textsf{ChE}$ if there exists a channel $\textsf{ChS}$ such that

$$\begin{aligned}\textsf{ChB}= \textsf{ChS}\circ \textsf{ChE}\end{aligned}$$

where $\circ $ denotes channel concatenation, that is $(\textsf{ChS}\circ \textsf{ChE})(x) = \textsf{ChS}(\textsf{ChE}(x))$.

Observe that if $\textsf{ChB}$ is a degradation of $\textsf{ChE}$, then secure wiretap coding schemes are impossible even in the computational setting since then there exists a $\textsf{ChS}$ such that $\textsf{ChB}= \textsf{ChS}\circ \textsf{ChE}$, which means Eve can simulate Bob’s output by running her channel output through $\textsf{ChS}$ and thus learn as much information as Bob learns.

On the other hand, if $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$, then this means that for every channel $\textsf{ChS}$, there exists an $x^* \in \mathcal X$ and $y^* \in \mathcal Y$ such that

$$\begin{aligned}\left|{p_B}(y^* \mid x^*) - p_{E \cdot S}(y^* \mid x^*)\right| > 0\end{aligned}$$

where ${p_B}(y^* \mid x^*) = \Pr [\textsf{ChB}(x^*) = y^*]$ and $p_{E \cdot S}(y^* \mid x^*) = \Pr [\textsf{ChS}(\textsf{ChE}(x^*)) = y^*]$. In fact, by using properties of continuity and compactness, we can prove that there is a constant $d > 0$ such that for every $\textsf{ChS}$, there exists an $x^* \in \mathcal X$ and $y^* \in \mathcal Y$ such that

$$\begin{aligned}\left|{p_B}(y^* \mid x^*) - p_{E \cdot S}(y^* \mid x^*)\right| \ge d\end{aligned}$$

Now, define the following notation.

Definition 2.3

Let $\mathcal X$ and $\mathcal Y$ be any two discrete finite sets and let $n \in \mathbb {N}$. For $r\in \mathcal X^n$ and $s \in \mathcal Y^n$ and for any $x \in \mathcal X$ and $y \in \mathcal Y$, we define the fraction of x’s in $r$ that are y’s in s to be

$$\begin{aligned}{\textsc {Ratio}_{x \rightarrow y}}(r,s) = \frac{\left|\{i \in [n]: r_i = x, s_{i} = y\}\right|}{\left|\{i \in [n]:r_i = x\}\right|}.\end{aligned}$$

If $\left|i \in [n]: r_i = x\right| = 0$, then we define ${\textsc {Ratio}_{x \rightarrow y}}(r,s) = 0$.

Fix any $\textsf{ChS}: \mathcal Z\rightarrow \mathcal Y$ and let $x^*$ and $y^*$ be defined as above. Consider sending a uniform random string $r \in \mathcal X^n$ through $\textsf{ChB}$ and $\textsf{ChS}\circ \textsf{ChE}$. By a Chernoff bound, we expect that with high probability, ${\textsc {Ratio}_{x^* \rightarrow y^*}}(r, \textsf{ChB}(r))$ should be close to ${p_B}(y^* \mid x^*)$ and ${\textsc {Ratio}_{x^* \rightarrow y^*}}(r, \textsf{ChS}(\textsf{ChE}(r)))$ should be close to $p_{E \cdot S}(y^* \mid x^*)$. But since $p_{E \cdot S}(y^* \mid x^*)$ and ${p_B}(y^* \mid x^*)$ differ by a constant, we expect ${\textsc {Ratio}_{x^* \rightarrow y^*}}(r, \textsf{ChS}(\textsf{ChE}(r)))$ to differ by a constant from ${p_B}(y^* \mid x^*)$ with high probability.

Thus, ${\textsc {Ratio}_{x^* \rightarrow y^*}}$ forms a distinguisher between $\textsf{ChB}$ and $\textsf{ChS}\circ \textsf{ChE}$. Therefore, we can define the following function which outputs m with high probability on an input sampled from $\textsf{ChB}(r)$ and outputs m with negligible probability on an input sampled from $\textsf{ChS}(\textsf{ChE}(r))$ for any channel $\textsf{ChS}$.^{Footnote 3}

In fact, since we are considering the ratios of all pairs $(x,y) \in \mathcal X\times \mathcal Y$, the same observation holds for the following function that considers only one-sided bounds.

Construction Overview We now describe our coding scheme for wiretap channel $(\textsf{ChB}, \textsf{ChE})$. Our encoder ${{\,\textrm{Enc}\,}}_{\textsf{ChB}}$ takes a security parameter $1^\lambda $ and a message $m \in \mathcal M$ and outputs a description of a circuit computing some function f and a string $r \in \mathcal X^n$. Our decoder ${{\,\textrm{Dec}\,}}^{(\cdot )}$ takes as input a security parameter $1^\lambda $ and a string ${r_B}\in \mathcal Y^n$ and outputs some message in $\mathcal M$. The string r is sent across both channels, and both Bob and Eve obtain bounded oracle access to f.

For convenience, we define $R$ to be a uniform random input over $\mathcal X^n$, ${R_E}= \textsf{ChE}(R)$, and ${R_B}= \textsf{ChB}(R)$.

Correctness holds since Bob can decode with high probability since $f_{m, r, \textsf{ChB}, n}$ on $\textsf{ChB}(r)$ will output m with high probability.

Security Overview Now consider security. Intuitively, since r is independent of the message bit b, then Eve should only be able to learn b if she can generate a guess ${\widehat{r}_B}{}$ such that $f_{b, r, \textsf{ChB}, n}({\widehat{r}_B}{}) = b$. Consider a strategy g that given input ${r_E}\leftarrow \textsf{ChE}(r)$ from Eve’s channel seeks to produce an output ${\widehat{r}_B}{}$ that maximizes the probability that $f_{b, r, \textsf{ChB}, n}({\widehat{r}_B}{}) = f_{b, r, \textsf{ChB}, n}(g({r_E})) = b$. We say that g wins if this occurs and b is output.

If strategy g is to send Eve’s channel output ${r_E}$ through some discrete memoryless channel $\textsf{ChS}$ (i.e. $g({r_E}) = \textsf{ChS}({r_E})$), then by our previous discussion on non-degraded channels, there exists some $x^* \in \mathcal X$ and $y^* \in \mathcal Y$ such that with high probability, ${\textsc {Ratio}_{x^* \rightarrow y^*}}(r, g(\textsf{ChE}(r)))$ differs from ${p_B}(y^* \mid x^*)$ by at least a constant. Thus, such a g would only win with negligible probability.

However, Eve can choose any arbitrary strategy g. Nevertheless, we can still prove that any strategy g has only a negligible chance of winning. To do so, we show through a series of hybrids that any strategy g is only polynomially better than a strategy $\textsc {Eve}_3$, where $\textsc {Eve}_3$’s strategy is to apply a DMC independently to each symbol of ${r_E}$. Then, we can use the non-degraded condition to show that $\textsc {Eve}_3$’s probability of success on a single query to the oracle is negligible, and thus that any g’s probability of success on a single query to the oracle is negligible. This hybrid argument is the main technical argument in our work, and it is summarized below.

The Hybrid Argument: Proving g has a Negligible Chance of Winning We first observe that an arbitrary strategy g cannot perform better than an optimal strategy $g^*$ defined as follows:

Definition 2.4

For any m, we say that a strategy $g^*: \mathcal Z^n \rightarrow \mathcal Y^n$ for guessing ${\widehat{r}_B}{}$ is optimal if

$$\begin{aligned}g^* = \mathop {\mathrm {arg\,max}}\limits _{g}\left( \Pr _{R, \textsf{ChE}}[f_{m, R, \textsf{ChB}, n}(g({R_E})) = m]\right) .\end{aligned}$$

Now, consider any deterministic optimal strategy. (Observe that there always exists an optimal $g^*$ that is deterministic since $g^*$ can arbitrarily break ties in the maximum.)

Our first step is to simplify our function $g^*$ by a symmetrization argument. We observe that our definition of evaluation function $f_{m, r, \textsf{ChB}, n}$ on input ${\widehat{r}_B}{}$ considers only the mapping ratios ${\textsc {Ratio}_{x \rightarrow y}}(r, {\widehat{r}_B}{})$ for all $x \in \mathcal X, y \in \mathcal Y$ from r to ${\widehat{r}_B}{}$. An immediate consequence of this recollection is that the probability of success for Eve when the input string is r and the guessed string is ${\widehat{r}_B}{}= g^*({r_E})$ is permutation-invariant. That is, for every permutation $\pi \in S_n$, the probability of succeeding on ${\widehat{r}_B}{}$ when the input string is r is equivalent to the probability of succeeding on $\pi ({\widehat{r}_B}{})$ when the input string is $\pi (r)$ because

$$\begin{aligned}{\textsc {Ratio}_{x \rightarrow y}}(r, {\widehat{r}_B}{}) = {\textsc {Ratio}_{x \rightarrow y}}(\pi (r), \pi ({\widehat{r}_B}{})).\end{aligned}$$

Thus, since $r$ is uniformly random, then we have $\Pr [R= \pi (r)] = \Pr [R= r]$, so morally an optimal $g^*$’s success probability on ${r_E}$ and $\pi ({r_E})$ should be the same. This is formally seen by a symmetrization argument regarding the equivalence relation we define below.

Definition 2.5

For ${r_E}\in \mathcal Z^n$, we define the weight of ${r_E}$ as

$$\begin{aligned}\textsf{wt}({r_E}) = (N_{z_1}({r_E}), \ldots , N_{z_{|\mathcal Z|}}({r_E}))\end{aligned}$$

where $\mathcal Z= \{z_1, \ldots , z_{|\mathcal Z|}\}$ and $N_{z_i}({r_E}) = \left|i \in [n] \mid {r_E}_i = z_i\right|$. We define an equivalence relation $\textsc {Eqwt}$ on $\mathcal Z^n \times \mathcal Z^n$ by

$$\begin{aligned} \textsc {Eqwt}&= \{({r_E}, {r_E}') \in \mathcal Z^n \times \mathcal Z^n \mid \textsf{wt}({r_E}) = \textsf{wt}({r_E}') \}\\&= \{({r_E}, {r_E}') \in \mathcal Z^n \times \mathcal Z^n \mid \exists \pi \in S_n, \; {r_E}= \pi ({r_E}') \}. \end{aligned}$$

Let ${r_E}_{w, 0}$ denote the lexicographically first vector in the equivalence class $\{{r_E}\in \mathcal Z^n \mid \textsf{wt}({r_E}) = w\}$.

Then since $g^*$ performs equally well on all permutations of ${r_E}$, we can create a new optimal deterministic strategy $\textsc {Eve}_0$ which behaves in a structured manner on all strings ${r_E}$ from the same equivalence class. Importantly, $\textsc {Eve}_0$ has the nice property that for any permutation $\pi $, then $\pi (\textsc {Eve}_0({r_E})) = \textsc {Eve}_0(\pi ({r_E}))$.

Now, consider a probabilistic $\textsc {Eve}_1$ that on input ${r_E}\in \mathcal Z^n$ deviates slightly from the deterministic $\textsc {Eve}_0$. For any $z \in \mathcal Z$, $y \in \mathcal Y$, and input ${r_E}\in \mathcal Z^n$, observe that $\textsc {Eve}_0$ will map some deterministically chosen subset of size $k_{z,y}$ of the z’s in ${r_E}$ to be a y in ${\widehat{r}_B}{}$. Instead, we will have $\textsc {Eve}_1$ map a random subset of size $k_{z,y}$ of the z’s in ${r_E}$ to be a y in ${\widehat{r}_B}{}$. By a similar symmetrization argument and the construction of $\textsc {Eve}_0$, then $\textsc {Eve}_1$’s probability of success is equal to that of $\textsc {Eve}_0$.

Now, we relax the necessity of requiring that exactly $k_{z, y}$ of the z’s in ${r_E}$ map to y’s in ${\widehat{r}_B}{}$. This relaxation is done by defining a set of stochastic matrices that model a DMC. In particular, we use the probabilistic strategy of $\textsc {Eve}_1$ to define a set of DMCs $\textsf{Ch}_{{r_E}}$ where $p_{{r_E}}(z \mid y) = {\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_1({r_E}))$ (which is also equal to ${\textsc {Ratio}_{z \rightarrow y}}({r_E}_{w,0}, \textsc {Eve}_0({r_E}_{w,0}))$ by definition of $\textsc {Eve}_1$). We then define a new strategy $\textsc {Eve}_2$ which on input ${r_E}$ applies the corresponding channel $\textsf{Ch}_{{r_E}}$ on each symbol of ${r_E}$ to get ${\widehat{r}_B}{}$. Then $\textsc {Eve}_2$ acts identically to $\textsc {Eve}_1$ whenever each of the ratios ${\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_2({r_E}))$ hit their expected value. We prove that this happens with probability at least $\frac{1}{{{\,\mathrm{\textsf{poly}}\,}}(n)}$, so therefore, $\textsc {Eve}_2$ wins at least inverse polynomially as often as $\textsc {Eve}_1$.

Although $\textsc {Eve}_2$’s strategy is to apply a channel $\textsf{Ch}_{{r_E}}$ to each symbol of her input ${r_E}$, the choice of channel she applies is dependent on which ${r_E}$ she received. However, it turns out that there are only polynomially many possible channels that $\textsc {Eve}_2$ may construct. In particular, the set of channels that $\textsc {Eve}_2$ can construct is in bijective correspondence with the equivalence classes $\textsc {Eqwt}$. To see this, observe that for any permutation $\pi $, $\textsf{Ch}_{{r_E}} = \textsf{Ch}_{\pi ({r_E})}$ because $\textsc {Eve}_0(\pi ({r_E})) = \pi (\textsc {Eve}_0({r_E}))$. Thus, the total number of possible channels that $\textsc {Eve}_2$ may apply to ${r_E}$ is bounded by the number of equivalence classes of $\textsc {Eqwt}$, which is polynomial in size. We define $\textsf{Ch}_{w}$ to be equal to $\textsf{Ch}_{{r_E}}$ for any ${r_E}$ of weight w.

Thus, instead of having $\textsc {Eve}_2$ choose a channel based on ${r_E}$’s weight, we define a new strategy that randomly selects the channel before seeing ${r_E}$. In particular, we construct an $\textsc {Eve}_3$ which in addition to getting input ${r_E}$ also gets an independently chosen random input w that defines which channel $\textsf{Ch}_{w}$ that $\textsc {Eve}_3$ should apply to ${r_E}$.

Now, if the randomly chosen w equals $\textsf{wt}({r_E})$, then $\textsc {Eve}_3$ acts identically to $\textsc {Eve}_2$. But since there are only polynomially many weight vectors, an independently chosen random w equals $\textsf{wt}({r_E})$ with probability $\frac{1}{{{\,\mathrm{\textsf{poly}}\,}}(n)}$. Thus, the probability that $\textsc {Eve}_3$ succeeds given a random w is only polynomially worse than the probability that $\textsc {Eve}_2$ succeeds.

However, for any weight w, it is now the case that $\textsc {Eve}_3$ applies an input-independent channel to each symbol of ${r_E}$. Thus, we can now apply the non-degraded condition to prove that $\textsc {Eve}_3$’s probability of success is negligible for any input weight w. This then implies that any arbitrary strategy g has a negligible probability of winning.

3 Preliminaries

Throughout, we will use $\lambda $ to denote a security parameter.

Notation

We say that a function $f(\lambda )$ is negligible in $\lambda $ if $f(\lambda ) = \lambda ^{-\omega (1)}$, and we denote it by $f(\lambda ) = \textsf{negl}(\lambda )$.
We say that a function $g(\lambda )$ is polynomial in $\lambda $ if $g(\lambda ) = p(\lambda )$ for some fixed polynomial p, and we denote it by $g(\lambda ) = {{\,\mathrm{\textsf{poly}}\,}}(\lambda )$.
For $n \in \mathbb {N}$, we use [n] to denote $\{1, \ldots , n\}$.
If $R$ is a random variable, then $r\leftarrow R$ denotes sampling $r$ from $R$. If T is a set, then $i \leftarrow T$ denotes sampling i uniformly at random from T.
Let $S_n$ denote the symmetric group on n letters.

Definition 3.1

(Max norm of a matrix) Let A by any $n \times m$ matrix. We define the max norm to be the maximal magnitude of any entry and denote it with

$$\begin{aligned}\Vert A\Vert _{\max } = \max _{i, j} \left|A_{i, j}\right|.\end{aligned}$$

Lemma 3.2

(Chernoff bound) Let $X_1, \ldots , X_n$ be independent random variables taking values in $\{0, 1\}$, and let $X = \sum _{i=1}^n X_i$ and $\mathop {\mathrm {\mathbb {E}}}\limits [X] = \mu $. Then a two-sided Chernoff bound for $0 \le \delta \le 1$ is

$$\begin{aligned} \Pr \left[ |X - \mu | \ge \delta \mu \right] \le 2\cdot \exp \left( -\frac{\delta ^2 \mu }{3}\right) \end{aligned}$$

And a one sided Chernoff bound for $0 \le \delta \le 1$ is

$$\begin{aligned} \Pr [X \ge (1 + \delta )\mu ] \le \exp \left( \frac{-\delta ^2\mu }{3}\right) \end{aligned}$$

Remark 3.3

As a reminder, computationally bounded adversaries are described as non-uniform polynomial-time throughout the paper but can be equivalently given as a family of polynomial-size circuits.

3.1 Channel Definitions

Definition 3.4

We associate $\textsf{ChW}$ with its stochastic matrix

$$\begin{aligned}{P_W}= [p_W(y|x)]_{x \in \mathcal X, y \in \mathcal Y}\end{aligned}$$

For $x \in \mathcal X$, we use $\textsf{ChW}(x)$ to denote a random variable over $\mathcal Y$ such that for $y \in \mathcal Y$,

$$\begin{aligned}\Pr [\textsf{ChW}(x) = y] = {p_W}(y|x)\end{aligned}$$

For $n \in \mathbb {N}$ and $r = (r_1, \ldots , r_n) \in \mathcal X^n$, we define

$$\begin{aligned}\textsf{ChW}(r) = \textsf{ChW}(r_1)\ldots \textsf{ChW}(r_n)\end{aligned}$$

Whenever we discuss channels in the context of efficient algorithms, we assume all channels have finite description size with constant alphabet size and rational probabilities.

Notation

If $\textsf{ChE}$ is a channel, we may use $\Pr _{\textsf{ChE}}$ to denote the probability over the randomness of $\textsf{ChE}$. Similarly, if f is a randomized function, we may use $\Pr _{f}$ to denote the probability over the randomness of f.

Definition 3.5

(Binary symmetric channel ($\textsf{BSC}$)) A binary symmetric channel with crossover probability p $(\textsf{BSC}_p)$ is a DMC with binary input and binary output such that on input bit b, it outputs $1-b$ with probability p and b otherwise.

Definition 3.6

(Binary erasure channel ($\textsf{BEC}$)) A binary erasure channel with erasure probability $\epsilon $ $(\textsf{BEC}_\epsilon )$ is a DMC with binary input and output $\{0,1,\bot \}$ such that on input bit b, it outputs $\bot $ (i.e. erases the bit) with probability $\epsilon $ and b otherwise.

3.1.1 Less Noisy and Channel Degradation

Definition 3.7

(Less noisy, [10]) Channel $\textsf{ChE}$ is less noisy than channel $\textsf{ChB}$ if for every Markov chain $V \rightarrow X \rightarrow YZ$ such that $p_{Y|X}(y|x)$ corresponds to $\textsf{ChB}$ and $p_{Z|X}(z|x)$ correspond to $\textsf{ChE}$ then

$$\begin{aligned}I(V; Z) \ge I(V; Y).\end{aligned}$$

Definition 3.8

(Channel degradation, [9]) We say that channel $\textsf{ChB}$ is a degradation of channel $\textsf{ChE}$ if there exists a channel $\textsf{ChS}$ such that

$$\begin{aligned}\textsf{ChB}= \textsf{ChS}\circ \textsf{ChE}\end{aligned}$$

where $\circ $ denotes channel concatenation, that is $(\textsf{ChS}\circ \textsf{ChE})(x) = \textsf{ChS}(\textsf{ChE}(x))$.

Definition 3.9

(Channel degradation equivalent definition) Equivalently, we say that channel $\textsf{ChB}: \mathcal X\rightarrow \mathcal Y$ is a degradation of channel $\textsf{ChE}: \mathcal X\rightarrow \mathcal Z$ if there exists a stochastic matrix ${P_S}= [p_S(y \mid z)]_{z \in \mathcal Z, y \in \mathcal Y}$ such that

$$\begin{aligned}{P_B}= {P_E}\cdot {P_S}\end{aligned}$$

where ${P_B}= [{p_B}(y \mid x)]_{x \in \mathcal X, y \in \mathcal Y}$ is the stochastic matrix of $\textsf{ChB}$ and ${P_E}= [{p_E}(z \mid x)]_{x \in \mathcal X, z \in \mathcal Z}$ is the stochastic matrix of $\textsf{ChE}$.

Remark 3.10

(Notions of degradation) The notion of degradation defined above is sometimes referred to as stochastic degradation. There is also a notion of physical degradation. (See [29] for further discussion.) However, the difference between these notions is irrelevant in the current context.

Consider two channels $\textsf{ChB}$ and $\textsf{ChE}$. To better understand the relationship between less noisy and channel degradation, consider a concrete example where $\textsf{ChB}$ is a $\textsf{BSC}_p$ and $\textsf{ChE}$ is a $\textsf{BEC}_\epsilon $.

Theorem 3.11

(Imported from [27], Claim 4) Let $\textsf{ChB}$ be a $BSC_p$ for $p \in [0, \frac{1}{2})$ and let $\textsf{ChE}$ be a $BEC_\epsilon $. Then the following holds:

1.
If $0 \le \epsilon \le 2p$, then $\textsf{ChB}$ is a degradation of $\textsf{ChE}$.
2.
If $2p < \epsilon \le 4p(1-p)$, then $\textsf{ChE}$ is less noisy than $\textsf{ChB}$, but $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$.

We remark that $\textsf{ChE}$ may have higher capacity than $\textsf{ChB}$ but may still not be considered less noisy than $\textsf{ChB}$, e.g. $(\textsf{ChB}, \textsf{ChE}) = (\textsf{BSC}_{0.1}, \textsf{BEC}_{0.4})$. As Theorem 3.11 implies, there are many channels where $\textsf{ChE}$ is less noisy than $\textsf{ChB}$, but $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$, e.g. $(\textsf{ChB}, \textsf{ChE}) = (\textsf{BSC}_{0.1}, \textsf{BEC}_{0.3})$.

3.1.2 Limiting Channel Degradation

We also prove that if channel $\textsf{ChB}$ is not a degradation of channel $\textsf{ChE}$ then there is a constant separation between the probability distribution of $\textsf{ChB}$ and the distribution of any channel formed by concatenating $\textsf{ChE}$ with some other channel.

Definition 3.12

(Limiting channel degradation) We say that channel $\textsf{ChB}$ is a limiting degradation of channel $\textsf{ChE}$ if there exists a sequence of stochastic matrices $(P_{S, 1}, P_{S, 2}, P_{S, 3}, \ldots )$ such that

$$\begin{aligned}\lim _{i \rightarrow \infty } \Vert {P_B}- {P_E}\cdot P_{S, i}\Vert _{\max } = 0\end{aligned}$$

Lemma 3.13

(Channel degradation is equivalent to limiting channel degradation) Channel $\textsf{ChB}$ is a degradation of channel $\textsf{ChE}$ if and only if $\textsf{ChB}$ is a limiting degradation of $\textsf{ChE}$

Proof

One direction is immediate: if channel $\textsf{ChB}$ is a degradation of channel $\textsf{ChE}$, then $\textsf{ChB}$ is a limiting degradation of $\textsf{ChE}$.

For the other direction, proceed by contrapositive. We show that if channel $\textsf{ChB}$ is not a degradation of channel $\textsf{ChE}$, then $\textsf{ChB}$ is not a limiting degradation of $\textsf{ChE}$. Let $\textsf{ChB}: \mathcal X\rightarrow \mathcal Y$ and $\textsf{ChE}: \mathcal X\rightarrow \mathcal Z$ be channels such that $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$. Let ${P_B}$ and ${P_E}$ be the stochastic matrices of $\textsf{ChB}$ and $\textsf{ChE}$ respectively. Let T be the set of all stochastic matrices from $\mathcal Z$ to $\mathcal Y$. Observe that T is a compact set: The set of stochastic matrices T is defined by finitely many constraints, each of which for $M \in T$ define either a closed halfspace $(0 \le M_{ij} \le 1)$ or a hyperplane $(\sum _{i} M_{ij} = 1)$. The finite intersection of these constraints forms a closed convex polytope which is indeed compact. We consider the metric given by the max norm $\Vert \cdot \Vert _{\max }$. Let $\delta _{B, E}: T \rightarrow [0,1]$ be defined as $\delta _{B, E}({P_S}) = \Vert {P_B}- {P_E}\cdot {P_S}\Vert _{\max }$. Then observe that $\delta _{B, E}$ is a continuous function since it is a composition of two continuous functions. Now, consider any converging sequence in [0, 1]

$$\begin{aligned}(\delta _{B, E}(P_{S, 1}), \delta _{B, E}(P_{S, 2}), \delta _{B, E}(P_{S, 3}), \ldots )\end{aligned}$$

Then note that T equipped with the max norm metric is sequentially compact so the corresponding sequence $(P_{S, 1}, P_{S, 2}, P_{S, 3}, \ldots )$ has a converging subsequence $\left( P_{S, i_1}, P_{S, i_2},\right. $ $\left. P_{S, i_3}, \ldots \right) $ such that $\lim _{j \rightarrow \infty }P_{S, i_j} = {P_S}^*$ for some stochastic matrix ${P_S}^* \in T$. Since $\delta _{B, E}$ is continuous, $\lim _{j \rightarrow \infty } \delta _{B, E}(P_{S, i_j}) = \delta _{B, E}({P_S}^*)$. Since channel $\textsf{ChB}$ is not a degradation of channel $\textsf{ChE}$ and ${P_S}^*$ is a stochastic matrix, then $\Vert {P_B}- {P_E}\cdot {P_S}^*\Vert _{\max } = \delta _{B, E}({P_S}^*) > 0$. But all converging subsequences of a converging sequence converge to the same limit; therefore the converging sequence

$$\begin{aligned}(\delta _{B, E}(P_{S, 1}), \delta _{B, E}(P_{S, 2}), \delta _{B, E}(P_{S, 3}), \ldots )\end{aligned}$$

converges to $\delta _{B, E}({P_S}^*) > 0$. Therefore no converging sequence can have limit 0, so $\textsf{ChB}$ is not a limiting degradation of $\textsf{ChE}$. $\square $

Lemma 3.14

If channel $\textsf{ChB}$ is not a degradation of channel $\textsf{ChE}$, then there exists a constant $d >0$ such that for all stochastic matrices ${P_S}= [p_S(y \mid z)]_{z \in \mathcal Z, y \in \mathcal Y}$,

$$\begin{aligned}\Vert {P_B}- {P_E}\cdot {P_S}\Vert _{\max } \ge d\end{aligned}$$

Proof

The non-existence of such d would imply that channel $\textsf{ChB}$ is a limiting degradation of channel $\textsf{ChE}$. But by Lemma 3.13, this would imply that $\textsf{ChB}$ is a degradation of $\textsf{ChE}$ which is a contradiction. $\square $

4 Wiretap Channels

4.1 Wiretap Channel Definitions

A wiretap channel [10, 30] is defined by two discrete memoryless channels $(\textsf{ChB}, \textsf{ChE})$ with the same input domain $\mathcal X$ where $\textsf{ChB}: \mathcal X\rightarrow \mathcal Y$ is the main channel and $\textsf{ChE}: \mathcal X\rightarrow \mathcal Z$ is the eavesdropper channel. We characterize $\textsf{ChB}$ by its stochastic matrix ${P_B}= [{p_B}(y \mid x)]_{x \in \mathcal X, y \in \mathcal Y}$ and $\textsf{ChE}$ by its stochastic matrix ${P_E}= [{p_E}(z \mid x)]_{x \in \mathcal X, z \in \mathcal Z}$. Throughout, we will use $\mathcal X, \mathcal Y, \mathcal Z$ to denote respectively the input alphabet of $\textsf{ChB}$ and $\textsf{ChE}$, the output alphabet of $\textsf{ChB}$, and the output alphabet of $\textsf{ChE}$. We use $\mathcal M$ to denote the message space.

Definition 4.1

(Wiretap coding scheme: syntax) A wiretap coding scheme $\Pi $ for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ and message space $\mathcal M$ is a pair of algorithms $({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$. ${{\,\textrm{Enc}\,}}$ is a randomized encoding algorithm that takes as input a security parameter $1^\lambda $, a message $m \in \mathcal M$, and outputs a finite length encoding in $\mathcal X^n$ where $n = n(\lambda )$. ${{\,\textrm{Dec}\,}}$ is a deterministic decoding algorithm that takes as input a security parameter $1^\lambda $ and a string from $\mathcal Y^n$ and outputs a message in $\mathcal M$.

A wiretap coding scheme satisfies correctness if Bob can decode the output of $\textsf{ChB}$ on an encoding of a message. Security holds if Eve when given the output of $\textsf{ChE}$ on the encoding of the message cannot learn the message. Similarly to [5],^{Footnote 4} we use the standard notion of semantic security [16]. For simplicity, we only consider the case when $\mathcal M= \{0,1\}$. However, we can easily generalize our definition to consider larger families of message spaces (see Definition 4.19).

Definition 4.2

(Statistically secure wiretap coding scheme) A wiretap coding scheme $\Pi = ({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ is a statistically secure wiretap coding scheme for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ and message space $\mathcal M= \{0,1\}$ if there exist negligible functions $\epsilon (\lambda ),\mu (\lambda )$ such that

Correctness: For all messages $m \in \{0,1\}$,
$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}(1^\lambda , \textsf{ChB}({{\,\textrm{Enc}\,}}(1^\lambda , m))) = m] \ge 1 - \epsilon (\lambda )\end{aligned}$$
Security: For all adversaries $\mathcal A$,
$$\begin{aligned}\Pr [\mathcal A(1^\lambda , \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , b))) = b] \le \frac{1}{2} + \mu (\lambda )\end{aligned}$$
where b is uniformly distributed over $\{0,1\}$.

We may similarly refer to a finite scheme $\Pi _0$ (with a fixed $\lambda $) as being $\epsilon _0$-correct and $\mu _0$-secure.

Definition 4.3

(Computationally secure wiretap coding scheme) $\Pi = ({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ is a computationally secure wiretap coding scheme if ${{\,\textrm{Enc}\,}}$ and ${{\,\textrm{Dec}\,}}$ are PPT algorithms, and if it satisfies the above definition except that we only require security against non-uniform polynomial-time adversaries $\mathcal A$.

Notation

We say that a wiretap channel $(\textsf{ChB}, \textsf{ChE})$ admits a statistically (resp. computationally) secure wiretap coding scheme if there exists a statistically (resp. computationally) secure wiretap coding scheme for $(\textsf{ChB}, \textsf{ChE})$.

We can also consider a finite version of Definition 4.2 where both error parameters are fixed to constants.

Definition 4.4

A wiretap coding scheme $\Pi = ({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ is a $\delta $-statistically secure wiretap coding scheme for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ and message space $\mathcal M= \{0,1\}$ if

Rate: For all $m \in \{0,1\}, |{{\,\textrm{Enc}\,}}(m)| = c$ for some constant c.
Correctness: For all $m \in \{0,1\}$,
$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}(\textsf{ChB}({{\,\textrm{Enc}\,}}(m))) = m] \ge \delta \end{aligned}$$
Security: For all adversaries $\mathcal A$,
$$\begin{aligned}\Pr [\mathcal A(\textsf{ChE}({{\,\textrm{Enc}\,}}(b))) = b] \le \frac{1}{2} + (1-\delta )\end{aligned}$$
where b is uniformly distributed over $\{0,1\}$.

4.2 Ideal Obfuscation Model

Similarly to the recent use of obfuscation in [1], it is convenient to describe and analyze our constructions in an ideal obfuscation model in which the sender can give a receiver (either Bob or Eve) bounded query access to an oracle. In this model, the encoding function outputs both an encoding of m and a description ${\hat{f}}$ of a circuit computing a deterministic function f. (We will typically abuse notation by using f to denote both the function and its description.) The receiver Bob and the adversary Eve are both given oracle access to f. In addition, though we require Eve to only make polynomially many queries to the oracle f, we allow Eve to be otherwise unbounded by default (see Remark 4.7 below for a relaxed variant of this definition). We will later consider the question of instantiating the ideal obfuscation primitive in the plain model under concrete cryptographic assumptions (see Sect. 7).

Definition 4.5

(Wiretap coding scheme in the ideal obfuscation model: syntax) A wiretap coding scheme $\Pi $ for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ and message space $\mathcal M$ in the ideal obfuscation model is a pair of algorithms $({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}}^{(\cdot )})$. ${{\,\textrm{Enc}\,}}$ is a randomized encoding algorithm that takes as input a security parameter $1^\lambda $ and a message $m \in \mathcal M$, and outputs a finite length encoding in $\mathcal X^n$ where $n = n(\lambda )$ and a description ${\hat{f}}$ of a circuit computing some deterministic function f. ${{\,\textrm{Dec}\,}}^{(\cdot )}$ is a deterministic decoding algorithm with polynomially bounded access to an oracle. It takes as input a security parameter $1^\lambda $, a string from $\mathcal Y^n$, and outputs a message in $\mathcal M$.

Definition 4.6

(Bounded query secure wiretap coding scheme in the ideal obfuscation model) A wiretap coding scheme $\Pi = ({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}}^{(\cdot )})$ is a bounded query secure wiretap coding scheme in the ideal obfuscation model for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ and message space $\mathcal M= \{0,1\}$ if ${{\,\textrm{Enc}\,}}$ and ${{\,\textrm{Dec}\,}}^{(\cdot )}$ are PPT algorithms which satisfy

Correctness: For all messages $m \in \{0,1\}$,
$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}^{f}(1^\lambda , \textsf{ChB}(c)) = m \mid (f, c) \leftarrow {{\,\textrm{Enc}\,}}(1^\lambda , m)] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$
Security: For every polynomial query bound $q(\lambda )$ and (computationally unbounded) adversary $\mathcal A^{(\cdot )}$ that makes at most $q(\lambda )$ queries to its oracle f,
$$\begin{aligned}\Pr [\mathcal A^{f_b}(1^\lambda , \textsf{ChE}(c_b)) = b \mid (f_b, c_b) \leftarrow {{\,\textrm{Enc}\,}}(1^\lambda , b)] \le \frac{1}{2} + \textsf{negl}(\lambda )\end{aligned}$$
where b is uniformly distributed over $\{0,1\}$.

Remark 4.7

(Computationally bounded adversaries) Definition 4.6 only bounds the number of queries made by ${{\mathcal {A}}}$ but does not otherwise bound its computational complexity. This makes our main feasibility results stronger. One may also consider a relaxed variant of the definition in which ${{\mathcal {A}}}$ is computationally bounded, as in Definition 4.3. This relaxation can be used for bootstrapping from a low-rate wiretap coding scheme in the ideal obfuscation model to a high-rate computationally secure scheme (with a “small” oracle f) via a hybrid encryption technique (see Remark 4.18).

4.3 Wiretap Feasibility in the Information Theoretic Setting

We will prove the following characterization of the wiretap feasibility region in the information theoretic setting:

Theorem 4.8

There exists a statistically secure wiretap coding scheme for $(\textsf{ChB}, \textsf{ChE})$ if and only if $\textsf{ChE}$ is not less noisy than $\textsf{ChB}$.

In fact, we will prove a stronger claim (Theorem 4.17) relating the definitions of wiretap security from prior work to our definitions. As information theorists have historically focused more on obtaining the maximal achievable rate R for the encoding function ${{\,\textrm{Enc}\,}}$ than on achieving strong notions of cryptographic security, their definitions of security are framed differently from the typical cryptographic definitions. This disconnect was addressed in [5], who bridged the gap between the information theoretic and cryptographic communities and proposed new security definitions for the wiretap channel.

We now define the following in terms of the correctness and security requirements of [10].

Definition 4.9

(CK rate-R wiretap coding family [10]) A family of wiretap encoder-decoder pairs $\{({{\,\textrm{Enc}\,}}_n, {{\,\textrm{Dec}\,}}_n)\}_{n \in \mathbb {N}}$ is a rate-R information theoretic wiretap coding family for a wiretap channel $(\textsf{ChB}, \textsf{ChE})$ and message family $\{\mathcal M_n\}_{n \in \mathbb {N}}$ if each ${{\,\textrm{Enc}\,}}_n$ outputs an encoding of length n such that

Message Rate R:
$$\begin{aligned}\lim _{n \rightarrow \infty } \frac{1}{n} \log \left|\mathcal M_n\right| = R\end{aligned}$$
Correctness: For all $m \in \mathcal M_n$,
$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}_n(\textsf{ChB}({{\,\textrm{Enc}\,}}_n(m))) = m] \ge 1 - \epsilon _n\end{aligned}$$
where
$$\begin{aligned}\lim _{n \rightarrow \infty }\epsilon _n = 0\end{aligned}$$
Security:
$$\begin{aligned}\lim _{n \rightarrow \infty } \frac{1}{n} I(M_n; \textsf{ChE}({{\,\textrm{Enc}\,}}_n(M_n))) = 0\end{aligned}$$
where $M_n$ is uniform over $\mathcal M_n$.

We denote the set of all achievable rates as $\mathcal R$.

We define secrecy capacity as the maximum rate of such an encoding.

Definition 4.10

(Secrecy capacity) The secrecy capacity $C_s$ of a wiretap channel $(\textsf{ChB}, \textsf{ChE})$, is the maximum of the rates R of any CK rate-R wiretap coding family for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ for any message family $\{\mathcal M_n\}_{n \in \mathbb {N}}$.

Furthermore, [10] completely characterized the region in which positive rate CK wiretap coding schemes are possible.

Theorem 4.11

[10] $C_s > 0$ if and only if $\textsf{ChE}$ is not less noisy than $\textsf{ChB}$.

Note that if $C_s = 0$, then no positive rate encoding can satisfy both correctness and security.

Additionally, [25] show that the security requirement can be strengthened to the following:

Definition 4.12

(CK rate-R wiretap coding family with strong secrecy [10, 25]) This is the same as the definition of a CK Rate-R wiretap coding family except that we replace the security requirement with the following:

Strong Security:
$$\begin{aligned}\lim _{n \rightarrow \infty } I(M_n; \textsf{ChE}({{\,\textrm{Enc}\,}}_n(M_n))) = 0\end{aligned}$$
where $M_n$ is uniform over $\mathcal M_n$.

We can then define the strong secrecy capacity.

Definition 4.13

(Strong secrecy capacity (Adapted from [25])) The strong secrecy capacity $\overline{C_s}$ of a wiretap channel $(\textsf{ChB}, \textsf{ChE})$, is the maximum of the rates R of any CK rate-R wiretap coding family with strong secrecy for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ for any message family $\{\mathcal M_n\}_{n \in \mathbb {N}}$.

Theorem 4.14

(Equivalence of strong and weak secrecy capacity (imported from [25])) For all wiretap channels $(\textsf{ChB}, \textsf{ChE})$, we have $C_s = \overline{C_s}$.

Remark 4.15

The definition of $C_s$ above is written differently from the definition in [10]. However, it is equivalent and follows easily from the definitions used in [10]. The definitions of $C_s$ and $\overline{C_s}$ are similar, but slightly different from the definitions used in [25]. However, Theorem 4.14 still holds with respect to our definitions. We provide a short explanation of these two facts in “Appendix A”.

As observed by [5], both the correctness and security definitions of [10] are weaker than our definitions and are insufficient for cryptographic purposes.^{Footnote 5} Thus, [5] defined several new notions of security including the semantic security definition we use. They also prove that this semantic security definition implies an information theoretic security notion.

Theorem 4.16

[5] The semantic security requirement of Definition 4.2 of a statistically secure wiretap coding scheme implies that $I(M; \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , M))) = \textsf{negl}(\lambda )$ where M is uniform over $\mathcal M= \{0,1\}$.

We now prove the following theorem which implies Theorem 4.8.

Theorem 4.17

The following are equivalent:

1.
$\textsf{ChE}$ is not less noisy than $\textsf{ChB}$. (Definition 3.7)
2.
$C_s > 0$ (Definition 4.10) i.e. There exists a CK Rate-R wiretap coding family for $(\textsf{ChB}, \textsf{ChE})$ with positive rate R. (Definition 4.9)
3.
$\overline{C_s} > 0$ (Definition 4.13) i.e. There exists a CK Rate-R wiretap coding family with strong secrecy for $(\textsf{ChB}, \textsf{ChE})$ with positive rate R. (Definition 4.12)
4.
There exists a 0.99-statistically secure wiretap coding scheme for $(\textsf{ChB}, \textsf{ChE})$. (Definition 4.4)
5.
There exists a statistically secure wiretap coding scheme for $(\textsf{ChB}, \textsf{ChE})$. (Definition 4.2)
6.
There exists a statistically secure wiretap coding scheme for general message spaces for $(\textsf{ChB}, \textsf{ChE})$ with a positive constant rate. (Definition 4.19. See Sect. 4.4 below for the definition.)

Proof

The theorem follows from the relations below.

$1 \iff 2$. This follows from Theorem 4.11.
$2 \iff 3$. This follows from Theorem 4.14.
$6 \Rightarrow 5$. A statistically secure wiretap coding scheme for general message spaces can be easily transformed into one for a binary message spaces by ignoring all but the first bit of the message from the general message space.
$5 \Rightarrow 2$. This proof can be found in “Appendix B”.
$3 \Rightarrow 4$. This proof can be found in “Appendix B”.
$4 \Rightarrow 6$. This proof can be found in “Appendix B”.^{Footnote 6}$\square $

4.4 Rate and General Message Spaces

Previously, we only considered the case when $\mathcal M= \{0,1\}$. This means that any secure wiretap coding scheme must be rate 0.

Remark 4.18

When the adversary is computationally bounded, and potentially has oracle access, we note that any computationally secure wiretap coding scheme can be made optimal rate, meaning rate asymptotically approaching Bob’s channel’s capacity. This is achieved by using the computationally secure wiretap coding scheme to share a secret key between Alice and Bob and then subsequently using a PRG to build a stream cipher between Alice and Bob. The ciphertext must then be sent across Bob’s channel; therefore the maximal rate is given by the capacity.

Unfortunately, in the information theoretic setting, we cannot improve rate in the same manner. Thus, we define a notion of secure wiretap coding schemes for general message spaces.

Definition 4.19

(Statistically secure wiretap coding schemes for general message spaces) A wiretap coding scheme $\Pi = ({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ is a secure wiretap coding scheme for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ and a polytime computable message length $\ell (\lambda )$ if there exist negligible functions $\epsilon (\lambda ),\mu (\lambda )$ such that

Correctness: For all messages $m \in \{0,1\}^{\ell (\lambda )}$,
$$\begin{aligned} \Pr [{{\,\textrm{Dec}\,}}(1^\lambda , \textsf{ChB}({{\,\textrm{Enc}\,}}(1^\lambda , m))) = m] \ge 1 - \epsilon (\lambda )\end{aligned}$$
Security: For all adversaries $\mathcal A$ and all messages $m_0 \ne m_1 \in \{0,1\}^{\ell (n)}$,
$$\begin{aligned}\Pr [\mathcal A(1^\lambda , m_0, m_1, \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , m_b))) = b] \le \frac{1}{2} + \mu (\lambda )\end{aligned}$$
where b is uniformly distributed over $\{0,1\}$.

Similarly, we can define this in the computational setting and in the ideal obfuscation model.

Remark 4.20

Our main result of Theorem 5.3 still holds with respect to this general definition with only notational changes in the proofs.

5 Constructing Bounded Query Secure Wiretap Coding Schemes in the Ideal Obfuscation Model

5.1 Construction

We consider the setting of a $(\textsf{ChB}, \textsf{ChE})$ wiretap channel where the main channel $\textsf{ChB}: \mathcal X\rightarrow \mathcal Y$ is not a degradation of the eavesdropping channel $\textsf{ChE}: \mathcal X\rightarrow \mathcal Z$. For the entirety of this section, we will characterize $\textsf{ChB}$ by its stochastic matrix ${P_B}= [{p_B}(y \mid x)]_{x \in \mathcal X, y \in \mathcal Y}$ and channel $\textsf{ChE}$ by its stochastic matrix ${P_E}= [{p_E}(z \mid x)]_{x \in \mathcal X, z \in \mathcal Z}$. We let $\mathcal M= \{0,1\}$.

Let $\lambda $ be a security parameter, and let $n = \lambda $. Our encoding of a message $m \in \mathcal M$ will specify a codeword and an oracle. The codeword will be a random string $r\in \mathcal X^n$ which will be sent across the two channels. We define

$R$: uniform random variable over $\mathcal X^n$
${R_B}:= \textsf{ChB}(R)$
${R_E}:= \textsf{ChE}(R)$

The oracle, which is transmitted perfectly to both parties, will output the message m if it receives an input which is “typical” for ${R_B}$ conditioned on $R= r$ (notationally ${R_B}_{|R= r}$) and will output $\bot $ otherwise. We will define typicality in terms of the expected number of x’s in $r$ that should turn into y’s in ${R_B}_{|R= r}$ for each pair $(x, y) \in \mathcal X\times \mathcal Y$ as specified by Bob’s channel probability matrix ${P_B}$. The receiver Bob should be able to recover m simply by sending his received value of ${R_B}$ to the oracle. Thus, the decoder will simply output the value of the oracle on its input. Security holds if the eavesdropper Eve cannot create a “typical" channel value for ${R_B}_{|R= r}$ given only ${R_E}_{|R= r}$. To specify this more formally, we first define the following:

Definition 5.1

Let $\mathcal X$ be any discrete finite set and let $n \in \mathbb {N}$. For any $r\in \mathcal X^n$ and $x \in \mathcal X$, we define the number of x’s in $r$ to be

$$\begin{aligned}N_{x}(r) = |\{i \in [n]: r_i = x\}|\end{aligned}$$

Definition 5.2

$$\begin{aligned}{\textsc {Ratio}_{x \rightarrow y}}(r,s) = \frac{\left|\{i \in [n]: r_i = x, s_{i} = y\}\right|}{N_{x}(r)}.\end{aligned}$$

If $N_{x}(r) = 0$, then we define ${\textsc {Ratio}_{x \rightarrow y}}(r,s) = 0$.

We now describe our wiretap encoder-decoder pair $({{\,\textrm{Enc}\,}}_\textsf{ChB}, {{\,\textrm{Dec}\,}}_\textsf{ChB})$ for main channel $\textsf{ChB}$.

We then prove that our coding scheme gives us both correctness and security.

Theorem 5.3

If $(\textsf{ChB}, \textsf{ChE})$ is a wiretap channel where $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$, then $({{\,\textrm{Enc}\,}}_\textsf{ChB}, {{\,\textrm{Dec}\,}}_\textsf{ChB}^{(\cdot )})$ achieves

Correctness: For all messages $m \in \{0,1\}$,
$$\begin{aligned}{} & {} \Pr [{{\,\textrm{Dec}\,}}_\textsf{ChB}^{f_{m, r,\textsf{ChB},n}}(1^\lambda , \textsf{ChB}(r)) = m \mid (f_{m,r,\textsf{ChB},n}, r) \leftarrow {{\,\textrm{Enc}\,}}_\textsf{ChB}(1^\lambda , m)] \\ {}{} & {} \quad \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$
Security: For every polynomial query bound $q(\lambda )$ and (computationally unbounded) adversary $\mathcal A^{(\cdot )}$ that makes at most $q(\lambda )$ queries to its oracle,
$$\begin{aligned}\Pr [\mathcal A^{f_{b, r, \textsf{ChB}, n}}(1^\lambda , \textsf{ChE}(r)) {=} b \mid (f_{b, r, \textsf{ChB}, n}, r) \leftarrow {{\,\textrm{Enc}\,}}_\textsf{ChB}(1^\lambda , b)] {\le } \frac{1}{2} + \textsf{negl}(\lambda )\end{aligned}$$
where b is uniformly distributed over $\{0,1\}$.

Proof

Correctness follows by Theorem 5.8, and security follows by Theorem 5.34 which are proven below. $\square $

Since ${{\,\textrm{Enc}\,}}_\textsf{ChB}$ and ${{\,\textrm{Dec}\,}}_\textsf{ChB}^{(\cdot )}$ are PPT, we get the following corollary.

Corollary 5.4

Remark 5.5

Theorem 5.3 and Corollary 5.4 hold even if we modify $f_{m, r, \textsf{ChB}, n}$ to have binary output domain by outputting 0 in place of $\bot $. Correctness still holds since the probability that the decoder using the original function outputs $\bot $ is negligible, so changing $\bot $ to 0 results in at most a negligible change in correctness. For security, observe that by outputting 0 instead of $\bot $, Eve gets strictly less information as she cannot tell whether an observed 0 from the oracle is an indicator of failure to receive the message bit or is the message bit itself.

5.2 Correctness

Correctness follows by a simple Chernoff bound over each set of symbols $x \in \mathcal X$ in $R$. However, for the Chernoff bound to apply, we need $R$ to have a sufficient number of each symbol in $\mathcal X$. By an additional Chernoff bound, this occurs with overwhelming probability over $R$.

Definition 5.6

Let $\textsc {Good}= \{r\in \mathcal X^n \mid \forall x \in \mathcal X, N_{x}(r) \ge \frac{n}{2|\mathcal X|}\} \subset \mathcal X^n$.

Observe that for all $r\in \textsc {Good}$ and $x \in \mathcal X$, then $N_{x}(r) = \Theta (n)$.

Lemma 5.7

$\Pr [R\in \textsc {Good}] \ge 1 - \textsf{negl}(\lambda )$

Proof

For any $x \in \mathcal X$ and $i \in [n]$, define

$$\begin{aligned} V_{x,i} = {\left\{ \begin{array}{ll} 1&{}\quad \text {if } R_i = x\\ 0&{} \text {else} \end{array}\right. } \end{aligned}$$

Since $R$ is uniformly random over $\mathcal X^n$, then $\mathop {\mathrm {\mathbb {E}}}\limits [V_{x,i}] = \frac{1}{|\mathcal X|}$. Let $N_{x}(R) = \sum _{i \in [n]}V_{x,i}$. Then, $\mathop {\mathrm {\mathbb {E}}}\limits [N_{x}(R)] = \frac{n}{|\mathcal X|}$. Therefore, by a Chernoff bound, for any $x \in \mathcal X$, we have

$$\begin{aligned} \Pr \left[ {N_{x}(R) \le \frac{1}{2} \cdot \frac{n}{|\mathcal X|}}\right] < e^{-\frac{n}{8|\mathcal X|}} = \textsf{negl}(n) \end{aligned}$$

Thus,

$$\begin{aligned} \Pr \left[ \forall x \in \mathcal X, N_{x}(R) \ge \frac{n}{2|X|}\right]&= 1 - \Pr \left[ \exists x \in \mathcal X, N_{x}(R)< \frac{n}{2|X|}\right] \\&\ge 1 - \sum _{x \in \mathcal X}\Pr \left[ N_{x}(R) < \frac{n}{2|X|}\right] \\&= 1 - |\mathcal X|\cdot \textsf{negl}(n) = 1 - \textsf{negl}(\lambda ) \end{aligned}$$

$\square $

Claim 5.14

For all $r\in \mathcal X^n$, ${r_E}\in \mathcal Z^n$, $\pi \in S_n$,

$$\begin{aligned}\Pr [R= r\mid {R_E}= {r_E}] = \Pr [R = \pi (r) \mid {R_E}= \pi ({r_E})]\end{aligned}$$

Proof

Let $r= (r_1, \ldots , r_n)$ and ${r_E}= ({r_E}_{1}, \ldots , {r_E}_{n})$. Since each bit of $r$ is chosen identically and independently and $\textsf{ChE}$ acts independently on each input symbol, then

$$\begin{aligned} \Pr [R= r\mid {R_E}= {r_E}]&= \frac{\Pr [{R_E}= {r_E}\mid R= r]\cdot \Pr [R= r]}{\Pr [{R_E}= {r_E}]}\\&= \prod _{i \in [n]}\frac{\Pr [{R_E}_{i} = {r_E}_{i} \mid R_i = r_i]\cdot \Pr [R_i = r_i]}{\Pr [{R_E}_{i} = {r_E}_{i}]}\\&= \prod _{j \in \pi ([n])}\frac{\Pr [{R_E}_{j} = {r_E}_{j} \mid R_j = r_j]\cdot \Pr [R_j = r_j]}{\Pr [{R_E}_{j} = {r_E}_{j}]}\\&= \frac{\Pr [{R_E}= \pi ({r_E}) \mid R= \pi (r)]\cdot \Pr [R= \pi (r)]}{\Pr [{R_E}= \pi ({r_E})]}\\&= \Pr [R= \pi (r) \mid {R_E}= \pi ({r_E})] \end{aligned}$$

$\square $

Now, we apply a Chernoff bound and a union bound to get correctness.

Theorem 5.8

For all messages $m \in \{0,1\}$,

$$\begin{aligned}\Pr \left[ {{\,\textrm{Dec}\,}}_\textsf{ChB}^{f_{m, r, \textsf{ChB}, n}}(1^\lambda , \textsf{ChB}(r)) = m \mid (f_{m, r, \textsf{ChB}, n}, r) \leftarrow {{\,\textrm{Enc}\,}}_\textsf{ChB}(1^\lambda , m)\right] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$

Proof

By definition of ${{\,\textrm{Enc}\,}}_\textsf{ChB}$ and ${{\,\textrm{Dec}\,}}_\textsf{ChB}^{(\cdot )}$,

$$\begin{aligned}&\Pr \left[ {{\,\textrm{Dec}\,}}_\textsf{ChB}^{f_{m, r, \textsf{ChB}, n}}(1^\lambda , \textsf{ChB}(r)) = m \mid (f_{m, r, \textsf{ChB}, n}, r) \leftarrow {{\,\textrm{Enc}\,}}_\textsf{ChB}(1^\lambda , m)\right] \\&= \Pr [f_{m, r, \textsf{ChB}, n}(\textsf{ChB}(r)) = m \mid r\leftarrow R\ ]\\&= \Pr \left[ \forall x \in \mathcal X, y \in \mathcal Y,\; {\textsc {Ratio}_{x \rightarrow y}}(R, \textsf{ChB}(R)) \le {p_B}(y|x) + n^{-\frac{1}{3}}\right] \\&= 1 - \Pr \left[ \exists x \in \mathcal X, y \in \mathcal Y,\; {\textsc {Ratio}_{x \rightarrow y}}(R, \textsf{ChB}(R)) > {p_B}(y|x) + n^{-\frac{1}{3}}\right] \end{aligned}$$

Thus, since $\Pr [R\notin \textsc {Good}] \le \textsf{negl}(\lambda )$ by Lemma 5.7, it suffices to prove that for all $r\in \textsc {Good}$,

$$\begin{aligned}\Pr \left[ \exists x \in \mathcal X, y \in \mathcal Y,\; {\textsc {Ratio}_{x \rightarrow y}}(r, \textsf{ChB}(r)) > {p_B}(y|x) + n^{-\frac{1}{3}}\right] \le \textsf{negl}(\lambda )\end{aligned}$$

Fix any $r \in \textsc {Good}$, $x \in \mathcal X$, and $y \in \mathcal Y$. For all $i \in [n]$, define

$$\begin{aligned} V_{i} = {\left\{ \begin{array}{ll} 1&{}\quad \text {if } r_i = x \text { and } (\textsf{ChB}(r))_i = y\\ 0&{}\quad \text {else} \end{array}\right. } \end{aligned}$$

Let $S_{x} = \{i \in [n] \mid r_i = x\}$. Then by a Chernoff bound,

$$\begin{aligned}&\Pr \left[ {\textsc {Ratio}_{x \rightarrow y}}(r, \textsf{ChB}(r)) - {p_B}(y|x) \ge n^{-\frac{1}{3}}\right] \\&=\Pr \left[ \sum _{i \in S_{x}} V_{i} - N_{x}(r)\cdot {p_B}(y|x) \ge N_{x}(r) \cdot n^{-\frac{1}{3}}\right] \\&\le \exp \left( \frac{- N_{x}(r)\cdot n^{-2/3}}{3 \cdot {p_B}(y|x)}\right) . \end{aligned}$$

Since ${p_B}(y| x) \le 1$ and $r\in \textsc {Good}$ implies $N_{x}(r) = \Theta (n)$,

$$\begin{aligned} \Pr \left[ \sum _{i \in S_{x}} V_{i} - N_{x}(r)\cdot {p_B}(y|x) \ge N_{x}(r) \cdot n^{-\frac{1}{3}}\right]&\le e^{-\Omega (n^{1/3})} = \textsf{negl}(n). \end{aligned}$$

Thus, by a union bound, for all $r\in \textsc {Good}$

$$\begin{aligned}&\Pr \left[ \exists x \in \mathcal X, y \in \mathcal Y,\; {\textsc {Ratio}_{x \rightarrow y}}(r, \textsf{ChB}(r)) > {p_B}(y|x) + n^{-\frac{1}{3}}\right] \\ {}&\quad \le |\mathcal X| \cdot |\mathcal Y|\cdot \textsf{negl}(n) = \textsf{negl}(\lambda ) \end{aligned}$$

and the proof follows. $\square $

5.3 Security

5.3.1 Overview

In our security game, the adversary receives ${R_E}= \textsf{ChE}(R)$ and oracle access to $f_{b, R, \textsf{ChB}, n}$ for a random $b \in \{0,1\}$ and tries to guess b. Intuitively, since $R$ is independent of b, if for all $b \in \{0,1\}$, an adversary is unable to generate an input ${\widehat{r}_B}{}$ such that $f_{b, r, \textsf{ChB}, n}({\widehat{r}_B}{}) \ne \bot $, then the adversary should be unable to learn anything about b. Thus, we will first attempt to show this.

To simplify our proof, we define the following function $h_{r, \textsf{ChB}, n}$ which on input ${r_B}$ outputs 1 if all of the ratios ${\textsc {Ratio}_{x \rightarrow y}}(r, {r_B})$ are sufficiently close to the channel probabilities ${p_B}(y \mid x)$ and 0 otherwise.

Definition 5.9

Let $r\in \mathcal X^n$ and ${r_B}\in \mathcal Y^n$. Define $h_{r, \textsf{ChB}, n}: \mathcal Y^n \rightarrow \{0,1\}$ as

We will first show that for any arbitrary strategy g that an adversary applies to ${R_E}$,

$$\begin{aligned}\Pr [h_{R, \textsf{ChB}, n}(g({R_E})) = 1] \le \textsf{negl}(\lambda ).\end{aligned}$$

We will then prove that this implies that for any arbitrary strategy g that an adversary applies to ${R_E}$ and for any message $m \in \{0,1\}$,

$$\begin{aligned}\Pr [f_{m, R, \textsf{ChB}, n}(g({R_E})) \ne \bot ] \le \textsf{negl}(\lambda ).\end{aligned}$$

Then we will prove that this implies security.

To prove the first step, we will need to rely on the fact that $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$. This means that for all channels $\textsf{ChS}$, then

$$\begin{aligned}\textsf{ChB}\ne \textsf{ChS}\circ \textsf{ChE}\end{aligned}$$

Thus, if Eve’s strategy g was to apply a DMC channel $\textsf{ChS}$ to each symbol of ${R_E}$, then the distribution of $g({R_E}) = \textsf{ChS}(\textsf{ChE}(R))$ should differ from the distribution of $\textsf{ChB}(R)$, and therefore result in $h_{R, \textsf{ChB}, n}(g({R_E})) = 0$ with high probability.

However, Eve may instead choose any arbitrary strategy g. Thus, to prove our result, we will show through a series of hybrids $g, \textsc {Eve}_0, \textsc {Eve}_1, \textsc {Eve}_2, \textsc {Eve}_3$ that strategy g is only polynomially better that strategy $\textsc {Eve}_3$, where $\textsc {Eve}_3$’s strategy is to apply a DMC independently to each symbol of ${R_E}$. Then, we can use the not-degraded condition to show that $\textsc {Eve}_3$’s probability of success is negligible. We refer further intuition to the Technical Overview.

We will first assume that Eve’s arbitrary strategy g is optimal, defined below:

Definition 5.10

We say that a strategy $g^*: \mathcal Z^n \rightarrow \mathcal Y^n$ for guessing ${\widehat{r}_B}{}$ is optimal if

$$\begin{aligned}g^* = \mathop {\mathrm {arg\,max}}\limits _{g}\left( \Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(g({R_E})) = 1]\right) .\end{aligned}$$

Remark 5.11

By definition, for any optimal strategy $g^*$,

$$\begin{aligned}g^*({r_E}) = \max _{{\widehat{r}_B}{}} \left( \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}({\widehat{r}_B}{}) = 1 \mid {R_E}= {r_E}]\right) \end{aligned}$$

Observe that there may be multiple possible optimal strategies $g^*$ which achieve the same maximal probability of success. Furthermore, since $g^*$ may arbitrarily break ties for the maximum, then there always exists an optimal strategy which is deterministic.

We also define a notion of weight.

Definition 5.12

For ${r_E}\in \mathcal Z^n$, we define the weight of ${r_E}$ as

$$\begin{aligned}\textsf{wt}({r_E}) = (N_{z_1}({r_E}), \ldots , N_{z_{|\mathcal Z|}}({r_E}))\end{aligned}$$

where $\mathcal Z= \{z_1, \ldots , z_{|\mathcal Z|}\}$. We define an equivalence relation $\textsc {Eqwt}$ on $\mathcal Z^n \times \mathcal Z^n$ by

We define the lexicographically first element in the equivalence class to be the canonical representative of the class.

Definition 5.13

Let ${r_E}_{w, 0}$ denote the lexicographically first vector in the equivalence class $\{{r_E}\in \mathcal Z^n \mid \textsf{wt}({r_E}) = w\}$.

5.3.2 Applying Symmetry

Let $g^*$ be any optimal deterministic strategy. We will first construct a new optimal strategy $\textsc {Eve}_0$ that has the property that for all ${r_E}\in \mathcal Z^n$ and all permutations $\pi $, $\textsc {Eve}_0(\pi ({r_E})) = \pi (\textsc {Eve}_0({r_E}))$.

First, we prove a fact about the symmetry of $r$ and ${r_E}$.

Claim 5.14

For all $r\in \mathcal X^n$, ${r_E}\in \mathcal Z^n$, $\pi \in S_n$,

$$\begin{aligned}\Pr [R= r\mid {R_E}= {r_E}] = \Pr [R = \pi (r) \mid {R_E}= \pi ({r_E})]\end{aligned}$$

Proof

$\square $

Then we concretize the observation that $h_{r, \textsf{ChB}, n}$ depends only on the global probabilities of input–output pairs in $\mathcal X\times \mathcal Y$.

Claim 5.15

For a fixed $r\in \mathcal X^n, {r_B}\in \mathcal Y^n$, and any $\pi \in S_n$, $h_{r, \textsf{ChB}, n}({r_B}) = 1$ if and only if $h_{\pi (r), \textsf{ChB}, n}(\pi ({r_B})) = 1$.

Proof

Consider the multiset of input–output pairs $\{(r_i, {r_B}_{i})\}_{i \in [n]}$ of $r$ and ${r_B}$. This is equal to the multiset of input–output pairs $\{(\pi (r)_i, \pi ({r_B})_i)\}_{i \in [n]}$ of $\pi (r)$ and $\pi ({r_B})$.

Therefore for all $x \in \mathcal X$ and $y \in \mathcal Y$, we have

$$\begin{aligned} {\textsc {Ratio}_{x \rightarrow y}}(r, {r_B})&= \frac{|i \in [n] : r_i = x, {r_B}_{i} = y|}{N_{x}(r)}\\&= \frac{|i \in [n] : \pi (r)_i = x, \pi ({r_B})_{i} = y|}{N_{x}(\pi (r))}\\&= {\textsc {Ratio}_{x \rightarrow y}}(\pi (r), \pi ({r_B})) \end{aligned}$$

Thus, $h_{r, \textsf{ChB}, n}({r_B}) = h_{\pi (r), \textsf{ChB}, n}(\pi ({r_B}))$. $\square $

Claims 5.14 and 5.15 give the following corollary which states that a guess ${\widehat{r}_B}{}$ given received string ${r_E}$ should succeed with the same probability as a guess $\pi ({\widehat{r}_B}{})$ given received string $\pi ({r_E})$. More concretely,

Corollary 5.16

For all ${\widehat{r}_B}{}\in \mathcal Y^n, {r_E}\in \mathcal Z^n, \pi \in S_n$,

$$\begin{aligned}\Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}({\widehat{r}_B}{}) = 1 \mid {R_E}= {r_E}] = \Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(\pi ({\widehat{r}_B}{})) = 1 \mid {R_E}= \pi ({r_E})]\end{aligned}$$

Proof

This follows immediately from Claims 5.14 and 5.15:

$$\begin{aligned}&\Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}({\widehat{r}_B}{}) \\&\quad = 1 \mid {R_E}= {r_E}]\\&\quad = \sum _{r} h_{r, \textsf{ChB}, n}({\widehat{r}_B}{}) \cdot \Pr [R= r\mid {R_E}= {r_E}]\\&\quad = \sum _{r} h_{\pi (r), \textsf{ChB}, n}(\pi ({\widehat{r}_B}{})) \cdot \Pr [R= \pi (r) \mid {R_E}= \pi ({r_E})]\\&\quad = \sum _{\pi (r)} h_{\pi (r), \textsf{ChB}, n}(\pi ({\widehat{r}_B}{})) \cdot \Pr [R= \pi (r) \mid {R_E}= \pi ({r_E})]\\&\quad = \sum _{r'} h_{r', \textsf{ChB}, n}(\pi ({\widehat{r}_B}{})) \cdot \Pr [R= r' \mid {R_E}= \pi ({r_E})]\\&\quad = \Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(\pi ({\widehat{r}_B}{})) = 1 \mid {R_E}= \pi ({r_E})] \end{aligned}$$

$\square $

Now, we can prove that any optimal deterministic strategy $g^*: \mathcal X^n \rightarrow \mathcal Y^n$ does equally well on all permutations of received string ${r_E}$.

Lemma 5.17

For all ${r_E}\in \mathcal Z^n, \pi \in S_n$, and for any optimal deterministic strategy $g^*: \mathcal X^n \rightarrow \mathcal Y^n$,

$$\begin{aligned}\Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(g^*({R_E})) \mid {R_E}= {r_E}] = \Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(g^*({R_E})) \mid {R_E}= \pi ({r_E})] \end{aligned}$$

Proof

Using the definition of an optimal strategy and Corollary 5.16 we have

$$\begin{aligned} \Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(g^*({R_E})) \mid {R_E}= {r_E}]&= \max _{{\widehat{r}_B}{}} \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}({\widehat{r}_B}{}) = 1 \mid {R_E}= {r_E}] \\&= \max _{{\widehat{r}_B}{}} \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}(\pi ({\widehat{r}_B}{})) = 1 \mid {R_E}= \pi ({r_E})] \end{aligned}$$

Define ${r_B}' = \pi ({\widehat{r}_B}{})$. Then express the above as follows:

$$\begin{aligned} \Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(g^*({R_E})) \mid {R_E}= {r_E}]&=\max _{{r_B}'} \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}({r_B}') = 1 \mid {R_E}= \pi ({r_E})]\\&= \Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(g^*({R_E})) = 1 \mid {R_E}= \pi ({r_E})] \end{aligned}$$

$\square $

Although $g^*$ has the same probability of success on all permutations of a given string ${r_E}$, $g^*$ may still behave rather differently on each permutation. To deal with this, we construct a new optimal strategy $\textsc {Eve}_0$ that acts in a structured manner on each permutation of ${r_E}$ so that $\textsc {Eve}_0(\pi ({r_E})) = \pi (\textsc {Eve}_0({r_E}))$ for all $\pi \in S_n$.

We define $\textsc {Eve}_0$ from $g^*$ as follows:

Remark 5.18

For any weight w and any permutation $\tau \in S_n$,

$$\begin{aligned}\textsc {Eve}_0(\tau ({r_E}_{w,0})) = \tau (g^*({r_E}_{w,0}))\end{aligned}$$

In particular,

$$\begin{aligned}\textsc {Eve}_0({r_E}_{w,0}) = g^*({r_E}_{w,0})\end{aligned}$$

Lemma 5.19

If $g^*: \mathcal Z^n \rightarrow \mathcal Y^n$ is an optimal deterministic strategy, then $\textsc {Eve}_0: \mathcal Z^n \rightarrow \mathcal Y^n$ is an optimal strategy. Moreover, for any ${r_E}\in \mathcal Z^n$ and $\pi \in S_n$, $\textsc {Eve}_0(\pi ({r_E})) = \pi (\textsc {Eve}_0({r_E}))$.

Proof

Fix any ${r_E}\in \mathcal Z^n$. Let $w = \textsf{wt}({r_E})$, and let ${r_E}_{w,0}$ be the lexicographically first vector of weight w in $\mathcal Z^n$. Let $\sigma \in S_n$ such that $\sigma ({r_E}_{w,0}) = {r_E}$.

By Corollary 5.16, we have that

$$\begin{aligned}&\Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n} (\sigma (g^*({r_E}_{w,0}))) = 1 \mid {R_E}= \sigma ({r_E}_{w,0})] \\&\quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n} (g^*({r_E}_{w,0})) = 1 \mid {R_E}= {r_E}_{w,0}] \end{aligned}$$

By Lemma 5.17, we have that

$$\begin{aligned}&\Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n} (g^*({r_E}_{w,0})) = 1 \mid {R_E}= {r_E}_{w,0}] \\ {}&\quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n} (g^*({r_E})) = 1 \mid {R_E}= {r_E}] \end{aligned}$$

Therefore, by definition of $\textsc {Eve}_0$ and $\sigma $ and applying the above corollary and lemma,

$$\begin{aligned}&\Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n} (\textsc {Eve}_0({R_E})) = 1 \mid {R_E}= {r_E}]\\&\quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n} (\sigma (g^*({r_E}_{w,0}))) = 1 \mid {R_E}= \sigma ({r_E}_{w,0})]\\&\quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n} (g^*({r_E}_{w,0})) = 1 \mid {R_E}= {r_E}_{w,0}]\\&\quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n} (g^*({r_E})) = 1 \mid {R_E}= {r_E}] \end{aligned}$$

Thus, $\textsc {Eve}_0$ has the same probability of success as $g^*$, so $\textsc {Eve}_0$ is also an optimal strategy.

Finally, for any ${r_E}\in \mathcal Z^n$ and any $\pi \in S_n$, to show that $\textsc {Eve}_0(\pi ({r_E})) = \pi (\textsc {Eve}_0({r_E}))$, by Remark 5.18 we have that

$$\begin{aligned} \textsc {Eve}_0(\pi ({r_E}))&= \textsc {Eve}_0(\pi (\sigma ({r_E}_{ w, 0})))\\&= \pi (\sigma (g^*({r_E}_{ w, 0})))\\&= \pi (\textsc {Eve}_0(\sigma ({r_E}_{ w, 0})))\\&= \pi (\textsc {Eve}_0({r_E})) \end{aligned}$$

$\square $

5.3.3 Randomized Locations

Consider a probabilistic $\textsc {Eve}_1$ that on input ${r_E}\in \mathcal Z^n$ deviates slightly from the deterministic $\textsc {Eve}_0$. For any $z \in \mathcal Z$, $y \in \mathcal Y$, and input ${r_E}\in \mathcal Z^n$, $\textsc {Eve}_0$ maps some deterministically chosen subset of size $k_{z,y}$ of the z’s in ${r_E}$ to be a y in ${\widehat{r}_B}{}$. Instead, $\textsc {Eve}_1$, will map a random subset of size $k_{z,y}$ of the z’s in ${r_E}$ to be a y in ${\widehat{r}_B}{}$.

More formally, we define $\textsc {Eve}_1$ as follows.

Remark 5.20

Observe that for any fixed randomness e of $\textsc {Eve}_1$ and any ${r_E}\in \mathcal Z^n$, then there exists a permutation $\pi _e \in S_n$ such that $\textsc {Eve}_1({r_E}; e) = \pi _e(\textsc {Eve}_0({r_E}))$ where $\pi _e({r_E}) = {r_E}$.

We show that such a probabilistic $\textsc {Eve}_1$ has the same success probability as $\textsc {Eve}_0$.

Lemma 5.21

$$\begin{aligned}\Pr _{R, \textsf{ChE}, \textsc {Eve}_1} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_1({R_E})) = 1] = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_0({R_E})) = 1]\end{aligned}$$

Proof

It suffices to prove that for all ${r_E}\in \mathcal Z^n$ and randomness e for $\textsc {Eve}_1$,

$$\begin{aligned}{} & {} \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_1({R_E}; e)) = 1 \mid {R_E}= {r_E}] \\{} & {} \quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_0({R_E})) = 1 \mid {R_E}= {r_E}]\end{aligned}$$

Fix some choice of randomness e for $\textsc {Eve}_1$ and some ${r_E}\in \mathcal Z^n$. By Remark 5.20, there exists a permutation $\pi _e \in S_n$ such that $\textsc {Eve}_1({r_E}; e) = \pi _e(\textsc {Eve}_0({r_E}))$. By our construction of $\textsc {Eve}_0$ as stated in Lemma 5.19, $\pi _e(\textsc {Eve}_0({R_E})) = \textsc {Eve}_0(\pi _e({R_E}))$. Therefore,

$$\begin{aligned}&\Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_1({R_E}; e)) = 1 \mid {R_E}= {r_E}]\\&\quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}(\pi _e(\textsc {Eve}_0({R_E}))) = 1 \mid {R_E}= {r_E}]\\&\quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_0(\pi _e({R_E}))) = 1 \mid {R_E}= {r_E}]\\&\quad = \Pr _{R, \textsf{ChE}} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_0({R_E})) = 1 \mid {R_E}= {r_E}] \end{aligned}$$

where the last equality follows since $\pi _e({r_E}) = {r_E}$. $\square $

5.3.4 Stochastic Matrix Strategy

Consider a probabilistic $\textsc {Eve}_2$ that on input ${r_E}\in \mathcal Z^n$ defines a new channel $\textsf{Ch}_{{r_E}}$ from $\mathcal Z$ to $\mathcal Y$ such that $p_{{r_E}}(z \mid y) = {\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_0({r_E}))$ and applies this channel to each symbol of ${r_E}$ to get ${\widehat{r}_B}{}$.

We will now prove that $\textsc {Eve}_2$ cannot perform much worse than $\textsc {Eve}_1$. In particular, we will prove that for an overwhelming fraction of ${r_E}\in \mathcal Z^n$, then with probability at least $\frac{1}{{{\,\mathrm{\textsf{poly}}\,}}(n)}$, $\textsc {Eve}_2({r_E})$ will produce an output that is distributed identically to the distribution of $\textsc {Eve}_1({r_E})$.

First, we prove a fact about multinomial distributions and about ${R_E}$.

Claim 5.22

Let $n \in \mathbb {N}$, let $\ell $ be a nonnegative constant, and let $p_1 = p_1(n), \ldots , p_\ell = p_\ell (n)$ be such that $\sum _{i=1}^\ell p_i = 1$ and $\forall i \in [\ell ], p_i \in [0,1]$ and $n \cdot p_i \in \mathbb {N}\cup \{0\}$. Let $X = (X_1, \ldots , X_\ell ) \sim \textsf{Multinomial}(n;\ p_1, p_2, \ldots , p_\ell )$ where $X_i$ is a random variable denoting the number of occurrences of outcome i in n independent trials where $\Pr [\text {outcome i occurs in a trial}] = p_i$. Then the probability that each $X_i$ hits its expected value is

$$\begin{aligned}\Pr _X \left[ \bigwedge _{i=1}^{\ell } (X_i = n \cdot p_i) \right] = \Omega \left( \frac{1}{n^{\ell /2}}\right) \end{aligned}$$

Proof

First consider the case where each $p_i > 0$. Then, the Multinomial distribution’s probability mass function gives

$$\begin{aligned}\Pr _X \left[ \bigwedge _{i=1}^{\ell } X_i = n \cdot p_i \right] = \frac{n!}{\prod _{i=1}^{\ell } (n \cdot p_i) !} \cdot \prod _{i=1}^{\ell } p_i^{n \cdot p_i}.\end{aligned}$$

Apply Stirling’s Approximation^{Footnote 7} to obtain

$$\begin{aligned} \frac{n!}{\prod _{i=1}^{\ell } (n \cdot p_i) !} = \Theta \left( \frac{1}{ (\sqrt{2 \pi n})^{\ell - 1}\prod _{i=1}^{\ell } p_i^{n\cdot p_i + 1/2}}\right) \end{aligned}$$

Therefore, we get

$$\begin{aligned}\Pr _X \left[ \bigwedge _{i=1}^{\ell } X_i = n \cdot p_i \right] = \Theta \left( \frac{1}{ (\sqrt{2 \pi n})^{\ell - 1}\prod _{i=1}^{\ell } \sqrt{p_i}}\right) \end{aligned}$$

Since each $p_i \le 1$,

$$\begin{aligned}\Pr _X \left[ \bigwedge _{i=1}^{\ell } X_i = n \cdot p_i \right] = \Omega \left( \frac{1}{n^{(\ell - 1)/2}}\right) \end{aligned}$$

Now, consider the case where $p_i = 0$ for some $i \in [l]$. Let $S = \{i \in [l] \mid p_i \ne 0\}$. Then, for $i \notin S$, we always have $X_i = np_i = 0$, and for $j \in S$, then the distribution of $X_j$ is not affected by events of probability 0. Therefore,

$$\begin{aligned}\Pr _X \left[ \bigwedge _{i=1}^{\ell } X_i = n \cdot p_i \right] = \Pr _X \left[ \bigwedge _{i \in S} X_i = n \cdot p_i \right] = \Omega \left( \frac{1}{n^{(|S| - 1)/2}}\right) = \Omega \left( \frac{1}{n^{\ell /2}}\right) .\end{aligned}$$

$\square $

Definition 5.23

Let $\textsc {Good}_E= \left\{ {r_E}\in \mathcal Z^n \mid \forall z \in \mathcal Z, N_{z}({r_E}) \ge \frac{n}{2|\mathcal X|}\cdot \max _{x \in \mathcal X}\right. $ $\left. ({p_E}(z|x))\right\} \subset \mathcal Z^n$. Observe that for all ${r_E}\in \textsc {Good}_E$ and $z \in \mathcal Z$, then $N_{z}({r_E}) = \Theta (n)$.

Lemma 5.24

$\Pr _{R, \textsf{ChE}}[{r_E}\in \textsc {Good}_E] \ge 1 - \textsf{negl}(\lambda )$

Proof

For any $z \in \mathcal Z$ and $i \in [n]$, define

$$\begin{aligned} V_{z,i} = {\left\{ \begin{array}{ll} 1&{}\quad \text {if } {R_E}_i = z\\ 0&{}\quad \text {else} \end{array}\right. } \end{aligned}$$

Then,

$$\begin{aligned} \mathop {\mathrm {\mathbb {E}}}\limits [V_{z,i}]&= \sum _{x \in \mathcal X}{p_E}(z|x)\Pr [R_i = x]\\&= \sum _{x \in \mathcal X}{p_E}(z|x)\frac{1}{|\mathcal X|}\\&\ge \frac{1}{|\mathcal X|}\cdot \max _{x \in \mathcal X}({p_E}(z|x)) \end{aligned}$$

Therefore, by the Chernoff bound, for any $z \in \mathcal Z$, we have $N_{z}({R_E}) = \sum _{i \in [n]}V_{z,i}$, and

$$\begin{aligned}&\Pr \left[ {N_{z}({R_E}) \le \frac{1}{2}}\frac{n}{|\mathcal X|}\cdot \max _{x \in \mathcal X}({p_E}(z|x))\right] \\&\le \Pr \left[ {N_{z}({R_E}) \le \frac{1}{2}\cdot \mathop {\mathrm {\mathbb {E}}}\limits [N_{z}({R_E})]}\right] \\&< \exp \left( -\frac{\mathop {\mathrm {\mathbb {E}}}\limits [N_{z}({R_E})]}{8}\right) \\&\le \exp \left( -\frac{n}{8|\mathcal X|}\cdot \max _{x \in \mathcal X}({p_E}(z|x))\right) = \textsf{negl}(n) \end{aligned}$$

Thus,

$$\begin{aligned}&\Pr \left[ \forall z \in \mathcal Z, N_{z}({R_E}) \ge \frac{n}{2|\mathcal X|}\cdot \max _{x \in \mathcal X}({p_E}(z|x))\right] \\&\quad = 1 - \Pr \left[ \exists z \in \mathcal Z, N_{z}({R_E})< \frac{n}{2|\mathcal X|}\cdot \max _{x \in \mathcal X}({p_E}(z|x))\right] \\&\quad \ge 1 - \sum _{z \in \mathcal Z}\Pr \left[ N_{z}({R_E}) < \frac{n}{2|\mathcal X|}\cdot \max _{x \in \mathcal X}({p_E}(z|x))\right] \\&\quad = 1 - |\mathcal Z|\cdot \textsf{negl}(n)\\&\quad = 1 - \textsf{negl}(\lambda ) \end{aligned}$$

$\square $

Lemma 5.25

For all ${r_E}\in \textsc {Good}_E$, there exists a polynomial $p(n) = O\left( n^{\left|\mathcal Z\right|\left|\mathcal Y\right|/2}\right) $ such that

$$\begin{aligned}{} & {} \Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E}))= 1 \mid {R_E}= {r_E}] \\{} & {} \quad \ge \frac{1}{p(n)} \cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_1} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_1({R_E})) = 1 \mid {R_E}= {r_E}]\end{aligned}$$

Proof

Fix any ${r_E}\in \textsc {Good}_E$. We first want to show that with probability at least $\frac{1}{{{\,\mathrm{\textsf{poly}}\,}}(\lambda )}$, we have that

$$\begin{aligned}\forall z \in \mathcal Z, y \in \mathcal Y, {\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_2({r_E})) = {\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_0({r_E})).\end{aligned}$$

Fix any $z \in \mathcal Z$. Let $\mathcal Y= (y_1, \ldots , y_{|\mathcal Y|})$ and let $V_{z} = (V_{z, 1}, \ldots , V_{z, |\mathcal Y|})$ be a random variable over the randomness of $\textsc {Eve}_2$ defined by

$$\begin{aligned}V_{z, i} = N_{z}({r_E})\cdot {\textsc {Ratio}_{z \rightarrow y_i}}({r_E}, \textsc {Eve}_2({r_E})).\end{aligned}$$

For $i \in [|\mathcal Y|]$, let $p_i = {\textsc {Ratio}_{z \rightarrow y_i}}({r_E}, \textsc {Eve}_0({r_E}))$. Now, by definition of $\textsc {Eve}_2$,

$$\begin{aligned}V_{z} = (V_{z, 1}, \ldots , V_{z, \ell _z}) \sim \textsf{Multinomial}(N_{z}({r_E});\ p_1, \ldots , p_{|\mathcal Y|}).\end{aligned}$$

Then by Claim 5.22 and since ${r_E}\in \textsc {Good}_E$ implies $N_{z}({r_E}) = \Theta (n)$, then

$$\begin{aligned}\Pr _{V_z} \left[ \bigwedge _{i=1}^{\ell _z} (V_{z, i} = N_{z}({r_E}) \cdot p_i) \right] = \Omega \left( \frac{1}{n^{|\mathcal Y|/2}}\right) .\end{aligned}$$

Observe that since $\textsc {Eve}_2$’s choice of ${\widehat{r}_B}{}_i$ is conditionally independent of ${\widehat{r}_B}{}_j$ given ${r_E}$ for $i \ne j$, then for all $z \ne z'$, $V_{z}$ is independent of $V_{z'}$ given ${r_E}$. Therefore,

$$\begin{aligned}\Pr _{V} \left[ \bigwedge _{z \in \mathcal Z} \bigwedge _{i=1}^{\ell _z} (V_{z, i} = N_{z}({r_E}) \cdot p_i) \right] = \Omega \left( \frac{1}{n^{\left|\mathcal Z\right|\left|\mathcal Y\right|/2}}\right) .\end{aligned}$$

Now, for a fixed ${r_E}\in \textsc {Good}_E$, observe that $\bigwedge _{z \in \mathcal Z}\bigwedge _{i=1}^{\ell _z} (V_{z, i} = N_{z}({r_E}) \cdot p_i)$ is equivalent to the statement that $\forall z \in \mathcal Z, y \in \mathcal Y$, ${\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_2({r_E})) = {\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_1({r_E}))$. Thus, the distribution of $\textsc {Eve}_2({r_E})$ conditioned on this event is uniformly distributed over all ${\widehat{r}_B}{}\in \mathcal Y^n$ with the property that $\forall z \in \mathcal Z, y \in \mathcal Y$, ${\textsc {Ratio}_{z \rightarrow y}}({r_E}, {\widehat{r}_B}{}) = {\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_0({r_E}))$. But this means that conditioned on this event, the distribution of $\textsc {Eve}_2({r_E})$ is identical to the distribution of $\textsc {Eve}_1({r_E})$ and so $\textsc {Eve}_2$ succeeds with equal probability as $\textsc {Eve}_1$. Therefore there exists a polynomial $p(n) = O\left( n^{\left|\mathcal Z\right|\left|\mathcal Y\right|/2}\right) $ such that

$\square $

Corollary 5.26

There exists a polynomial $p(n) = O\left( n^{\left|\mathcal Z\right|\left|\mathcal Y\right|/2}\right) $ such that

$$\begin{aligned}{} & {} p(n)\cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1] + \textsf{negl}(\lambda ) \\{} & {} \quad \ge \Pr _{R, \textsf{ChE}, \textsc {Eve}_1} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_1({R_E})) = 1]\end{aligned}$$

Proof

For ${r_E}\in \textsc {Good}_E$, let $p_{{r_E}}(n)$ be the polynomial for ${r_E}$ described in Lemma 5.25. Let $p(n) = \max _{{r_E}\in \textsc {Good}_E}\left( p_{{r_E}}(n)\right) = O\left( n^{\left|\mathcal Z\right|\left|\mathcal Y\right|/2}\right) $. Then, by Lemma 5.25,

$$\begin{aligned}&p(n)\cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1] + \Pr [{R_E}\notin \textsc {Good}_E]\\&\quad \ge \sum _{{r_E}\in \textsc {Good}_E}\left( p(n) \cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1 \mid {R_E}= {r_E}]\cdot \Pr [{R_E}= {r_E}]\right) \\&\qquad + \Pr [{R_E}\notin \textsc {Good}_E]\\&\quad \ge \sum _{{r_E}\in \textsc {Good}_E}\left( \frac{p(n)}{p_{{r_E}}(n)}\cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1 \mid {R_E}= {r_E}]\cdot \Pr [{R_E}= {r_E}]\right) \\&\qquad + \Pr [{R_E}\notin \textsc {Good}_E]\\&\quad \ge \Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1 \mid {R_E}\in \textsc {Good}_E] + \Pr [{R_E}\notin \textsc {Good}_E]\\&\quad \ge \Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1] \end{aligned}$$

The corollary then follows since $\Pr [{R_E}\notin \textsc {Good}_E] = \textsf{negl}(\lambda )$ by Lemma 5.24. $\square $

5.3.5 Input-Independent Strategy

Now, although $\textsc {Eve}_2$’s strategy is to apply a channel $\textsf{Ch}_{{r_E}}$ to each symbol of her input ${r_E}$, the choice of channel she applies is dependent on which ${r_E}$ she received. To remove this dependence, we construct an $\textsc {Eve}_3$ who in addition to getting input ${r_E}$ also gets an independent random input w that defines which channel $\textsf{Ch}_{w}$ that $\textsc {Eve}_3$ should apply to ${r_E}$. More formally,

Notation

Let $\mathcal W_n = \{ w = (w_1, \ldots , w_{|\mathcal Z|}) \mid \sum _{i = 1}^{|\mathcal Z|}(w_i) = n\} = \{w \in \mathbb {N}^n \mid w = \textsf{wt}({r_E}) \text { for some } {r_E}\in \mathcal Z^n\}$ be the set of all weight vectors of $\mathcal Z^n$.
Note that $|\mathcal W_n| = \left( {\begin{array}{c}n + |\mathcal Z| - 1\\ |\mathcal Z| - 1\end{array}}\right) = {{\,\mathrm{\textsf{poly}}\,}}(n)$.
Let W be a random variable uniformly distributed over $\mathcal W_n$.

Now, we will show that $\textsc {Eve}_3(\textsf{wt}({r_E}), {r_E})$ has the same behavior as $\textsc {Eve}_2({r_E})$.

Lemma 5.27

For all weights $w \in \mathcal W_n$ and all ${r_E}\in \mathcal Z^n$ such that $\textsf{wt}({r_E}) = w$, then

$$\begin{aligned}\textsf{Ch}_{w} = \textsf{Ch}_{{r_E}}\end{aligned}$$

where $\textsf{Ch}_{w}$ is defined as in $\textsc {Eve}_3$ and $\textsf{Ch}_{{r_E}}$ is defined as in $\textsc {Eve}_2$.

Proof

Since for all ${r_E}\in \mathcal Z^n$ and $\pi \in S_n$, $\textsc {Eve}_0(\pi ({r_E})) = \pi (\textsc {Eve}_0({r_E}))$, then

$$\begin{aligned}{}[{\textsc {Ratio}_{z \rightarrow y}}({r_E}, \textsc {Eve}_0({r_E}))]_{z \in \mathcal Z, y \in \mathcal Y}&= [{\textsc {Ratio}_{z \rightarrow y}}(\pi ({r_E}), \pi (\textsc {Eve}_0({r_E})))]_{z \in \mathcal Z, y \in \mathcal Y} \\&= [{\textsc {Ratio}_{z \rightarrow y}}(\pi ({r_E}), \textsc {Eve}_0(\pi ({r_E})))]_{z \in \mathcal Z, y \in \mathcal Y} \end{aligned}$$

Therefore, for all $({r_E}, {r_E}') \in \textsc {Eqwt}$, $\textsf{Ch}_{{r_E}} = \textsf{Ch}_{{r_E}'}$. Thus, $\textsf{Ch}_{w} = \textsf{Ch}_{{r_E}_{w,0}} = \textsf{Ch}_{{r_E}}$. $\square $

Corollary 5.28

For any ${r_E}\in \mathcal Z^n$, the distribution of $\textsc {Eve}_3(\textsf{wt}({r_E}), {r_E})$ is the same as the distribution of $\textsc {Eve}_2({r_E})$.

Proof

This follows directly from Lemma 5.27 by definition of $\textsc {Eve}_2$ and $\textsc {Eve}_3$. $\square $

We claim that given a uniformly randomly chosen weight vector w, $\textsc {Eve}_3$’s probability of success is not much worse than $\textsc {Eve}_2$’s probability of success. This follows since there are only polynomially many possible weight vectors, so with some inverse polynomially probability, the randomly chosen weight w for $\textsc {Eve}_3$ will be equal to $\textsf{wt}({r_E})$ and thus $\textsc {Eve}_3$ will act identically to $\textsc {Eve}_2$.

Lemma 5.29

$$\begin{aligned}{} & {} \Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W, {R_E})) = 1] \\{} & {} \quad \ge \frac{1}{q(n)} \cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1]\end{aligned}$$

where $q(n) = \left( {\begin{array}{c}n + |\mathcal Z| - 1\\ |\mathcal Z| - 1\end{array}}\right) = |\mathcal W_n| = {{\,\mathrm{\textsf{poly}}\,}}(n)$.

Proof

$$\begin{aligned}&\Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W}[h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W, {R_E})) = 1] \\&\quad \ge \Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W}[W = \textsf{wt}({R_E})]\cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W} \\&\qquad [h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W, {R_E})) = 1 \mid W = \textsf{wt}({R_E})]\\&\quad = \frac{1}{|\mathcal W_n|}\Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W, {R_E})) = 1 \mid W = \textsf{wt}({R_E})]\\&\quad = \frac{1}{|\mathcal W_n|}\Pr _{R, \textsf{ChE}, \textsc {Eve}_2} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1]\ \end{aligned}$$

where the last equality follows by Corollary 5.28. $\square $

Finally, we prove that $\textsc {Eve}_3$ only succeeds with negligible probability. This step crucially requires that the main channel $\textsf{ChB}$ is not a degradation of Eve’s channel $\textsf{ChE}$. Recall that $\textsc {Good}= \{r\in \mathcal X^n \mid \forall x \in \mathcal X, N_{x}(r) \ge \frac{n}{2|\mathcal X|}\} \subset \mathcal X^n$ and that for all $r\in \textsc {Good}$ and $x \in \mathcal X$, then $N_{x}(r) = \Theta (n)$.

Lemma 5.30

$$\begin{aligned}\Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W, {R_E})) = 1] \le \textsf{negl}(\lambda )\end{aligned}$$

Proof

First,

$$\begin{aligned}&\Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W, {R_E})) = 1] \\&\quad \le \Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W, {R_E})) = 1 \mid R\in \textsc {Good}] \\&\qquad + \Pr _{R}[R\notin \textsc {Good}] \\&\quad \le \max _{w \in W, r\in \textsc {Good}} \left( \Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W} [h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W, {R_E})) = 1 \mid W = w, R= r]\right) \\&\qquad + \Pr _{R}[R\notin \textsc {Good}]\\&\quad = \max _{w \in W, r\in \textsc {Good}} \left( \Pr _{\textsf{ChE}, \textsc {Eve}_3} [h_{r, \textsf{ChB}, n}(\textsc {Eve}_3(w, \textsf{ChE}(r)) = 1]\right) + \Pr _{R}[R\notin \textsc {Good}]\ \end{aligned}$$

By Lemma 5.7, $\Pr _{R}[R\notin \textsc {Good}] \le \textsf{negl}(\lambda )$, so it suffices to prove that $\forall w \in \mathcal W_n$ and $\forall r\in \textsc {Good}$,

$$\begin{aligned}\Pr _{\textsf{ChE}, \textsc {Eve}_3} [h_{r, \textsf{ChB}, n}(\textsc {Eve}_3(w, \textsf{ChE}(r)) = 1] = \textsf{negl}(\lambda )\end{aligned}$$

Fix any $w \in \mathcal W_n$ and any $r\in \textsc {Good}$. Let $\textsf{Ch}_{w}$ be defined by stochastic matrix

$$\begin{aligned}P_{w} = [p_{w}(y \mid z)]_{z \in \mathcal Z, y \in \mathcal Y} = [{\textsc {Ratio}_{z \rightarrow y}}({r_E}_{w,0}, \textsc {Eve}_0({r_E}_{w,0}))]_{z \in \mathcal Z, y \in \mathcal Y}\end{aligned}$$

Let ${{\widehat{R}_B}{}_{|r, w}}{}$ be a random variable representing the output of $\textsc {Eve}_3(w, \textsf{ChE}(r))$. Now, by definition of $\textsc {Eve}_3$, the distribution of each $({{\widehat{R}_B}{}_{|r, w}}{})_i = \textsf{Ch}_{w}(\textsf{ChE}(r_i))$. In other words, ${{\widehat{R}_B}{}_{|r, w}}{}$ is produced by sending $r$ symbol by symbol through a channel formed by concatenating $\textsf{ChE}$ with $\textsf{Ch}_{w}$. Intuitively, since $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$ then this concatenated channel should not emulate $\textsf{ChB}$ well, and therefore we expect some ratio ${\textsc {Ratio}_{x \rightarrow y}}(r, {{\widehat{R}_B}{}_{|r, w}}{})$ to be far from the ratio ${p_B}(y|x)$ expected by $f_{m, r, \textsf{ChB},n}$.

Indeed, since $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$, then by Lemma 3.14 there exists a constant $d > 0$ and $x^* \in \mathcal X, y^* \in \mathcal Y$ such that

$$\begin{aligned}\left|[{P_B}- {P_E}\cdot P_{w}]_{x^*,y^*}\right| \ge d.\end{aligned}$$

Or equivalently, using $p_{E \cdot w}(y^* | x^*) = [{P_E}\cdot P_{w}]_{x^*, y^*} = \Pr [\textsf{Ch}_{w}(\textsf{ChE}(x^*)) = y^*]$,

$$\begin{aligned}\left|{p_B}(y^*|x^*) - p_{E \cdot w}(y^*|x^*)\right| \ge d\end{aligned}$$

Therefore, since d is constant, for large enough n,

$$\begin{aligned}&\Pr _{\textsf{ChE}, \textsc {Eve}_3} [h_{r, \textsf{ChB}, n}(\textsc {Eve}_3(w, \textsf{ChE}(r))) = 1] \\&\quad \le \Pr _{\textsf{ChE}, \textsc {Eve}_3}\left[ |{\textsc {Ratio}_{x^* \rightarrow y^*}}(r, {{\widehat{R}_B}{}_{|r, w}}{}) - {p_B}(y^*|x^*)| \le |\mathcal Y|\cdot n^{-\frac{1}{3}}\right] \\&\quad \le \Pr _{\textsf{ChE}, \textsc {Eve}_3}\left[ |{\textsc {Ratio}_{x^* \rightarrow y^*}}(r, {{\widehat{R}_B}{}_{|r, w}}{}) - p_{E \cdot w}(y^*|x^*)| \ge |\mathcal Y|\cdot n^{-\frac{1}{3}}\right] \end{aligned}$$

For all $i \in [n]$, define

$$\begin{aligned} V_{i} = {\left\{ \begin{array}{ll} 1&{}\quad \text {if } r_i = x^* \text { and } ({{\widehat{R}_B}{}_{|r, w}}{})_i = y^*\\ 0 &{}\quad \text {else} \end{array}\right. } \end{aligned}$$

Let $S_{x^*} = \{i \in [n] \mid r_i = x^*\}$. Then,

$$\begin{aligned} \forall i \in S_{x^*}, \Pr [V_i = 1] = p_{E \cdot w}(y^*|x^*)\\ \mathop {\mathrm {\mathbb {E}}}\limits \left[ \sum _{i \in S_{x^*}}V_i\right] = N_{x^*}(r)\cdot p_{E \cdot w}(y^*|x^*)\\ \sum _{i \in S_{x^*}}V_i = N_{x^*}(r)\cdot {\textsc {Ratio}_{x^* \rightarrow y^*}}(r, {{\widehat{R}_B}{}_{|r, w}}{}) \end{aligned}$$

By a Chernoff bound,

$$\begin{aligned}&\Pr _{\textsf{ChE}, \textsc {Eve}_3}\left[ |{\textsc {Ratio}_{x^* \rightarrow y^*}}(r, {{\widehat{R}_B}{}_{|r, w}}{}) - p_{E \cdot w}(y^*|x^*)| \ge |\mathcal Y|\cdot n^{-\frac{1}{3}}\right] \\&\quad =\Pr \left[ \left|\sum _{i \in S_{x^*}} V_{i} - N_{x^*}(r)\cdot p_{E \cdot w}(y^*|x^*)\right| \ge N_{x^*}(r) \cdot |\mathcal Y|\cdot n^{-\frac{1}{3}}\right] \\&\quad \le 2 \cdot \exp \left( \frac{- N_{x^*}(r)\cdot |\mathcal Y|^2 \cdot n^{-2/3}}{3 \cdot p_{E \cdot w}(y^*|x^*)}\right) . \end{aligned}$$

Since $p_{E \cdot w}(y^* | x^*) \le 1$ and $r\in \textsc {Good}$ implies $N_{x^*}(r) = \Theta (n)$,

$$\begin{aligned} \Pr \left[ \left|\sum _{i \in S_{x^*}} V_{i} - N_{x^*}(r)\cdot p_{E \cdot w}(y^*|x^*)\right| \ge N_{x^*}(r) \cdot |\mathcal Y|\cdot n^{-\frac{1}{3}}\right]&\le 2 \cdot e^{-\Omega (n^{1/3})} = \textsf{negl}(\lambda ). \end{aligned}$$

Thus, our lemma holds since for any $w \in \mathcal W_n$ and any $r\in \textsc {Good}$,

$$\begin{aligned} \Pr _{\textsf{ChE}, \textsc {Eve}_3} [h_{r, \textsf{ChB}, n}(\textsc {Eve}_3(w, \textsf{ChE}(r))) = 1] \le \textsf{negl}(\lambda ) \end{aligned}$$

$\square $

5.3.6 Putting it Together

Theorem 5.31

For all randomized functions $g: \mathcal Z^n \rightarrow \mathcal Y^n$,

$$\begin{aligned}\Pr _{R, \textsf{ChE}, g}[h_{R, \textsf{ChB}, n}(g({R_E})) = 1] \le \textsf{negl}(\lambda )\end{aligned}$$

Proof

By Lemma 5.19, $\textsc {Eve}_0$ is an optimal strategy so

$$\begin{aligned}\Pr _{R, \textsf{ChE}, g}[h_{R, \textsf{ChB}, n}(g({R_E})) = 1] \le \Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(\textsc {Eve}_0({R_E})) = 1]\end{aligned}$$

Then, by Lemma 5.21, Corollary 5.26, Lemmas 5.29 and 5.30 for some polynomials $p(n), q(n) = {{\,\mathrm{\textsf{poly}}\,}}(n)$,

$$\begin{aligned}&\Pr _{R, \textsf{ChE}}[h_{R, \textsf{ChB}, n}(\textsc {Eve}_0({R_E})) = 1]\\&\quad = \Pr _{R, \textsf{ChE}, \textsc {Eve}_1}[h_{R, \textsf{ChB}, n}(\textsc {Eve}_1({R_E})) = 1]\\&\quad \le p(n)\cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_2}[h_{R, \textsf{ChB}, n}(\textsc {Eve}_2({R_E})) = 1] + \textsf{negl}(\lambda )\\&\quad \le p(n)\cdot q(n)\cdot \Pr _{R, \textsf{ChE}, \textsc {Eve}_3, W}[h_{R, \textsf{ChB}, n}(\textsc {Eve}_3(W,{R_E})) = 1] + \textsf{negl}(\lambda )\\&\quad \le p(n)\cdot q(n) \cdot \textsf{negl}(\lambda ) + \textsf{negl}(\lambda )\\&\quad \le \textsf{negl}(\lambda ) \end{aligned}$$

$\square $

We now show that this implies that any strategy g can only cause $f_{m, R, \textsf{ChB}, n}$ to output m with negligible probability. This follows from the lemma below:

Lemma 5.32

For any $r\in \mathcal X^n$ and ${\widehat{r}_B}{}\in \mathcal Y^n$,

$$\begin{aligned}\forall x \in \mathcal X, y \in \mathcal Y,\; {\textsc {Ratio}_{x \rightarrow y}}(r, {\widehat{r}_B}{}) \le {p_B}(y|x) + n^{-\frac{1}{3}}\end{aligned}$$

implies

$$\begin{aligned}\forall x \in \mathcal X, y \in \mathcal Y,\; \left|{\textsc {Ratio}_{x \rightarrow y}}(r, {\widehat{r}_B}{}) - {p_B}(y|x)\right| \le |\mathcal Y|\cdot n^{-\frac{1}{3}}\end{aligned}$$

Proof

Fix any $r\in \mathcal X^n$ and ${\widehat{r}_B}{}\in \mathcal Y^n$. Suppose that $\forall x \in \mathcal X, y \in \mathcal Y,\; {\textsc {Ratio}_{x \rightarrow y}}(r, {\widehat{r}_B}{}) \le {p_B}(y|x) + n^{-\frac{1}{3}}$. Then, clearly

$$\begin{aligned}\forall x \in \mathcal X, y \in \mathcal Y, {\textsc {Ratio}_{x \rightarrow y}}(r, {\widehat{r}_B}{}) \le {p_B}(y|x) + |\mathcal Y|\cdot n^{-\frac{1}{3}}\end{aligned}$$

To show the other inequality induced by the absolute value, first fix any $x^* \in \mathcal X$ and $y^* \in \mathcal Y$. Then, by definition of the ratio function,

$$\begin{aligned} N_{x^*}(r)&= \sum _{y \in \mathcal Y}N_{x^*}(r)\cdot {\textsc {Ratio}_{x^* \rightarrow y}}(r, {\widehat{r}_B}{})\\ 1&= \sum _{y \in \mathcal Y}{\textsc {Ratio}_{x^* \rightarrow y}}(r, {\widehat{r}_B}{}) \end{aligned}$$

This implies

$$\begin{aligned} {\textsc {Ratio}_{x^* \rightarrow y^*}}(r, {\widehat{r}_B}{})&= 1 - \sum _{y \ne y^* \in \mathcal Y}{\textsc {Ratio}_{x^* \rightarrow y}}(r, {\widehat{r}_B}{})\\&\ge 1 - \sum _{y \ne y^* \in \mathcal Y}\left( {p_B}(y|x^*) + n^{-\frac{1}{3}}\right) \\&= \left( 1 - \sum _{y \ne y^* \in \mathcal Y}{p_B}(y|x^*)\right) - \sum _{y \ne y^* \in \mathcal Y}n^{-\frac{1}{3}}\\&= {p_B}(y^*\mid x^*) - (|\mathcal Y| - 1)n^{-\frac{1}{3}}\end{aligned}$$

Thus,

$$\begin{aligned}\forall x \in \mathcal X, y \in \mathcal Y, {\textsc {Ratio}_{x \rightarrow y}}(r, {\widehat{r}_B}{}) \ge {p_B}(y|x) - |\mathcal Y|\cdot n^{-\frac{1}{3}}\end{aligned}$$

so the claim follows. $\square $

Therefore, we obtain

Theorem 5.33

For all randomized functions $g: \mathcal Z^n \rightarrow \mathcal Y^n$ and any message $m \in \{0,1\}$,

$$\begin{aligned}\Pr _{R, \textsf{ChE}, g}[f_{m, R, \textsf{ChB}, n}(g({R_E})) \ne \bot ] \le \textsf{negl}(\lambda )\end{aligned}$$

Proof

By Theorem 5.31 and Lemma 5.32

$$\begin{aligned}&\Pr _{R, \textsf{ChE}, g}[f_{m, R, \textsf{ChB}, n}(g({R_E})) \ne \bot ] \\&\quad = \Pr _{R, \textsf{ChE}, g}\big [\forall x \in \mathcal X, y \in \mathcal Y,\; {\textsc {Ratio}_{x \rightarrow y}}(R, g({R_E})) \le {p_B}(y|x) + n^{-\frac{1}{3}}\big ]\\&\quad \le \Pr _{R, \textsf{ChE}, g}\big [\forall x \in \mathcal X, y \in \mathcal Y,\; \left|{\textsc {Ratio}_{x \rightarrow y}}(R, g({R_E})) - {p_B}(y|x)\right| \le |\mathcal Y|\cdot n^{-\frac{1}{3}}\big ]\\&\quad = \Pr _{R, \textsf{ChE}, g}[h_{R, \textsf{ChB}, n}(g({R_E})) = 1] \le \textsf{negl}(\lambda ) \end{aligned}$$

$\square $

We now prove full security.

Theorem 5.34

For every polynomial query bound $q(\lambda )$ and (computationally unbounded) adversary $\mathcal A^{(\cdot )}$ that makes at most $q(\lambda )$ queries to its oracle,

$$\begin{aligned}\Pr [\mathcal A^{f_{b, r, \textsf{ChB}, n}}(1^\lambda , \textsf{ChE}(r)) = b \mid (f_{b, r, \textsf{ChB}, n}, r) \leftarrow {{\,\textrm{Enc}\,}}_\textsf{ChB}(1^\lambda , b)] \le \frac{1}{2} + \textsf{negl}(\lambda )\end{aligned}$$

where b is uniformly distributed over $\{0,1\}$.

Proof

Consider any unbounded adversary $\mathcal A^{(\cdot )}$ which will make at most a polynomial number q(n) of queries to its oracle. For $i \in \{0, 1, 2, \ldots , q(n)\}$, define $\textsf{View}^{(i)}_{b}$ to be the distribution of views (transcripts) of $\mathcal A$ interacting with the oracle $f_{b, r, \textsf{ChB}, n}$ i-times when the challenge bit is b. Let $V^{(i)}_{b}$ be a random variable over $\textsf{View}^{(i)}_{b}$ and define for convenience an indicator $\mathcal Q:\textsf{View}^{(i)}_{b} \rightarrow \{\top , \bot \}$ such that $\mathcal Q(v) = \bot $ if and only if $f_{b, r, \textsf{ChB}, n}$ output $\bot $ for all queries in v. For example, the starting view is $({r_E})$ and after a single query ${\widehat{r}_B}{}_1$ to the oracle that returned $\bot $ the view is $({r_E}, {\widehat{r}_B}{}_1, \bot )$. Observe that if $\mathcal A$ submits no queries to the oracle, then $\mathcal A$ is completely unable to distinguish between the $b= 0$ and $b=1$ case as $v = ({r_E})$ is a random string chosen independently from b, so

$$\begin{aligned}\Pr _{\textsf{View}^{(0)}_{0}} \left[ V^{(0)}_{0} = v \right] = \Pr _{\textsf{View}^{(0)}_{1}} \left[ V^{(0)}_{1} = v \right] \end{aligned}$$

Now, the first query ${\widehat{r}_B}{}_1$ is equally like to be chosen regardless of b since the views were identically distributed when $i = 0$. Therefore as long as the oracle does not reveal the message (doing so reveals the challenge bit), the distribution of views is identical.

$$\begin{aligned}\Pr _{\textsf{View}^{(1)}_{0}} \left[ V^{(1)}_{0} = v \mid \mathcal Q(v) = \bot \right] = \Pr _{\textsf{View}^{(1)}_{1}} \left[ V^{(1)}_{1} = v \mid \mathcal Q(v) = \bot \right] \end{aligned}$$

Then by induction the ith query is equally likely to be chosen assuming all previous queries do not reveal the message.

$$\begin{aligned}\Pr _{\textsf{View}^{(q(n))}_{0}} \left[ V^{(q(n))}_{0} = v \mid \mathcal Q(v) = \bot \right] = \Pr _{\textsf{View}^{(q(n))}_{1}} \left[ V^{(q(n))}_{1} = v \mid \mathcal Q(v) = \bot \right] \end{aligned}$$

Now it remains to show that the probability that $\mathcal Q(v) = \bot $ over $v \in \textsf{View}^{(q(n))}_{b}$ is negligible. We proceed by a standard union bound strategy. Suppose $g_1$ is the first randomized strategy that $\mathcal A$ uses to produce a query to the oracle. By Theorem 5.33 the probability that any randomized strategy $g_1$ produces a guess that reveals the message b is negligible:

$$\begin{aligned}\Pr _{R, \textsf{ChE}, g_1}[f_{b, R, \textsf{ChB}, n}(g_1({r_E})) \ne \bot ] \le \textsf{negl}(\lambda )\end{aligned}$$

Now consider any randomness $(r^*_1, \ldots , r^*_{i-1})$ needed for generating the first $i - 1$ queries of $\mathcal A$. Let $g_i$ be the randomized strategy that $\mathcal A$ would use to produce the ith query assuming that all of the first $i - 1$ queries to the oracle (that would have been generated by $({R_E}, r^*_1, \ldots , r^*_{i-1})$) all returned $\bot $. Again by Theorem 5.33 the probability that any randomized strategy $g_i$ produces a guess that reveals the message b is negligible.

$$\begin{aligned}\Pr _{R, \textsf{ChE}, g_i}[f_{b, R, \textsf{ChB}, n}(g_i({R_E})) \ne \bot ] \le \textsf{negl}(\lambda )\end{aligned}$$

By a union bound, the probability that $\mathcal A$ learns b from any polynomial q(n) number of queries is $q(n) \cdot \textsf{negl}(\lambda )$. Thus, with probability $1 - q(n) \cdot \textsf{negl}(\lambda ) = 1 - \textsf{negl}(\lambda )$, $\mathcal A$ will not learn b from any oracle query, so

$$\begin{aligned}\Pr _{\textsf{View}^{(q(n))}_{b}} \left[ \mathcal Q\left( V^{(q(n))}_{b}\right) = \bot \right] = 1 - \textsf{negl}(\lambda ).\end{aligned}$$

In other words, $\mathcal A$ can only distinguish between $b = 0$ and $b=1$ when $\mathcal Q(V^{(q(n))}_{b}) = \top $, but this occurs with $\textsf{negl}(\lambda )$ probability. $\square $

6 Universal Coding Schemes

A universal coding scheme for a main channel $\textsf{ChB}$ is a wiretap coding scheme that allows decoding for Bob but is secure against any eavesdropping channel $\textsf{ChE}$ from some set $\mathcal E$.

Definition 6.1

(secure $(\textsf{ChB}, \mathcal E)$-universal coding scheme) A statistically secure (resp. computationally secure, resp. bounded query secure in the ideal obfuscation model) $(\textsf{ChB}, \mathcal E)$-universal coding scheme for channel $\textsf{ChB}$, a class of eavesdropping channels $\mathcal E$, and message space $\mathcal M$ is a wiretap coding scheme $({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ that is a statistically secure (resp. computationally secure, resp. bounded query secure in the ideal obfuscation model) wiretap coding scheme for all wiretap channels in the set $\{(\textsf{ChB}, \textsf{ChE}) \mid \textsf{ChE}\in \mathcal E\}$ and for message space $\mathcal M$.

6.1 Our Construction is a Universal Coding Scheme in the Ideal Oracle Model

We observe that for any channel $\textsf{ChB}$, our wiretap coding scheme $({{\,\textrm{Enc}\,}}_\textsf{ChB}, {{\,\textrm{Dec}\,}}_\textsf{ChB})$ in the ideal oracle model gives us a universal coding scheme against all eavesdropping channels for which secure wiretap coding schemes are possible. Recall, that if $\textsf{ChB}$ is a degradation of $\textsf{ChE}$, then no secure wiretap coding scheme is possible since the adversary can simulate anything that $\textsf{ChB}$ produces.

Theorem 6.2

Let $\textsf{ChB}$ be any channel and let

$$\begin{aligned} \textsf{Not}\text {-}\textsf{Degraded}(\textsf{ChB}) = \{\textsf{ChE}\mid \textsf{ChB} \text{ is } \text{ not } \text{ a } \text{ degradation } \text{ of } \textsf{ChE}\}. \end{aligned}$$

Then, $({{\,\textrm{Enc}\,}}_\textsf{ChB}, {{\,\textrm{Dec}\,}}_\textsf{ChB}^{(\cdot )})$ is a bounded query secure $(\textsf{ChB}, \textsf{Not}\text {-}\textsf{Degraded}(\textsf{ChB}))$ wiretap coding scheme in the ideal oracle model.

Proof

The proof follows by Corollary 5.4 and the observation that $({{\,\textrm{Enc}\,}}_\textsf{ChB}, {{\,\textrm{Dec}\,}}_\textsf{ChB}^{(\cdot )})$ only depend on $\textsf{ChB}$. $\square $

6.2 Universal Coding Schemes in the Information Theoretic Setting

In contrast, in the information theoretic setting, there exist channels $\textsf{ChB}$ for which there is no positive rate universal coding schemes against all channels $\textsf{ChE}$ that are not less noisy than $\textsf{ChB}$. Recall that there exist positive rate statistically secure wiretap codings for general message spaces for wiretap channel $(\textsf{ChB}, \textsf{ChE})$ if and only if $\textsf{ChE}$ is not less noisy than $\textsf{ChB}$ (Theorem 4.17).

Remark 6.3

As we are considering positive rate wiretap codings, we consider universality with respect to the definition of statistically secure wiretap codings for general message spaces (see Sect. 4.4).

We consider a simple example where both $\textsf{ChB}$ and $\textsf{ChE}$ are $\textsf{BSC}$ channels. Note that if $\textsf{ChB}= \textsf{BSC}_p$ and $\textsf{ChE}= \textsf{BSC}_{p'}$ with $p' > p$, then $\textsf{ChE}$ is a degradation of $\textsf{ChB}$ and therefore not less noisy than $\textsf{ChB}$.

Theorem 6.4

There is no positive rate statistically secure $(\textsf{ChB}, \mathcal E)$-universal coding scheme, where $\textsf{ChB}= \textsf{BSC}_p$ and $\mathcal E= \{ \textsf{BSC}_{p'}: p' > p \}$.

Proof

Suppose for sake of contradiction that $({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ is a statistically secure $(\textsf{ChB}, \mathcal E)$-universal coding scheme with rate $R > 0$ for some message space $\mathcal M$. Now, the secrecy capacity of a $(\textsf{ChB}= \textsf{BSC}_{p}, \textsf{ChE}=\textsf{BSC}_{p'})$ wiretap channel is the difference of their capacities, namely $C_s(\textsf{BSC}_{p}, \textsf{BSC}_{p'}) = h_2(p') - h_2(p)$ [26]. Thus, for any $\varepsilon > 0$, there exists a parameter $p_\varepsilon > p$ such that $C_s(\textsf{BSC}_{p}, \textsf{BSC}_{p_\varepsilon }) = \varepsilon $. Choose any positive $\varepsilon ' < R$. Then, $\textsf{BSC}_{p_{\varepsilon '}} \in \mathcal E$ and $C_s(\textsf{BSC}_p, \textsf{BSC}_{p_{\varepsilon '}}) < R$. But by definition of secrecy capacity (Definition 4.10), this means that a wiretap coding scheme with rate $R > C_s$ cannot be a CK rate-R wiretap coding family. But since CK correctness and security are weaker than requiring overwhelming correctness and semantic security, then this means that $({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ cannot be a statistically secure wiretap coding scheme for $(\textsf{BSC}_p, \textsf{BSC}_{p_{\varepsilon '}})$, which is a contradiction. $\square $

Theorem 6.4 shows that in general, there are no positive rate statistically secure universal coding schemes for every channel $\textsf{ChB}$ against all channels that are not less noisy than $\textsf{ChB}$. We conjecture that outside this case there are many settings in which there are no positive rate statistically secure universal coding schemes. To prove this conjecture for eavesdropping channel family $\mathcal E$, it suffices to show that for any main channel $\textsf{ChB}$ and any $\varepsilon >0$, there exists a channel $\textsf{ChE}_{\varepsilon } \in \mathcal E$ whose secrecy capacity with $\textsf{ChB}$ is equal to $\varepsilon $.

7 Instantiating the Oracle via Obfuscation

7.1 Obfuscation Definitions

We now give obfuscation definitions that suffice for building computationally secure wiretap coding schemes. Crucially, we will use the fact that the function classes we are obfuscating are statistically evasive—that is, even given the information that Eve receives over her channel, it is infeasible for (even a computationally unbounded) Eve to find even one input that causes the function to output anything but 0. We formalize this notion now.

Definition 7.1

(Statistically evasive circuit collection with auxiliary input) A statistically evasive circuit collection with auxiliary input $ ({\mathscr {F}}, {\mathscr {G}})$ is defined by

a collection ${\mathscr {F}} = \{ \mathcal C_\lambda \}_{\lambda \in \mathbb {N}}$ of circuits such that each $C \in \mathcal C_\lambda $ maps $\lambda $ input bits to a single output bit and has size ${{\,\mathrm{\textsf{poly}}\,}}(\lambda )$
a collection ${\mathscr {G}}$ of pairs $(D, \textsf{Aux})$ where D is a PPT sampler that takes as input the security parameter $1^\lambda $ and output circuits from $\mathcal C_\lambda $, and $\textsf{Aux}$ is a PPT auxiliary input generator that takes as input the security parameter $1^\lambda $ and a circuit in $\mathcal C_\lambda $ and outputs an auxiliary input

such that for every computationally unbounded oracle machine $\mathcal A^{(\cdot )}$ that is limited to polynomially many queries to the oracle, and for every $(D, \textsf{Aux}) \in {\mathscr {G}}$, there exists a negligible function $\mu $ such that for every $\lambda \in \mathbb {N}$,

$$\begin{aligned}\Pr _{C \leftarrow D(1^\lambda )} \left[ C \left( \mathcal A^{C}\left( 1^\lambda , \textsf{Aux}(1^\lambda , C) \right) \right) = 1 \right] \le \mu (\lambda ).\end{aligned}$$

Obfuscation for evasive functions has been studied in several works, most relevantly for us in [2, 3]. We stress that while there are impossibility results for several definitions of obfuscation, there are no impossibility results known for obfuscation of statistically evasive circuits with auxiliary input. Indeed, this is for good reason: all known impossibilities for obfuscating circuits involve either: (i) providing (computationally hiding) obfuscations as auxiliary input [15], which is ruled out in the statistically evasive case; or (ii) “feeding an obfuscated circuit to itself” [4] which requires a non-evasive circuit family. Beyond merely avoiding impossibilities, both the circuit families that we are obfuscating and the auxiliary inputs we are considering are quite natural, and there are multiple natural avenues for instantiating our obfuscation using previous work.

In particular, we consider essentially Definition 2.3 from [2], which is itself a generalization of the standard average-case VBB definition of obfuscation [4], but extended to consider auxiliary input. The work of [2] gives a construction achieving this definition for evasive functions based on multilinear map candidates [8, 13], that remain secure even in light of all known attacks on multilinear map candidates (when instantiated with sufficiently large security parameters). Below, we also comment that the recent construction of indistinguishability obfuscation from well-studied assumptions [20] also gives a plausible candidate for obfuscating our oracle.

Here, our definition slightly extends the average-case VBB definition given in [2] only in that we consider security with respect to a class of possibly randomized auxiliary input generators as opposed to a single deterministic auxiliary input generator. The proof of security in [2] is oblivious to this change. We also restrict our notion of obfuscation to statistically evasive circuit collections with auxiliary input.

Definition 7.2

(Average-case virtual black box obfuscation for statistically evasive circuit collections with auxiliary input) Consider a statistically evasive circuit collection with auxiliary input, $({\mathscr {F}}, {\mathscr {G}})$ where ${\mathscr {F}} = \{ \mathcal C_\lambda \}_{\lambda \in \mathbb {N}}$ and ${\mathscr {G}}$ are defined as in Definition 7.1. A uniform PPT algorithm $\textsf{Obf}$ is an average-case virtual black box obfuscator for $ ({\mathscr {F}}, {\mathscr {G}})$ if there exist negligible functions $\epsilon $ and $\mu $ such that

Correctness: For all $\lambda \in \mathbb {N}$, every circuit $C \in \mathcal C_{\lambda }$, and every input y to C,
$$\begin{aligned}\Pr \left[ \textsf{Obf}(1^\lambda , C)(y) \ne C(y)\right] \le \epsilon (\lambda )\end{aligned}$$
${\mathscr {G}}$-VBB Security: For all non-uniform polynomial time adversaries $\mathcal A$, there exists a non-uniform polynomial time oracle algorithm $\textsf{Sim}^{(\cdot )}$ such that for all $\lambda \in \mathbb {N}$ and for every $(D, \textsf{Aux}) \in {\mathscr {G}}$,
$$\begin{aligned}&\Big |\Pr _{C \leftarrow D(1^\lambda )}[\mathcal A(1^{\lambda }, \textsf{Obf}(1^{\lambda }, C), \textsf{Aux}(1^\lambda , C)) = 1]\\&\qquad - \Pr _{C \leftarrow D(1^\lambda )}[\textsf{Sim}^{C}(1^{\lambda }, 1^{\left|C\right|}, \textsf{Aux}(1^\lambda , C)) = 1] \Big |\le \mu (\lambda ) \end{aligned}$$

7.2 Fuzzy Point Function Obfuscation for the $\textsf{BSC}$–$\textsf{BEC}$ Case

As a warm-up we consider fuzzy point function obfuscation which suffices when the main channel is a $\textsf{BSC}_p$ channel and Eve’s channel is a $\textsf{BEC}_\epsilon $ channel such that $\epsilon > 2p$. Notably this fuzzy point function solution uses only Hamming distance. Therefore this solution is based on a standard definition of fuzzy point functions.

Notation

Define $\Delta _H(x, y)$ for two binary strings x, y to be the Hamming distance between x and y.

Definition 7.3

(Fuzzy point function (FPF)) A fuzzy point function $\textsf{fuzzy}_{b, x, \delta , n}: \{0, 1\}^n \rightarrow \{0,1\}$ contains a hardcoded bit $b \in \{0, 1\}$ and $x \in \{0, 1\}^n$, and takes as input $y \in \{0, 1\}^n$. If the Hamming distance $\Delta _H(x, y)$ is less than $n\delta $, then $\textsf{fuzzy}_{b, x, \delta , n}$ outputs b. Otherwise, $\textsf{fuzzy}_{b, x, \delta , n}$ outputs 0.

Consider again the wiretap channel $(\textsf{ChB}, \textsf{ChE}) = (\textsf{BSC}_p, \textsf{BEC}_\epsilon )$. Recall that in our ideal obfuscation model construction from Sect. 5, our wiretap coding scheme uses an encoder ${{\,\textrm{Enc}\,}}_{\textsf{BSC}_p}$ that outputs a description of a circuit computing $f_{m, r, \textsf{BSC}_p, n}$ where $n = \lambda $, $m \in \{0,1\}$, and $r \leftarrow \{0,1\}^n$. This function checks if its input ${r_B}$ is in the set

$$\begin{aligned}S_{r, p, n} \triangleq \big \{ r' \in \{0,1\}^n: \forall i, j \in \{0, 1\}, {\textsc {Ratio}_{i \rightarrow j}}(r, r') \le \delta _{i j}p + (1 -\delta _{ij})(1-p) + n^{-\frac{1}{3}}\big \}.\end{aligned}$$

where $\delta _{ij}$ is the Kronecker-delta and outputs m if ${r_B}\in S_{r, p, n}$ and 0 otherwise.^{Footnote 8} This function is not a fuzzy point function; however, we show below that there exists a fuzzy point function that suffices for constructing a secure wiretap coding scheme. This arises from the observation that every string in $S_{r,p,n}$ has no more than $pn + n^{2/3}$ bit flips.

An Alternate Fuzzy Point Function Solution

Definition 7.4

Let $g_{m, r, p, n}: \{0, 1\}^n \rightarrow \{0, 1\}$ be the fuzzy point function which outputs $m \in \{0, 1\}$ if the input is contained in the set

$$\begin{aligned}A_{r, p, n} \triangleq \{ r' \in \mathcal Y^n: \Delta _H(r', r) \le p n + n^{2/3} \}\end{aligned}$$

and 0 otherwise. Note that $g_{m,r,p,n} = \textsf{fuzzy}_{m,r,p+n^{-1/3},n}$

Remark 7.5

($S_{r, p,n} \subsetneq A_{r, p, n}$) Observe that $S_{r, p, n} \subsetneq A_{r, p, n}$. Let $N_0(r)$ be the number of 0’s in r. If $r' \in S_{r, p,n}$, then the number of additional flips over the expected number pn of flips is

$$\begin{aligned}N_0(r) \cdot \left|{\textsc {Ratio}_{0 \rightarrow 1}}(r, r') - p\right| +(n - N_0(r)) \cdot \left|{\textsc {Ratio}_{1 \rightarrow 0}}(r, r') - p\right| \le n^{2/3}.\end{aligned}$$

Thus, the total number of flips is less than $pn + n^{2/3}$. The reverse inclusion does not hold: There exist strings in $A_{r,p, n}$ that are not in $S_{r,p, n}$: for example $r = 0^n$ is in $A_{0^n, p, n}$, but not in $S_{0^n, p, n}$.

Definition 7.6

(FPF function class and sampler) For $p \in [0,\frac{1}{2})$, define a class of FPFs ${\mathscr {P}}_p = \{{\mathscr {P}}_{p,n}\}_{n \in \mathbb {N}}$ by

$$\begin{aligned}{\mathscr {P}}_{p, n} = \{g_{m, r, p, n}\}_{r \in \{0, 1\}^n, m \in \{0,1\}}\end{aligned}$$

For $m \in \{0,1\}$, we define $D_{m,p}$ to be a PPT circuit sampler for ${\mathscr {P}}$ such that

$$\begin{aligned}D_{m,p}(1^n) \text { outputs a uniformly random circuit from } \{g_{m,r,p,n}\}_{r \in \{0,1\}^n}.\end{aligned}$$

Definition 7.7

(FPF wiretap auxiliary input generator) For $p \in [0,\frac{1}{2})$, we define a class of auxiliary input generators for ${\mathscr {P}}_p$ by

$$\begin{aligned}\mathscr {A}_{\textsf{BSC}_{\epsilon> 2p}} \triangleq \left\{ \textsf{Aux}_{\textsf{BEC}_\epsilon } \mid \epsilon > 2p \right\} \end{aligned}$$

where

$$\begin{aligned}\textsf{Aux}_{\textsf{BEC}_\epsilon }(1^n, g_{m, r, p,n}) \text { outputs } \textsf{BEC}_\epsilon (r)\end{aligned}$$

Lemma 7.8

(Wiretap fuzzy point functions are statistically evasive with auxiliary input) For every $p \in [0,\frac{1}{2})$, $({\mathscr {P}}_p, {\mathscr {G}}_{p})$ where ${\mathscr {G}}_{p} = \{D_{0,p}, D_{1,p}\} \times \mathscr {A}_{\textsf{BSC}_{\epsilon > 2p}}$ is a statistically evasive circuit collection with auxiliary input.

Proof

Let $p \in [0, \frac{1}{2})$. Using the definition of statistically evasive circuit collections and the definitions of $({\mathscr {P}}_p, {\mathscr {G}}_{p})$, it suffices to show that for all $n \in \mathbb {N}$, $m \in \{0,1\}$, $\epsilon > 2p$, and for every computationally unbounded oracle machine $\mathcal A^{(\cdot )}$ that is limited to polynomially many queries to the oracle,

$$\begin{aligned}\Pr [g_{m, R, p, n}(\mathcal A^{g_{m, R, p, n}} (1^n, \textsf{BEC}_\epsilon (R))) = 1] \le \textsf{negl}(n)\end{aligned}$$

where $R$ is a uniform random variable over $\{0,1\}^n$. First, we show that no adversary given a single query to $g_{m, R, p, n}$ can cause $g_{m, R, p, n}$ to output 1 with more than negligible probability.$\square $

Claim 7.9

Let $n \in \mathbb {N}$, $p \in [0,\frac{1}{2})$, and $\epsilon > 2p$. Let $R$ be a uniform random variable over $\{0,1\}^n$. For any randomized function $\mathcal A$,

$$\begin{aligned}\Pr _{R, \textsf{BEC}_{\epsilon }, \mathcal A}\left[ \Delta _H(R, \mathcal A(\textsf{BEC}_{\epsilon }(R))) \le n^{2/3} + p n \right] \le \textsf{negl}(n)\end{aligned}$$

Proof

Choose $\eta ', \eta '' > 0$ to be some small enough constants such that $(1 - \eta ') \left( \frac{\epsilon }{2}\right) > (1 + \eta '')\cdot p$. Such constants exist since $\epsilon > 2p$. Let $\eta $ be a constant such that $0< \eta < \eta '$. By a Chernoff bound $\textsf{BEC}_{\epsilon }(R)$ contains with overwhelming probability at least $(1 - \eta ) (\epsilon \cdot n)$ erasures. $\mathcal A$’s best strategy is to guess randomly on the erasures, resulting with overwhelming probability (by Chernoff) an output string with Hamming distance from $R$ at least $(1 - \eta ') \left( \frac{\epsilon \cdot n}{2}\right) $. Then,

$$\begin{aligned}\Pr _{R, \textsf{BEC}_{\epsilon }, \mathcal A}\left[ \Delta _H(R, \mathcal A(\textsf{BEC}_{\epsilon }(R))) > (1 - \eta ') \left( \frac{\epsilon \cdot n}{2}\right) \right] \ge 1 - \textsf{negl}(n).\end{aligned}$$

But since $(1 - \eta ') \left( \frac{\epsilon \cdot n}{2}\right)> (1 + \eta '') (pn) > p n + n^{2/3}$ for sufficiently large n,

$$\begin{aligned}\Pr _{R, \textsf{BEC}_{\epsilon }, \mathcal A}\left[ \Delta _H(R, \mathcal A(\textsf{BEC}_{\epsilon }(R))) \le n^{2/3} + p n \right] \le \textsf{negl}(n).\end{aligned}$$

$\square $

Then, by using the above claim and a similar proof as in Theorem 5.34, we obtain security against an adversary that is given polynomially many queries to $g_{m, r, p, n}$.

Theorem 7.10

Let $p \in [0, \frac{1}{2})$. If there exists an average-case virtual black box with auxiliary input obfuscator $\textsf{Obf}_p$ for $({\mathscr {P}}_p, {\mathscr {G}}_{p})$ where ${\mathscr {G}}_{p} = \{D_{0,p}, D_{1,p}\} \times \mathscr {A}_{\textsf{BSC}_{\epsilon > 2p}}$, then there exists a computationally secure wiretap coding scheme for every $(\textsf{BSC}_p, \textsf{BEC}_\epsilon )$-wiretap channel where $\epsilon > 2p$.

Proof

Let $(\textsf{BSC}_p, \textsf{BEC}_\epsilon )$ be a wiretap channel where $p \in [0,\frac{1}{2})$ and $\epsilon > 2p$. Let $\textsf{Obf}_{p}$ be an average-case virtual black box with auxiliary input obfuscator for $({\mathscr {P}}_p, {\mathscr {G}}_p)$. Let $\textsf{ECC}= (\textsf{ECC}.{{\,\textrm{Enc}\,}}, \textsf{ECC}.{{\,\textrm{Dec}\,}})$ be a sufficiently strong error correcting code for $\textsf{BSC}_p$ such that for all $x \in \{0,1\}^*$,

$$\begin{aligned}\Pr [\textsf{ECC}.{{\,\textrm{Dec}\,}}(1^\lambda , \textsf{BSC}_p(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^\lambda , x))) = x] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$

We define the following wiretap coding scheme $({{\,\textrm{Enc}\,}}_p, {{\,\textrm{Dec}\,}}_p)$. Recall that Alice sends a message $m \in \{0,1\}$ to Bob by sending ${{\,\textrm{Enc}\,}}_p(1^\lambda , m)$ over $\textsf{BSC}_p$ and $\textsf{BEC}_\epsilon $ to Bob and Eve respectively. Bob decodes his channel’s output using ${{\,\textrm{Dec}\,}}_p$.

${{\,\textrm{Enc}\,}}_p$ takes as input a security parameter $1^\lambda $ and a message $m \in \{0, 1\}$, and sets $n = \lambda $. The encoder outputs a uniformly random chosen $r \in \{0,1\}^{n}$, and an error-correcting encoding $\mathcal E= \textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, \textsf{Obf}_{p}(1^n, g_{m, r, p, n}))$ of the obfuscation of the circuit description of $g_{m, r, p, n}$ from Definition 7.4.
${{\,\textrm{Dec}\,}}_p$ takes as input a security parameter $1^\lambda $, the noisy encoding $\widehat{\mathcal E} = \textsf{ChB}(\mathcal E)$, and a string ${r_B}= \textsf{ChB}(r)$. The decoder first uses the error-correcting code to decode $\widehat{\mathcal E}$ to $\textsf{Obf}_{p}(1^n, g_{m, r, p, n})$ and then outputs $(\textsf{Obf}_{p}(1^n, g_{m,r,p,n}))({r_B})$.

Observe that $\Pi _p = ({{\,\textrm{Enc}\,}}_p, {{\,\textrm{Dec}\,}}_p)$ above is essentially the same as the ideal oracle model construction $\Pi _{\textsf{BSC}_p} = ({{\,\textrm{Enc}\,}}_{\textsf{BSC}_p}, {{\,\textrm{Dec}\,}}_{\textsf{BSC}_p})$ from Sect. 5 except that we have replaced the oracle for $f_{m, r, \textsf{BSC}_p, n}$ with an error correcting encoding of the obfuscation of $g_{m, r, p, n}$.

For correctness, first observe that by correctness of the error correcting code and the obfuscation, the decoder outputs a value equal to $g_{m, r, p,n}({r_B}) = g_{m, r, p, n}(\textsf{ChB}(r))$ except with negligible probability. By Remark 7.5, for any r and m, the set of strings $S_{r, p, n}$ on which the original function $f_{m, r, \textsf{ChB}, n}$ from the ideal obfuscation model construction outputs bit m is a subset of the set of strings $A_{r, p, n}$ on which $g_{m, r, p, n}$ outputs the bit m. Therefore,

$$\begin{aligned}\Pr _{R, \textsf{ChB}}[f_{m, R, \textsf{BSC}_p, n}(\textsf{ChB}(R)) = m] \le \Pr _{R, \textsf{ChB}}[g_{m, R, p, n}(\textsf{ChB}(R)) = m]\end{aligned}$$

Then we note by Theorem 5.8 that

$$\begin{aligned}\Pr _{R, \textsf{ChB}}[f_{m, R, \textsf{BSC}_p, n}(\textsf{ChB}(R)) = m] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$

Therefore, for all $m \in \{0,1\}$,

$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}_p(1^\lambda , \textsf{ChB}({{\,\textrm{Enc}\,}}_p(1^\lambda , m))) = m] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$

For semantic security, the proof is nearly identical to the proof we will later show for generalized fuzzy point functions in Theorem 7.17, so we omit it here. $\square $

7.3 Generalized Fuzzy Point Function Obfuscation

In general wiretap settings, a fuzzy point function obfuscation does not suffice to produce secure wiretap coding schemes. Thus, we define a generalization of fuzzy point functions that does suffice.

Definition 7.11

(Generalized fuzzy point function (GFPF)) Let $\mathcal X$ and $\mathcal Y$ be finite alphabets. For a value $n \in \mathbb {N}$, a message $m \in \{0, 1\}$, a string $r \in \mathcal X^n$, a parameter $\delta \in [0,1]$, and a stochastic matrix $P = [p(y \mid x)]_{x, y \in \mathcal X\times \mathcal Y}$, the generalized fuzzy point function $f_{m,r,P,n,\delta }:\mathcal Y^n \rightarrow \{0, 1\}$ is defined as

As we will only be concerned with the case where $\delta = n^{-1/3}$ and P is some stochastic matrix for a channel $\textsf{ChB}$, we define the following:

Definition 7.12

Let $\textsf{ChB}$ be a channel with stochastic matrix ${P_B}$. We define

$$\begin{aligned}f_{m, r, \textsf{ChB}, n} = f_{m, r, {P_B}, n, n^{-1/3}}.\end{aligned}$$

Remark 7.13

The definition above is identical to the definition for the function with the same notation used in Sect. 5.^{Footnote 9}

Definition 7.14

(GFPF function class and sampler) For a channel $\textsf{ChB}$, we define a class of GFPFs ${\mathscr {F}}_\textsf{ChB}= \{{\mathscr {F}}_{\textsf{ChB}, n}\}_{n \in \mathbb {N}}$ by

$$\begin{aligned}{\mathscr {F}}_{\textsf{ChB}, n} = \{f_{m, r, \textsf{ChB}, n}\}_{r \in \mathcal X^n, m \in \{0, 1\}}.\end{aligned}$$

For $m \in \{0, 1\}$, we define $D_{m,\textsf{ChB}}$ to be a PPT circuit sampler such that

$$\begin{aligned}D_{m,\textsf{ChB}}(1^n) \text { outputs a uniformly random circuit from } \{f_{m, r, \textsf{ChB}, n}\}_{r \in \mathcal X^n}.\end{aligned}$$

Definition 7.15

(GFPF wiretap auxiliary input generator) For a channel $\textsf{ChB}: \mathcal X\rightarrow \mathcal Y$, we define a class of auxiliary input generators

$$\begin{aligned}\mathscr {A}_{\textsf{ChB}} = \left\{ \textsf{Aux}_{\textsf{ChE}} \mid \text {channel } \textsf{ChE}:\mathcal X\rightarrow \mathcal Z\text { such that }\textsf{ChB}\text { is not a degradation of} \textsf{ChE}\right\} \end{aligned}$$

where

$$\begin{aligned}\textsf{Aux}_{\textsf{ChE}}(1^n, f_{m, r, \textsf{ChE},n}) \text { outputs } \textsf{ChE}(r)\end{aligned}$$

Lemma 7.16

(Wiretap generalized fuzzy point functions are statistically evasive with auxiliary input) For every channel $\textsf{ChB}$, $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_{\textsf{ChB}})$ where ${\mathscr {G}}_{\textsf{ChB}} = \{D_{0,\textsf{ChB}}, D_{1,\textsf{ChB}}\} \times \mathscr {A}_{\textsf{ChB}}$ is a statistically evasive circuit collection with auxiliary input.

Proof

Let $\textsf{ChB}$ be any channel, and let $\mathcal X$ be the input domain of $\textsf{ChB}$. Using the definition of statistically evasive circuit collections and the definitions of $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_{\textsf{ChB}})$, it suffices to show that for all $n \in \mathbb {N}$, $m \in \{0,1\}$, channels $\textsf{ChE}$ such that $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$, and for every computationally unbounded oracle machine $\mathcal A^{(\cdot )}$ that is limited to polynomially many queries to the oracle,

$$\begin{aligned}\Pr [f_{m, R, \textsf{ChB}, n}(\mathcal A^{f_{m, R, \textsf{ChB}, n}} (1^n, \textsf{ChE}(R))) = 1] \le \textsf{negl}(n)\end{aligned}$$

where $R$ is a uniform random variable over $\mathcal X^n$. The proof then follows directly from Theorem 5.34. $\square $

Theorem 7.17

Let $\textsf{ChB}$ be a channel. If there exists an average-case virtual black box with auxiliary input obfuscator $\textsf{Obf}_\textsf{ChB}$ for $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_\textsf{ChB})$ where ${\mathscr {G}}_{\textsf{ChB}} = \{D_{0,\textsf{ChB}}, D_{1,\textsf{ChB}}\} \times \mathscr {A}_{\textsf{ChB}}$, then there exists a computationally secure wiretap coding scheme for every $(\textsf{ChB}, \textsf{ChE})$-wiretap channel where $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$.

Proof

Let $(\textsf{ChB}, \textsf{ChE})$ be a wiretap channel where $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$. Let $\textsf{Obf}_\textsf{ChB}$ be an average-case virtual black box with auxiliary input obfuscator for $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_\textsf{ChB})$. Let $\textsf{ECC}= (\textsf{ECC}.{{\,\textrm{Enc}\,}}, \textsf{ECC}.{{\,\textrm{Dec}\,}})$ be a sufficiently strong error correcting code for $\textsf{ChB}$ such that for all $x \in \{0,1\}^*$,

$$\begin{aligned}\Pr [\textsf{ECC}.{{\,\textrm{Dec}\,}}(1^\lambda , \textsf{ChB}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^\lambda , x))) = x] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$

We define the following wiretap coding scheme dependent only on $\textsf{ChB}$. Recall that Alice sends a message $m \in \{0,1\}$ to Bob by sending ${{\,\textrm{Enc}\,}}(1^\lambda , m)$ over $\textsf{ChB}$ and $\textsf{ChE}$ to Bob and Eve respectively. Bob decodes his channel’s output using ${{\,\textrm{Dec}\,}}$.

${{\,\textrm{Enc}\,}}$ takes as input a security parameter $1^\lambda $ and a message $m \in \{0, 1\}$, and sets $n = \lambda $. The encoder outputs a uniformly random $r \in \mathcal X^{n}$, and an error-correcting encoding $\mathcal E= \textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, \textsf{Obf}_\textsf{ChB}(1^n, f_{m, r, \textsf{ChB}, n}))$ of the obfuscation of the circuit description of $f_{m, r, \textsf{ChB}, n}$ from Definition 7.12.
${{\,\textrm{Dec}\,}}$ takes as input a security parameter $1^\lambda $, the noisy encoding $\widehat{\mathcal E} = \textsf{ChB}(\mathcal E)$, and a string ${r_B}= \textsf{ChB}(r)$. The decoder first uses the error-correcting code to decode $\widehat{\mathcal E}$ to $\textsf{Obf}_\textsf{ChB}(1^n, f_{m, r, \textsf{ChB}, n})$ and then outputs $(\textsf{Obf}_\textsf{ChB}(1^n, f_{m, r, \textsf{ChB}, n}))({r_B})$.

Observe that $\Pi = ({{\,\textrm{Enc}\,}}, {{\,\textrm{Dec}\,}})$ above is essentially the same as the ideal oracle model construction $\Pi _{\textsf{ChB}} = ({{\,\textrm{Enc}\,}}_{\textsf{ChB}}, {{\,\textrm{Dec}\,}}_{\textsf{ChB}})$ from Sect. 5 except that we have replaced the oracle for $f_{m, r, \textsf{ChB}, n}$ with an error correcting encoding of the obfuscation of $f_{m, r, \textsf{ChB}, n}$.

For correctness, first observe that by correctness of the error correcting code and the obfuscation, the decoder outputs a value equal to $f_{m, r, \textsf{ChB}, n}({r_B}) = f_{m, r, \textsf{ChB}, n}(\textsf{ChB}(r))$ except with negligible probability. Thus, with high probability, ${{\,\textrm{Dec}\,}}$ outputs the same value as ${{\,\textrm{Dec}\,}}_\textsf{ChB}$, so correctness follows by Theorem 5.8.

Now we analyze the semantic security of the encoding scheme. Recall semantic security requires:

$$\begin{aligned}\Pr [\mathcal A(1^\lambda , \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , b))) = b] \le \frac{1}{2} + \textsf{negl}(\lambda ).\end{aligned}$$

Note that this is equivalent to requiring

$$\begin{aligned}\left|\Pr [\mathcal A(1^\lambda , \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , 0))) = 1] - \Pr [\mathcal A(1^\lambda , \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , 1))) = 1]\right| \le \textsf{negl}(\lambda ).\end{aligned}$$

By construction of the encoder above, the above statement is equivalent to

$$\begin{aligned}&\Big |\Pr _{r \leftarrow R}[\mathcal A(1^n, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, \textsf{Obf}_\textsf{ChB}(1^n, f_{0, r, \textsf{ChB}, n}))), \textsf{ChE}(r)) = 1]\\&\qquad - \Pr _{r \leftarrow R}[\mathcal A(1^n, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, \textsf{Obf}_\textsf{ChB}(1^n, f_{1, r, \textsf{ChB}, n}))), \textsf{ChE}(r)) = 1] \Big |\le \textsf{negl}(n) \end{aligned}$$

where $R$ is the uniform distribution on $\mathcal X^n$. A strengthening of $\mathcal A$ is to assume $\mathcal A$ correctly decodes the encoded obfuscated circuit description. Therefore, rewriting the above using the notation from Definition 7.14 and Definition 7.15, it suffices to prove

Now we aim to show $(\star )$ through a series of inequalities.

First, the security definition of average-case virtual black box with auxiliary input obfuscation in Definition 7.2 yields a non-uniform polynomial time oracle simulator machine $\textsf{Sim}$ such that,

$$\begin{aligned}&\Big |\Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^n)}[\mathcal A(1^n, \textsf{Obf}_\textsf{ChB}(1^n, C_0), \textsf{Aux}_\textsf{ChE}(1^n, C_0)) = 1]\nonumber \\&\qquad - \Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^n)}[\textsf{Sim}^{C_0}(1^n, 1^{\left|C_0\right|}, \textsf{Aux}(1^n, C_0)) = 1] \Big |\le \textsf{negl}(n) \end{aligned}$$

(1)

$$\begin{aligned}&\Big |\Pr _{C_1 \leftarrow D_{1, \textsf{ChB}}(1^n)}[\mathcal A(1^n, \textsf{Obf}_\textsf{ChB}(1^n, C_1), \textsf{Aux}_\textsf{ChE}(1^n, C_1)) = 1]\nonumber \\&\qquad - \Pr _{C \leftarrow D_{1, \textsf{ChB}}(1^n)}[\textsf{Sim}^{C_1}(1^n, 1^{\left|C_1\right|}, \textsf{Aux}(1^n, C_1)) = 1] \Big |\le \textsf{negl}(n) \end{aligned}$$

(2)

Next, we note by Lemma 7.16, that $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_\textsf{ChB})$ is statistically evasive. Therefore, with high probability, since $\textsf{Sim}^{(\cdot )}$ is polynomial time, $\textsf{Sim}^{C_0}(1^n, 1^{\left|C_0\right|}, \textsf{Aux}(1^n, C_0))$ and $\textsf{Sim}^{C_1}(1^n, 1^{\left|C_0\right|}, \textsf{Aux}(1^n, C_0))$ both only ever receive 0’s from their oracles, so

$$\begin{aligned}&\Big |\Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^n)}[\textsf{Sim}^{C_0}(1^n, 1^{\left|C_0\right|}, \textsf{Aux}(1^n, C_0)) = 1 ]\nonumber \\&\qquad - \Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^n), C_1 \leftarrow D_{1, \textsf{ChB}}(1^n)}[\textsf{Sim}^{C_1}(1^n, 1^{\left|C_0\right|}, \textsf{Aux}(1^n, C_0))) = 1] \Big |\le \textsf{negl}(n). \end{aligned}$$

(3)

Then, observe that since the auxiliary input generator is only dependent on $r$, and $D_{0, \textsf{ChB}}$ and $D_{1, \textsf{ChB}}$ output circuits of the same size, then the resulting distribution of

$$\begin{aligned}(1^n, 1^{|C_0|}, \textsf{Aux}(1^n, C_0))\end{aligned}$$

when $C_0 \leftarrow D_{0, \textsf{ChB}}$ is identical to that of

$$\begin{aligned}(1^n, 1^{|C_1|}, \textsf{Aux}(1^n, C_1))\end{aligned}$$

when $C_1 \leftarrow D_{1, \textsf{ChB}}$. Therefore,

$$\begin{aligned}&\Big |\Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^n), C_1 \leftarrow D_{1, \textsf{ChB}}(1^n)}[\textsf{Sim}^{C_1}(1^n, 1^{\left|C_0\right|}, \textsf{Aux}(1^n, C_0))) = 1] \nonumber \\&\qquad - \Pr _{C_1' \leftarrow D_{1, \textsf{ChB}}(1^n), C_1 \leftarrow D_{1, \textsf{ChB}}(1^n)}[\textsf{Sim}^{C_1}(1^n, 1^{\left|C_1'\right|}, \textsf{Aux}(1^n, C_1'))) = 1] \Big |\le \textsf{negl}(n). \end{aligned}$$

(4)

Then, again since $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_\textsf{ChB})$ is evasive,

$$\begin{aligned}&\Big |\Pr _{C_1' \leftarrow D_{1, \textsf{ChB}}(1^n), C_1 \leftarrow D_{1, \textsf{ChB}}(1^n)}[\textsf{Sim}^{C_1}(1^n, 1^{\left|C_1'\right|}, \textsf{Aux}(1^n, C_1'))) = 1] \nonumber \\&\qquad - \Pr _{C_1 \leftarrow D_{1, \textsf{ChB}}(1^n)}[\textsf{Sim}^{C_1}(1^n, 1^{\left|C_1\right|}, \textsf{Aux}(1^n, C_1))) = 1]\Big |\le \textsf{negl}(n). \end{aligned}$$

(5)

Applying the triangle inequality on (1), (2), (3), (4), (5) yields $(\star )$. As mentioned earlier, $(\star )$ suffices to show semantic security of the scheme. $\square $

7.4 Construction from $i\mathcal O$

Finally, we remark that if there exists a uniformly bounded average case virtual black box with auxiliary input obfuscator, then $i\mathcal O$ (indistinguishability obfuscation) also implies secure wiretap coding schemes for $(\textsf{ChB}, \textsf{ChE})$ wiretap channels where $\textsf{ChB}$ is not a degradation of $\textsf{ChE}$.

Definition 7.18

A uniform PPT algorithm $\textsf{Obf}$ for a collection $\{ {\mathscr {F}}_\lambda \}_{\lambda \in \mathbb {N}}$ of circuits is said to be be uniformly bounded if it satisfies the following property:

Polynomially Bounded Obfuscation Circuit Size There exists a polynomial $p(\lambda )$ such that for all $\lambda \in \mathbb {N}$ and for all $C \in {\mathscr {F}}_\lambda $, we have $\left|\textsf{Obf}(1^\lambda , C)\right| = p(\left|C\right|)$ where $\left|C\right|$ is the circuit size of C.

Definition 7.19

(Indistinguishability obfuscation ($i\mathcal O$) for circuits, imported from [20]) A uniform PPT algorithm $i\mathcal O$ is called a $(T, \gamma )$-secure indistinguishability obfuscator for polynomial-sized circuits if the following holds:

Completeness: For every $\lambda \in \mathbb {N}$, every circuit C with input length n, every input $x \in \{0, 1\}^n$ we have that
$$\begin{aligned}\Pr \left[ C'(x) = C(x): C' \xleftarrow {} i\mathcal O(1^\lambda , C)\right] = 1\end{aligned}$$
$(T, \gamma )$-Indistinguishability: For every two ensembles $\{C_{0, \lambda }\}, \{C_{1, \lambda }\}$ of polynomial-sized circuits that have the same size, input length, and output length, and are functionally equivalent, that is, $\forall \lambda $, $C_{0, \lambda }(x) = C_{1, \lambda }(x)$ for every input x, the following distributions are $(T, \gamma )$-indistinguishable.
$$\begin{aligned} \{i\mathcal O(1^\lambda , C_{0, \lambda })\} \qquad \{i\mathcal O(1^{\lambda }, C_{1, \lambda })\} \end{aligned}$$
meaning that for all adversaries running in time $T\cdot \textsf{poly}(\lambda )$ we have that for all sufficiently large $\lambda $,
$$\begin{aligned}\left|\Pr \left[ \mathcal A(1^\lambda ,i\mathcal O(1^\lambda , C_{0, \lambda })) = 1\right] - \Pr \left[ \mathcal A(1^\lambda ,i\mathcal O(1^\lambda , C_{1, \lambda })) = 1 \right] \right| \le \gamma (\lambda ). \end{aligned}$$

Following the discussion on $i\mathcal O$ in [1], we note that $i\mathcal O$ is a "best-possible" obfuscation [17]. More specifically, if there exists some instantiation of the ideal obfuscation that gives a secure computational wiretap coding scheme, then replacing that instantiation with $i\mathcal O$ should preserve the security properties. However, in our setting, the adversary is given additional auxiliary information that may depend on the obfuscated circuit. Despite this auxiliary information, we formally show below that $i\mathcal O$ still behaves as a best possible obfuscation.

Lemma 7.20

Let $\textsf{ChB}$ be a channel and $\lambda $ be a security parameter. If there exists a uniformly bounded average-case virtual black box with auxiliary input obfuscator $\textsf{Obf}_\textsf{ChB}$ with perfect correctness for $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_\textsf{ChB})$ where ${\mathscr {G}}_{\textsf{ChB}} = \{D_{0,\textsf{ChB}}, D_{1,\textsf{ChB}}\} \times \mathscr {A}_{\textsf{ChB}}$, then $(\lambda , \mu )$-secure $i\mathcal O$ for a negligible $\mu $ implies a computationally secure wiretap coding scheme for any $(\textsf{ChB}, \textsf{ChE})$-wiretap channel where $\textsf{ChB}$ is not a degraded version of $\textsf{ChE}$.

Proof

Let $(\textsf{ChB}, \textsf{ChE})$ be a wiretap channel where $\textsf{ChB}$ is not a degration of $\textsf{ChE}$. Let $\textsf{Obf}_\textsf{ChB}$ be a uniformly bounded average-case virtual black box with auxiliary input obfuscator with perfect correctness for $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_\textsf{ChB})$. Let p be the polynomial which bounds the obfuscation circuit size (i.e. $|\textsf{Obf}(1^\lambda , C)| = p(|C|)$). Let $\textsf{Pad}_p$ be a function that pads a circuit $C \in \mathscr {F}_{\textsf{ChB}}$ to a functionally identical circuit of size p(|C|).

Our computationally secure wiretap coding scheme construction is identical to the construction in Theorem 7.17 except we replace $\textsf{Obf}(1^n, f_{m,r,\textsf{ChB},n})$ with $i\mathcal O(1^n, \textsf{Pad}_p(f_{m,r,\textsf{ChB},n}))$. Correctness follows in the same way as in Theorem 7.17 by correctness of $i\mathcal O$.

Analogously to the proof of Theorem 7.17, to show semantic security, it suffices to show that for all non-uniform polynomial time adversaries $\mathcal A$,

First we show the following claim:

Claim 7.21

$$\begin{aligned}&\Big |\Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^\lambda )} \left[ \mathcal A(1^\lambda , i\mathcal O(1^\lambda ,\textsf{Pad}_p(C_0)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_0)) = 1 \right] \\&\qquad - \Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^\lambda )} \left[ \mathcal A(1^\lambda , i\mathcal O(1^\lambda , \textsf{Obf}_\textsf{ChB}(1^\lambda , C_0)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_0)) = 1 \right] \Big |\le \mu (\lambda ). \end{aligned}$$

(1)

Proof

For the sake of contradiction, suppose not. Then there exists an adversary $\mathcal A^*$ such that

$$\begin{aligned}&\Big |\Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^\lambda )} \left[ \mathcal A^*(1^\lambda , i\mathcal O(1^\lambda ,\textsf{Pad}_p(C_0)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_0)) = 1 \right] \\&\qquad - \Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^\lambda )} \left[ \mathcal A^*(1^\lambda , i\mathcal O(1^\lambda , \textsf{Obf}_\textsf{ChB}(1^\lambda , C_0)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_0)) = 1 \right] \Big |> \mu (\lambda ). \end{aligned}$$

Let $(C^*, r^*)$ be the circuit $C^*$ from $D_{0, \textsf{ChB}}$ and the randomness $r^*$ for the auxiliary input generator that maximizes $\mathcal A^*$’s distinguishing advantage. Now, we construct a distinguisher $\mathcal A'$ that breaks the $(\lambda , \mu )$-indistinguishability of $i\mathcal O$ on circuits $\textsf{Pad}_p(C^*)$ and $\textsf{Obf}_\textsf{ChB}(C^*)$. $\mathcal A'$ takes as input Q which is either $i\mathcal O(1^\lambda , \textsf{Pad}_p(C^*))$ or $i\mathcal O(1^\lambda , \textsf{Obf}_\textsf{ChB}(C^*))$ as well as non-uniform advice $r^*$ and circuit descriptions of $\mathcal A^*$ and $C^*$, and outputs either 0 or 1.

Then, $\mathcal A'$ on input $i\mathcal O(1^\lambda , \textsf{Pad}_p(C^*))$ outputs $\mathcal A^*(1^\lambda , i\mathcal O(1^\lambda ,\textsf{Pad}_p(C^*)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C^*; r^*))$ and on input $i\mathcal O(1^\lambda , \textsf{Obf}_\textsf{ChB}(C^*))$ outputs $\mathcal A^*(1^\lambda , i\mathcal O(1^\lambda , \textsf{Obf}_\textsf{ChB}(1^\lambda , C^*)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C^*; r^*))$. But then since $\mathcal A^*$ has greater than $\mu (\lambda )$ advantage in distinguishing the two, then $\mathcal A'$ has greater than $\mu (\lambda )$ advantage in distinguishing the obfuscations, contradicting $(\lambda , \mu )$-indistinguishability. $\square $

The same exact argument gives

$$\begin{aligned}&\Big |\Pr _{C_1 \leftarrow D_{1, \textsf{ChB}}(1^\lambda )} \left[ \mathcal A(1^\lambda , i\mathcal O(1^\lambda ,\textsf{Pad}_p(C_1)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_1)) = 1 \right] \\&\qquad - \Pr _{C_1 \leftarrow D_{1, \textsf{ChB}}(1^\lambda )} \left[ \mathcal A(1^\lambda , i\mathcal O(1^\lambda , \textsf{Obf}_\textsf{ChB}(1^\lambda , C_1)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_1)) = 1 \right] \Big |\le \mu (\lambda ). \end{aligned}$$

(2)

Then, as shown in ($\star $) of the proof of Theorem 7.17, by security of $\textsf{Obf}_\textsf{ChB}$ and since $({\mathscr {F}}_\textsf{ChB}, {\mathscr {G}}_\textsf{ChB})$ is statistically evasive,

$$\begin{aligned}&\Big |\Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^\lambda )}[\mathcal A(1^\lambda , \textsf{Obf}_\textsf{ChB}(1^\lambda , C_0), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_0)) = 1]\\&\qquad - \Pr _{C_1 \leftarrow D_{1, \textsf{ChB}}(1^\lambda )}[\mathcal A(1^\lambda , \textsf{Obf}_\textsf{ChB}(1^\lambda , C_1), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_1)) = 1] \Big |\le \textsf{negl}(n). \end{aligned}$$

which implies

$$\begin{aligned}&\Big |\Pr _{C_0 \leftarrow D_{0, \textsf{ChB}}(1^\lambda )} \left[ \mathcal A(1^\lambda , i\mathcal O(1^\lambda , \textsf{Obf}_\textsf{ChB}(1^\lambda , C_0)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_0)) = 1 \right] \\&\qquad - \Pr _{C_1 \leftarrow D_{1, \textsf{ChB}}(1^\lambda )} \left[ \mathcal A(1^\lambda , i\mathcal O(1^\lambda ,\textsf{Obf}_\textsf{ChB}(1^\lambda , C_1)), \textsf{Aux}_\textsf{ChE}(1^\lambda , C_1)) = 1 \right] \Big |\le \mu (\lambda ). \end{aligned}$$

(3)

Applying the triangle inequality on (1), (2), (3) gives $(\star )$.

Notes

In the computational setting, any wiretap coding scheme for 1-bit messages can be bootstrapped into one that encodes long messages with rate achieving the capacity of $\textsf{ChB}$ via the use of a standard hybrid encryption technique (see Remark 4.18 for more details).
In the computational setting, if we allow interaction, we can solve the wiretap problem even more easily using standard key agreement.
A slight caveat is that this holds only when r contains sufficiently many of each $x \in \mathcal X$, but this occurs with overwhelming probability over the choice of r.
Our security definition corresponds to requiring the distinguishing advantage $\textsf{Adv}^{ds}$ of [5] to be negligible. [5] define a separate notion for semantic security, but prove that the two definitions are equivalent.
As the growth rate of the correctness and security functions is not specified, correctness would be satisfied even if the probability of correct decryption is $1 - \frac{1}{\log (n)}$ and security would be satisfied even if $\lim _{n \rightarrow \infty } I(M_n; \textsf{ChE}({{\,\textrm{Enc}\,}}_n(M_n))) = \log (n)$. Even when using the strong secrecy definition of [24, 25], security is defined only with respect to a uniformly random message distribution.
Our proof technique can be viewed as security amplification of weak key agreement. Unlike the work of [18] whose amplification technique is interactive, our amplification is non-interactive. However, [18] achieves better parameters and also considers the computational setting.
Note that since we have assumed $n, p_i > 0$ and $np_i \in \mathbb {N}\cup \{0\}$, then $np_i = \Omega (1)$. If $np_i$ is a constant, then Stirling’s approximation still holds up to a constant since in this case $(np_i)! = \Theta (\sqrt{2\pi n p_i}\left( \frac{np_i}{e}\right) ^{np_i}) = \Theta (1)$
Here we use Remark 5.5 to assume $f_{m, r, \textsf{BSC}_p, n}$ has binary output.
Here we use Remark 5.5 to assume $f_{m, r, \textsf{ChB}, n}$ has binary output.
This only holds for n such that $\epsilon _n < \frac{1}{4}$. For n such that $\epsilon _n \ge \frac{1}{4}$, we can simply let $\epsilon _n'$ be any large enough value to satisfy the [10] correctness and security requirements for some corresponding message space $\mathcal M_n'$. This suffices since $\epsilon _n \rightarrow 0$ implies that $\epsilon _n < \frac{1}{4}$ for large n, so the requirements hold in the limit.
A CK rate-0 wiretap coding family is ill-posed for security: A zero rate encoding satisfies $\lim _{n \rightarrow \infty } \frac{\log \left|\mathcal M_n\right|}{n} = 0$ so even if Eve learns all information, meaning $I(M_n; Y) = H(M_n) = \log \left|\mathcal M_n\right|$, Eve would satisfy the security definition as $\lim _{n \rightarrow \infty } \frac{1}{n} I(M_n; Y) = 0$.

References

S. Agrawal, Y. Ishai, E. Kushilevitz, V. Narayanan, M. Prabhakaran, V. Prabhakaran, A. Rosen, Secure computation from one-way noisy communication, or: anti-correlation via anti-concentration, in CRYPTO (2021).
S. Badrinarayanan, E. Miles, A. Sahai, M. Zhandry, Post-zeroizing obfuscation: new mathematical tools, and the case of evasive circuits, in M. Fischlin, J.-S. Coron, editors, Advances in Cryptology—EUROCRYPT 2016, Part II volume 9666 of Lecture Notes in Computer Science, Vienna, Austria, May 8–12, 2016 (Springer, Heidelberg, 2016), pp. 764–791
Google Scholar
B. Barak, N. Bitansky, R. Canetti, Y.T. Kalai, O. Paneth, A. Sahai, Obfuscation for evasive functions, in Theory of Cryptography Conference (Springer, 2014), pp. 26–51
B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K. Yang, On the (im)possibility of obfuscating programs, in J. Kilian, editor, Advances in Cryptology—CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August 19–23, 2001 (Springer, Heidelberg, 2001), pp. 1–18
Chapter Google Scholar
M. Bellare, S. Tessaro, A. Vardy, Semantic security for the wiretap channel, in R. Safavi-Naini, R. Canetti, editors, Advances in Cryptology—CRYPTO 2012—32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science (Springer, 2012), pp. 294–311
M. Blum, S. Micali, How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13(4), 850–864 (1984)
Article MathSciNet Google Scholar
R. Canetti, B. Fuller, O. Paneth, L. Reyzin, A.D. Smith, Reusable fuzzy extractors for low-entropy distributions. J. Cryptol. 34(1), 2 (2021). Earlier version in Eurcrypt 2016
J.-S. Coron, T. Lepoint, M. Tibouchi, Practical multilinear maps over the integers, in R. Canetti, J.A. Garay, editors, Advances in Cryptology—CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August 18–22, 2013 (Springer, Heidelberg, 2013), pp. 476–493
Chapter Google Scholar
T. Cover, Broadcast channels. IEEE Trans. Inf. Theory 18(1), 2–14 (1972)
Article MathSciNet Google Scholar
I. Csiszár, J. Korner, Broadcast channels with confidential messages. IEEE Trans. Inf. Theory 24(3), 339–348 (1978)
Article MathSciNet Google Scholar
Y. Dodis, R. Ostrovsky, L. Reyzin, A.D. Smith, Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)
Article MathSciNet Google Scholar
B. Fuller, X. Meng, L. Reyzin, Computational fuzzy extractors. Inf. Comput. 275, 104602 (2020). Earlier version in Asiacrypt 2013
S. Garg, C. Gentry, S. Halevi, Candidate multilinear maps from ideal lattices, in T. Johansson, P.Q. Nguyen, editors, Advances in Cryptology—EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, Athens, Greece, May 26–30, 2013 (Springer, Heidelberg, 2013), pp. 1–17
Chapter Google Scholar
O. Goldreich, S. Micali, A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in A. Aho, editor, 19th Annual ACM Symposium on Theory of Computing, New York City, NY, USA, May 25–27, 1987 (ACM Press, New York, 1987), pp. 218–229
Google Scholar
S. Goldwasser, Y.T. Kalai, On the impossibility of obfuscation with auxiliary input, in 46th Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, USA, October 23–25, 2005 (IEEE Computer Society Press, 2005), pp. 553–562
S. Goldwasser, S. Micali, Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)
Article MathSciNet Google Scholar
S. Goldwasser, G.N. Rothblum, On best-possible obfuscation, in S.P. Vadhan, editor, TCC 2007: 4th Theory of Cryptography Conference, volume 4392 of Lecture Notes in Computer Science, Amsterdam, The Netherlands, February 21–24, 2007 (Springer, Heidelberg, 2007), pp. 194–213
Google Scholar
T. Holenstein, Key agreement from weak bit agreement, in H.N. Gabow, R. Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22–24, 2005 (ACM, 2005), pp. 664–673
Y. Ishai, A. Korb, P. Lou, A. Sahai, Beyond the csiszár–körner bound: best-possible wiretap coding via obfuscation, in Crypto 2022 (2022)
A. Jain, H. Lin, A. Sahai, Indistinguishability obfuscation from well-founded assumptions, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021), pp. 60–73
A. Juels, M. Sudan, A fuzzy vault scheme. Des. Codes Cryptogr. 38(2), 237–257 (2006)
Article MathSciNet Google Scholar
A. Juels, M. Wattenberg, A fuzzy commitment scheme, in J. Motiwalla, G. Tsudik, editors, ACM CCS 99: 6th Conference on Computer and Communications Security, Singapore, November 1–4, 1999 (ACM Press, 1999), pp. 28–36
Chapter Google Scholar
Y. Liang, G. Kramer, H.V. Poor, Compound wiretap channels. EURASIP J. Wirel. Commun. Netw. 2009, 1–12 (2009)
Article Google Scholar
U.M. Maurer, The strong secret key rate of discrete random triples, in Communications and Cryptography (Springer, 1994), pp. 271–285
U.M. Maurer, S. Wolf, Information-theoretic key agreement: from weak to strong secrecy for free, in B. Preneel, editor, Advances in Cryptology—EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, Bruges, Belgium, May 14–18, 2000 (Springer, Heidelberg, 2000), pp. 351–368
Chapter Google Scholar
U.M. Maurer, Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39(3), 733–742 (1993)
Article MathSciNet Google Scholar
C. Nair, Capacity regions of two new classes of two-receiver broadcast channels. IEEE Trans. Inf. Theory 56(9), 4207–4214 (2010)
Article MathSciNet Google Scholar
H.V. Poor, R.F. Schaefer, Wireless physical layer security. Proc. Natl. Acad. Sci. 114(1), 19–26 (2017)
Article ADS CAS PubMed Google Scholar
M.T.C.A.J. Thomas, A.T. Joy, Elements of Information Theory (Wiley-Interscience, 2006)
A.D. Wyner, The wire-tap channel. Bell Syst. Tech. J. 54(8), 1355–1387 (1975)
Article MathSciNet Google Scholar
A.C. Yao, Theory and application of trapdoor functions, in 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) (IEEE, 1982), pp. 80–91

Download references

Acknowledgements

Y. Ishai was supported in part by ERC Project NTSC (742754), BSF grant 2018393, and ISF grant 2774/20. This research was supported in part from a Simons Investigator Award, DARPA SIEVE award, NTT Research, NSF Frontier Award 1413955, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, and an Okawa Foundation Research Grant. This material is based upon work supported by the Defense Advanced Research Projects Agency through Award HR00112020024. We would also like to thank Mark Zhandry for his useful comments.

Author information

Authors and Affiliations

Technion, Haifa, Israel
Yuval Ishai
UCLA, Los Angeles, USA
Alexis Korb, Paul Lou & Amit Sahai

Authors

Yuval Ishai
View author publications
You can also search for this author in PubMed Google Scholar
Alexis Korb
View author publications
You can also search for this author in PubMed Google Scholar
Paul Lou
View author publications
You can also search for this author in PubMed Google Scholar
Amit Sahai
View author publications
You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexis Korb.

Additional information

Communicated by Serge Fehr.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This is the full version of [19].

This article was reviewed by Shun Watanabe and an anonymous reviewer.

Appendices

CK78 [10] and MW00 [25] Definitions

In this section, we connect the definitions of wiretap channels and secrecy capacity used in [10] and [25] to the definitions used in our preliminaries.

1.1 CK78 [10] Definitions

First, we state the definitions from [10].

Definition A.1

(Achievable rate pairs (Imported from [10])) A rate pair $(R, R_e)$ of non-negative numbers is an achievable rate pair for a $(\textsf{ChB}, \textsf{ChE})$-wiretap channel if there exists a family of messages $\{\mathcal M_n\}_{n \in \mathbb {N}}$ and encoder-decoder pairs $\{({{\,\textrm{Enc}\,}}_n, {{\,\textrm{Dec}\,}}_n)\}_{n \in \mathbb {N}}$ where ${{\,\textrm{Enc}\,}}_n$ outputs an encoding of length n and such that

Message Rate R:
$$\begin{aligned} \lim _{n \rightarrow \infty } \frac{1}{n} \log \left|\mathcal M_n\right| = R \end{aligned}$$
Correctness: For all $m \in \mathcal M_n$,
$$\begin{aligned} \Pr [{{\,\textrm{Dec}\,}}_n(\textsf{ChB}({{\,\textrm{Enc}\,}}_n(m))) = m] \ge 1 - \epsilon _n \end{aligned}$$
where
$$\begin{aligned} \lim _{n \rightarrow \infty }\epsilon _n = 0 \end{aligned}$$
Equivocation Rate (Secrecy) $R_e$:
$$\begin{aligned} \lim _{n \rightarrow \infty } \frac{1}{n} H(M_n \mid \textsf{ChE}({{\,\textrm{Enc}\,}}_n(M_n))) \ge R_e \end{aligned}$$
where $M_n$ is uniform over $\mathcal M_n$.

We denote the set of all achievable rates as $\mathcal R$.

The equivocation rate $R_e$ captures a notion of statistical secrecy for a uniform random message. As the equivocation rate increases, the information that Eve has about the message decreases:

$$\begin{aligned}\lim _{n \rightarrow \infty } \frac{1}{n} I(M_n; \textsf{ChE}({{\,\textrm{Enc}\,}}_n(M_n)))= & {} \lim _{n \rightarrow \infty } \frac{1}{n}\left[ H(M_n) - H(M_n \mid \textsf{ChE}({{\,\textrm{Enc}\,}}_n(M_n))) \right] \\ {}{} & {} \le R - R_e\end{aligned}$$

In particular, when $R = R_e$, then $\lim _{n \rightarrow \infty } \frac{1}{n} I(M_n; \textsf{ChE}({{\,\textrm{Enc}\,}}_n(M_n))) = 0$.

This motivates the definition of secrecy capacity.

Definition A.2

(Secrecy capacity (Imported from [10])) The secrecy capacity of a wiretap channel is defined to be

$$\begin{aligned}C_s = \max _{(R, R) \in \mathcal R} R.\end{aligned}$$

The definition of CK Rate-R Wiretap Encoding Family (Definition 4.9) then follows by requiring $R = R_e$, and the alternate definition of secrecy capacity (Definition 4.10) is immediate.

1.2 MW00 [25] Definitions

The definitions of secrecy capacity and strong secrecy capacity used in [25] are essentially the same as the definitions used in [10] and Sect. 4.3 except that

The message space is binary: $\mathcal M_n = \{0,1\}^k$ where $k:= \lfloor (R - \epsilon _n)n\rfloor $
We only require correctness with respect to a random message:
$$\begin{aligned} \Pr [{{\,\textrm{Dec}\,}}_n(\textsf{ChB}({{\,\textrm{Enc}\,}}_n(M_n))) = M_n] \ge 1 - \epsilon _n \end{aligned}$$
where $M_n$ is uniformly distributed over $\mathcal M_n = \{0,1\}^k$.

Note that if we have a wiretap coding that satisfies the [10] definition, then it also satisfies the [25] definition as we can simply map each $m \in \mathcal M_n$ to a binary string in $\{0,1\}^k$.

Now, suppose we have a wiretap coding scheme that satisfies the [25] definition. Observe that by an averaging argument, for $\epsilon _n < \frac{1}{4}$, if

$$\begin{aligned} \Pr [{{\,\textrm{Dec}\,}}_n(\textsf{ChB}({{\,\textrm{Enc}\,}}_n(M_n))) = M_n] \ge 1 - \epsilon _n \end{aligned}$$

where $M_n$ is uniformly distributed over $\{0,1\}^k$, then for at least a $1 - \sqrt{\epsilon _n}$ fraction of the messages $m \in \{0,1\}^k$,

$$\begin{aligned} \Pr [{{\,\textrm{Dec}\,}}_n(\textsf{ChB}({{\,\textrm{Enc}\,}}_n(m))) = m] \ge 1 - \sqrt{\epsilon _n} \end{aligned}$$

Thus, we can define a new message space

$$\begin{aligned} \mathcal M'_n = \{m \mid \Pr [{{\,\textrm{Dec}\,}}_n(\textsf{ChB}({{\,\textrm{Enc}\,}}_n(m))) = m] \ge 1 - \sqrt{\epsilon _n}\} \end{aligned}$$

Then, the encoding scheme satisfying the [25] definition satisfies the [10] definition with respect to $\mathcal M'_n$ and $\epsilon '_n = \sqrt{\epsilon _n}$.^{Footnote 10} Note that since we only removed a $\sqrt{\epsilon _n}$ fraction of messages from $\mathcal M_n$ and $\epsilon _n \rightarrow 0$, then the rate and security requirement of [10] also hold in the limit since $\epsilon _n' \rightarrow 0$. In particular, this means that Theorem 4.14 holds with respect to the definitions we use in Sect. 4.3.

Proof of Theorem 4.17

In this section, we prove Theorem 4.17.

Theorem 4.17

The following are equivalent:

1.
$\textsf{ChE}$ is not less noisy than $\textsf{ChB}$. (Definition 3.7)
2.
$C_s > 0$ (Definition 4.10) i.e. There exists a CK Rate-R wiretap coding family for $(\textsf{ChB}, \textsf{ChE})$ with positive rate R. (Definition 4.9)
3.
$\overline{C_s} > 0$ (Definition 4.13) i.e. There exists a CK Rate-R wiretap coding family with strong secrecy for $(\textsf{ChB}, \textsf{ChE})$ with positive rate R. (Definition 4.12)
4.
There exists a 0.99-statistically secure wiretap coding scheme for $(\textsf{ChB}, \textsf{ChE})$. (Definition 4.4)
5.
There exists a statistically secure wiretap coding scheme for $(\textsf{ChB}, \textsf{ChE})$. (Definition 4.2)
6.
There exists a statistically secure wiretap coding scheme for general message spaces for $(\textsf{ChB}, \textsf{ChE})$ with a positive constant rate. (Definition 4.19.)

1.1 Background Information

To prove the theorem, we will use universal hash functions and average case extractors. We include some useful definitions and lemmas below.

Definition B.1

(Universal hash function) A family of functions $\mathcal H= \{H_k: \{0,1\}^n \rightarrow \{0,1\}^\ell \}_{k \in \mathcal K}$ is universal if $\forall x \ne x' \in \{0,1\}^n$,

$$\begin{aligned}\Pr _{k \leftarrow \mathcal K}[H_k(x) = H_k(x')] = 2^{-\ell }\end{aligned}$$

Definition B.2

(Average conditional min-entropy) The average conditional min-entropy of a random variable A given a random variable B is defined as

$$\begin{aligned}\tilde{H}_\infty (A \mid B) \triangleq - \log \left( \mathbb {E}_{b \leftarrow B} [\max _{a} \Pr \left[ A = a \mid B = b\right] \right) \end{aligned}$$

Lemma B.3

(Generalized leftover hash lemma, imported from [11]) Assume $\mathcal H= \{ H_k: \{0, 1 \}^n \rightarrow \{0, 1\}^\ell \}_{k \in \mathcal K}$ is a family of universal hash functions. Then, for any random variables X and $\textsf{Aux}$,

$$\begin{aligned}\Delta ((H_K(X), K, \textsf{Aux}), (U_\ell , K, \textsf{Aux})) \le \frac{1}{2} \sqrt{2^{-\tilde{H}_\infty (X \mid \textsf{Aux}) 2^\ell }}\end{aligned}$$

where K is uniform on $\mathcal K$ and $U_\ell $ is uniform over $\{0,1\}^\ell $.

Definition B.4

(Average case extractor) Let $\textrm{Ext}:\{0,1\}^n \times \{0,1\}^r \rightarrow \{0,1\}^\ell $ be a polynomial time probabilistic function which uses r bits of randomness. We say that $\textrm{Ext}$ is an efficient average-case $(n, m, \ell , \epsilon )$-strong extractor if for all pairs of random variables $(X, \textsf{Aux})$ such that X is an n-bit string satisfying $\tilde{H}_\infty (X \mid \textsf{Aux}) \ge m$,

$$\begin{aligned}\Delta ((\textrm{Ext}(X; R), R, \textsf{Aux}), (U_\ell , R, \textsf{Aux})) \le \epsilon \end{aligned}$$

where R is uniform on $\{0,1\}^r$ and $U_\ell $ is uniform on $\{0,1\}^\ell $.

Corollary B.5

(Imported from [11]) Universal hash functions are average-case $(n, m, \ell , \epsilon )$-strong extractors whenever $\ell \le m - 2\log (1/\epsilon ) + 2$.

Lemma B.6

If $(A_1, \ldots , A_n)$ and $(B_1, \ldots , B_n)$ are random variables such that for all $i \in [n]$, $(A_i, B_i)$ is independent of $\{(A_j, B_j)\}_{j \in [n] \backslash i}$, then

$$\begin{aligned}\tilde{H}_\infty ((A_1, \ldots , A_n) \mid (B_1, \ldots , B_n)) = \sum _{i = 1}^n\tilde{H}_\infty (A_i \mid B_i)\end{aligned}$$

Proof

$$\begin{aligned}&\tilde{H}_\infty ((A_1, \ldots , A_n) \mid (B_1, \ldots , B_n)) \\&= -\log \left( \sum _{b_1, \ldots , b_n}\Pr [B_1 = b_1, \ldots , B_n = b_n] \max _{a_1, \ldots a_n} \Pr \left[ A_1 = a_1, \ldots A_n = a_n \mid B_1 = b_1, \ldots B_n = b_n\right] \right) \\&= -\log \left( \sum _{b_1, \ldots , b_n}\prod _{i = 1}^n\Pr [B_i = b_i] \max _{a_1, \ldots a_n} \prod _{i = 1}^n\Pr \left[ A_i = a_i \mid B_i = b_i\right] \right) \\&= -\log \left( \sum _{b_1, \ldots , b_n}\prod _{i = 1}^n\Pr [B_i = b_i]\max _{a_i} \Pr \left[ A_i = a_i \mid B_i = b_i\right] \right) \\&= -\log \left( \prod _{i = 1}^n\left( \sum _{b_i}\Pr [B_i = b_i]\max _{a_i} \Pr \left[ A_i = a_i \mid B_i = b_i\right] \right) \right) \\&= \sum _{i=1}^n\left( -\log \left( \sum _{b_i}\Pr [B_i = b_i]\max _{a_i} \Pr \left[ A_i = a_i \mid B_i = b_i\right] \right) \right) \\&= \sum _{i=1}^n\tilde{H}_\infty (A_i \mid B_i) \end{aligned}$$

$\square $

Lemma B.7

Let $\{X_n\}_{n \in \mathbb {N}}$ be a sequence of discrete random variables where each $X_n$ is over a set $\mathcal X_n$. Let $\{f_n\}_{n \in \mathbb {N}}$ be a sequence of functions and let $Z_n = f_n(X_n)$. If

$$\begin{aligned}\lim _{n \rightarrow \infty }I(X_n; Z_n) = 0\end{aligned}$$

then for all $\epsilon > 0$, there exists $N_\epsilon $ such that for all $n > N_\epsilon $,

$$\begin{aligned}\tilde{H}_\infty (X_n \mid Z_n) \ge \log \log (|\mathcal X_n|) - \log (\log (|\mathcal X_n|) - H(X_n) + 1 + \epsilon )\end{aligned}$$

Proof

Define $g_n$ by $g_n(z) = \mathop {\mathrm {arg\,max}}\limits _{x \in \mathcal X_n}\Pr [X_n = x \mid Z_n = z]$. Then, define $p_n$ such that

$$\begin{aligned}1 - p_n:= \Pr [g_n(Z_n) = X_n] = \sum _{z}\Pr [Z_n = z]\left( \max _{x \in \mathcal X_n}\Pr [X_n = x \mid Z_n = z]\right) \end{aligned}$$

By Fano’s inequality,

$$\begin{aligned} H(X_n \mid Z_n) \le H_2(p_n) + p_n\log (|\mathcal X_n|) \le 1 + p_n\log (|\mathcal X_n|) \end{aligned}$$

which implies that

$$\begin{aligned} p_n \ge \frac{H(X_n \mid Z_n) - 1}{\log (|\mathcal X_n|)} \end{aligned}$$

Then, since $\lim _{n \rightarrow \infty }I(X_n; Z_n) = 0$, for all $\epsilon > 0$, there exists $N_\epsilon $ such that for all $n > N_\epsilon $,

$$\begin{aligned}H(X_n \mid Z_n) = H(X_n) - I(X_n; Z_n) \ge H(X_n) - \epsilon \end{aligned}$$

Thus, for all $n > N_\epsilon $,

$$\begin{aligned} 1 - p_n&\le 1 - \frac{(H(X_n) - \epsilon - 1)}{\log (|\mathcal X_n|)} = \frac{\log |\mathcal X_n| - H(X_n) + 1 + \epsilon }{\log |\mathcal X_n|} \end{aligned}$$

Now, by definition of average conditional min-entropy.

$$\begin{aligned}\tilde{H}_\infty (X_n \mid Z_n):= & {} -\log \left( \sum _{z}\Pr [Z_n = z]\left( \max _{x \in \mathcal X_n}\Pr [X_n = x \mid Z_n = z]\right) \right) \\ {}= & {} -\log (1 - p_n)\end{aligned}$$

Thus, for all $n > N_\epsilon $,

$$\begin{aligned} \tilde{H}_\infty (X_n \mid Z_n)&\ge -\log \left( \frac{\log |\mathcal X_n| - H(X_n) + 1 + \epsilon }{\log |\mathcal X_n|}\right) \\&= \log \log (|\mathcal X_n|) - \log (\log (|\mathcal X_n|) - H(X_n) + 1 + \epsilon ) \end{aligned}$$

$\square $

Lemma B.8

(Imported from [11]) If the support of B has size at most $2^\lambda $, then

$$\begin{aligned}\tilde{H}_\infty (A \mid (B, C)) \ge \tilde{H}_\infty (A \mid C) - \lambda \end{aligned}$$

Lemma B.9

(Maximal guessing probability) Let X be a random variable over $\{0,1\}$, let Y be a random variable over $\mathcal Y$, and let U be a uniform distribution over $\{0,1\}$ that is independent of (X, Y). Then, over all function $f:\mathcal Y\rightarrow \{0,1\}$,

$$\begin{aligned}\max _f\Pr [f(Y) = X] = \Delta ((X, Y), (U, Y)) + \frac{1}{2}\end{aligned}$$

Furthermore,

$$\begin{aligned}\tilde{H}_\infty (X \mid Y) = -\log (\max _f\Pr [f(Y) = X])\end{aligned}$$

Proof

$$\begin{aligned} \max _f\Pr [f(Y) = X]&= \sum _{y \in \mathcal Y}\left( \Pr [Y = y]\max _{x \in \{0,1\}}\Pr [X = x \mid Y = y]\right) \\&= \sum _{y \in \mathcal Y}\left( \Pr [Y = y]\left( \max _{x \in \{0,1\}}\Pr [X = x \mid Y = y] - \frac{1}{2}\right) \right) + \frac{1}{2}\\&= \frac{1}{2}\sum _{y \in \mathcal Y}\left( \Pr [Y = y]\cdot 2\max _{x \in \{0,1\}}\left|\Pr [X = x \mid Y = y] - \frac{1}{2}\right|\right) + \frac{1}{2}\\&= \frac{1}{2}\sum _{y \in \mathcal Y}\left( \Pr [Y = y]\cdot \sum _{x \in \{0,1\}}\left|\Pr [X = x \mid Y = y] - \frac{1}{2}\right|\right) + \frac{1}{2}\\&= \frac{1}{2}\sum _{x \in \{0,1\}, y \in \mathcal Y}\left( \left|\Pr [X = x \mid Y = y]\Pr [Y = y] - \frac{1}{2}\Pr [Y = y]\right|\right) + \frac{1}{2}\\&= \frac{1}{2}\sum _{x \in \{0,1\}, y \in \mathcal Y}\left( \left|\Pr [X = x, Y = y] - \Pr [U = x, Y = y]\right|\right) + \frac{1}{2}\\&= \Delta ((X, Y), (U, Y)) + \frac{1}{2} \end{aligned}$$

This proves the first statement. The second follows by definition:

$$\begin{aligned} \tilde{H}_\infty (X \mid Y)&= -\log \left( \sum _{y \in \mathcal Y}\left( \Pr [Y = y]\max _{x \in \{0,1\}}\Pr [X = x \mid Y = y]\right) \right) \\&= -\log (\max _f\Pr [f(Y) = X]) \end{aligned}$$

$\square $

Lemma B.10

If A and B are discrete random variables with support in $\mathcal X$ and $f:\mathcal X\rightarrow \mathcal Y$ is any (possibly randomized) function, then

$$\begin{aligned}\Delta (f(A), f(B)) \le \Delta (A, B)\end{aligned}$$

Furthermore, if f is a bijection,

$$\begin{aligned}\Delta (f(A), f(B)) = \Delta (A,B)\end{aligned}$$

Proof

$$\begin{aligned} \Delta (f(A), f(B))&= \frac{1}{2}\sum _{y \in \mathcal Y}\left|\Pr [f(A) = y] - \Pr [f(B) = y]\right|\\&= \frac{1}{2}\sum _{y \in \mathcal Y}\left| \sum _{x \in \mathcal X}(\Pr [f(A) = y \mid A = x]\right. \\&\quad \left. \Pr [A = x] - \Pr [f(B) = y \mid B = x]\Pr [B = x])\right| \\&= \frac{1}{2}\sum _{y \in \mathcal Y}\left|\sum _{x \in \mathcal X}\Pr [f(x) = y](\Pr [A = x] - \Pr [B = x])\right|\\&\le \frac{1}{2}\sum _{y \in \mathcal Y}\sum _{x \in \mathcal X}\Pr [f(x) = y]\left|(\Pr [A = x] - \Pr [B = x])\right|\\&= \frac{1}{2}\sum _{x \in \mathcal X}\left|(\Pr [A = x] - \Pr [B = x])\right|\\&= \Delta (A, B) \end{aligned}$$

If f is a bijection, the statistical distances are equal since $(A, B) = (f^{-1}(f(A)), f^{-1}(f(B)))$ additionally implies that $\Delta (f(A), f(B)) \ge \Delta (A, B)$. $\square $

Notation

If f is a function with a binary domain $\{0,1\}$, then for $x = (x_1, \ldots , x_t) \in \{0,1\}^t$, we use f(x) to denote $f(x_1) || \ldots || f(x_t)$.

1.2 Proof

We now prove Theorem 4.17.

Proof

The theorem follows from the relations below.

$1 \iff 2$. This follows from Theorem 4.11.
$2 \iff 3$. This follows from Theorem 4.14.
$6 \Rightarrow 5$. A statistically secure wiretap coding scheme for general message spaces can be easily transformed into one for a binary message spaces by ignoring all but the first bit of the message from the general message space.
$5 \Rightarrow 2$. Although, the correctness and security requirements of a statistically secure wiretap coding scheme are strictly stronger than those of a CK rate-R wiretap coding family, (2) requires the rate R to be positive^{Footnote 11} whereas (5) has no requirement on rate and can be satisfied with rate 0. Thus, our proof though simple is not immediate. Assume for contradiction that there is a statistically secure wiretap coding scheme for $(\textsf{ChB}, \textsf{ChE})$, but there does not exist a CK Rate-R wiretap coding family for $(\textsf{ChB}, \textsf{ChE})$ with positive rate. Let M be a uniform random variable over $\{0,1\}$. By correctness there exists some negligible function $\epsilon (\lambda )$ such that
$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}(1^\lambda , \textsf{ChB}({{\,\textrm{Enc}\,}}(1^\lambda , M))) = M] \ge 1 - \epsilon (\lambda ).\end{aligned}$$
Observe also that
$$\begin{aligned}I(M; \textsf{ChB}({{\,\textrm{Enc}\,}}(1^{\lambda }, M))) = 1 - H(M \mid \textsf{ChB}({{\,\textrm{Enc}\,}}(1^\lambda , M)))\end{aligned}$$
Then by Fano’s inequality and for sufficiently large $\lambda $, we have $H(M \mid \textsf{ChB}({{\,\textrm{Enc}\,}}(1^\lambda , M))) \le H(\epsilon (\lambda ))$ so that
$$\begin{aligned}I(M; \textsf{ChB}({{\,\textrm{Enc}\,}}(1^{\lambda }, M))) \ge 1 - H(\epsilon (\lambda )) = 1 - \textsf{negl}(\lambda )\end{aligned}$$
Moreover, by Theorem 4.16, for Eve, we have that
$$\begin{aligned}I(M; \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , M))) = \textsf{negl}(\lambda ).\end{aligned}$$
By the above, there exists some $n_0 \in \mathbb {N}$ such that $I(M; \textsf{ChB}({{\,\textrm{Enc}\,}}(1^{n_0}, M))) \ge 2/3$ and $I(M; \textsf{ChE}({{\,\textrm{Enc}\,}}(1^{n_0}, M))) \le 1/3$. Let ${{\,\textrm{Enc}\,}}_{n_0} \triangleq {{\,\textrm{Enc}\,}}(1^{n_0}, \cdot )$. We now define a new wiretap channel $(\textsf{ChB}', \textsf{ChE}')$ where
$$\begin{aligned}\textsf{ChB}' \triangleq \textsf{ChB}\circ \ {{\,\textrm{Enc}\,}}_{n_0}\\\textsf{ChE}' \triangleq \textsf{ChE}\circ \ {{\,\textrm{Enc}\,}}_{n_0}\end{aligned}$$
are two channels that first apply the encoder with block size $n_0$ and then apply the original channel $\textsf{ChB}$ (resp. $\textsf{ChE}$). Then observe that
$$\begin{aligned}I(M; \textsf{ChB}({{\,\textrm{Enc}\,}}_{n_0}( M))) - I(M; \textsf{ChE}({{\,\textrm{Enc}\,}}_{n_0}(M))) \ge 1/3\end{aligned}$$
so $\textsf{ChE}'$ is not less noisy than $\textsf{ChB}'$. Then Theorem 4.11 implies there exists a positive rate $R > 0$ CK rate-R code for the $(\textsf{ChB}', \textsf{ChE}')$-wiretap channel with encoder-decoder family $\{({{\,\textrm{Enc}\,}}'_n, {{\,\textrm{Dec}\,}}'_n)\}$ and message family $\{\mathcal M_n'\}$. This CK rate-R wiretap coding family for the $(\textsf{ChB}', \textsf{ChE}')$-wiretap channel can be converted into a CK rate-$R / n_0$ code for the $(\textsf{ChB}, \textsf{ChE})$-wiretap channel by constructing the encoder-decoder family
$$\begin{aligned}\{({{\,\textrm{Enc}\,}}_{n_0} \circ \ {{\,\textrm{Enc}\,}}_{n}', {{\,\textrm{Dec}\,}}_{n_0} \circ \ {{\,\textrm{Dec}\,}}_{n}')\}_{n}\end{aligned}$$
with message space $\{ \mathcal M_{n}' \}$. Since $n_0$ is a fixed positive constant, $R/n_0$ is a positive constant. This contradicts our assumption that there are no positive rate CK coding families for this $(\textsf{ChB}, \textsf{ChE})$-wiretap channel.

$3 \Rightarrow 4$ Suppose that $({{\,\textrm{Enc}\,}}_n, {{\,\textrm{Dec}\,}}_n)_{n \in \mathbb {N}}$ satisfies (3) for $(\textsf{ChB}, \textsf{ChE})$. Recall the definition of (3):

$\square $

Definition B.11

(CK rate-R wiretap coding family with strong secrecy [10, 25]) A family of wiretap encoder-decoder pairs $\{({{\,\textrm{Enc}\,}}_n, {{\,\textrm{Dec}\,}}_n)\}_{n \in \mathbb {N}}$ is a rate-R information theoretic wiretap coding family for a wiretap channel $(\textsf{ChB}, \textsf{ChE})$ and message family $\{\mathcal M_n\}_{n \in \mathbb {N}}$ if each ${{\,\textrm{Enc}\,}}_n$ outputs an encoding of length n such that

Message Rate R:
$$\begin{aligned}\lim _{n \rightarrow \infty } \frac{1}{n} \log \left|\mathcal M_n\right| = R\end{aligned}$$
Correctness: For all $m \in \mathcal M_n$,
$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}_n(\textsf{ChB}({{\,\textrm{Enc}\,}}_n(m))) = m] \ge 1 - \epsilon _n\end{aligned}$$
where
$$\begin{aligned}\lim _{n \rightarrow \infty }\epsilon _n = 0\end{aligned}$$
Strong Security:
$$\begin{aligned}\lim _{n \rightarrow \infty } I(M_n; \textsf{ChE}({{\,\textrm{Enc}\,}}_n(M_n))) = 0\end{aligned}$$
where $M_n$ is uniform over $\mathcal M_n$.

We denote the set of all achievable rates as $\mathcal R$.

To construct a 0.99-statistically secure wiretap encoding family for $(\textsf{ChB}, \textsf{ChE})$, we first need to move to a binary message space. To do so, we will use an extractor to extract a secure bit from a random message m over the larger message space $\mathcal M_n$ which we will then use to pad our binary message b. The 0.99 correctness of the new scheme will follow from the correctness of $({{\,\textrm{Enc}\,}}_n, {{\,\textrm{Dec}\,}}_n)$. Then, using the security of the extractor, we can show that Eve’s probability of decoding the message is at most $\frac{1}{2} + 0.01$.

Let $\ell (n) = \lceil \log (|\mathcal M_n|)\rceil $. For the remainder of this proof, we will assume that there is some canonical mapping between $\mathcal M_n$ and $\{0,1\}^{\ell (n)}$ and will allow for implicit conversions between the two representations.

Let $\textsf{ECC}= (\textsf{ECC}.{{\,\textrm{Enc}\,}}, \textsf{ECC}.{{\,\textrm{Dec}\,}})$ be an error correcting code for $\textsf{ChB}$ for single bit messages such that for $b \in \{0,1\}$,
$$\begin{aligned}\Pr [\textsf{ECC}.{{\,\textrm{Dec}\,}}(1^n, \textsf{ChB}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, b)))] \ge 1 - \textsf{negl}(n)\end{aligned}$$
and
$$\begin{aligned}|\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, b)| = dn\end{aligned}$$
for some constant d.
Let $\textrm{Ext}_n: \{0,1\}^{\ell (n)} \rightarrow \{0,1\}$ be a $(\ell (n), \log (nR) - 2, 1, (nR)^{-1/4})$ average case strong extractor that takes $r_n$ bits of randomness. Such an extractor exists for large enough n (i.e. $n > 4/R$) by Corollary B.5 since
$$\begin{aligned}1 \le \log (nR) - 2 - 2\log ((nR)^{1/4}) + 2 = \log (nR) - \frac{1}{2}\log (nR) = \frac{1}{2}\log (nR)\end{aligned}$$
Furthermore, for large n, since $\lim _{n \rightarrow \infty }\frac{1}{n}\log (|\mathcal M_n|) = R$, then $\ell (n) = O(n)$, so $r_n = O(n)$.

Define $({{\,\textrm{Enc}\,}}'_n, {{\,\textrm{Dec}\,}}'_n)_{n \in \mathbb {N}}$ by

We claim that for a large enough $n^*$, $({{\,\textrm{Enc}\,}}^*, {{\,\textrm{Dec}\,}}^*) = ({{\,\textrm{Enc}\,}}_{n^*}', {{\,\textrm{Dec}\,}}_{n^*}')$ satisfies (4). Correctness: If the decoder correctly recovers (v, p) and $\hat{x} = x$, then the decoder will output

$$\begin{aligned}\textrm{Ext}_n(\hat{x}; v) \oplus p = \textrm{Ext}_n(\hat{x}; v) \oplus \textrm{Ext}_n(x; v) \oplus b = b\end{aligned}$$

By our choice of error correcting code, since $|(v, p)| = O(n)$, the probability of correctly recovering (v, p) is at least $1 - \textsf{negl}(n)$. By the correctness of $({{\,\textrm{Enc}\,}}_n, {{\,\textrm{Dec}\,}}_n)$, the probability of correctly recovering $\hat{x} = x$ is at least $1 - \epsilon _n$ where $\lim _{n \rightarrow \infty }\epsilon _n = 0$.

Thus, for large enough n, the decoder outputs the message b with probability at least 0.99.

Security: Let $X_n, V_n, B, U$ be uniform random variables on $\mathcal M_n$, $\{0,1\}^{r_n}$, $\{0,1\}$, and $\{0,1\}$ respectively. Let $Z_n = \textsf{ChE}({{\,\textrm{Enc}\,}}_n(X_n))$. Then, by security of $({{\,\textrm{Enc}\,}}_n, {{\,\textrm{Dec}\,}}_n)$ and by Lemma B.7, for large enough n,

$$\begin{aligned} \tilde{H}_\infty (X_n \mid Z_n)&\ge \log \log (|\mathcal M_n|) - \log (\log (|\mathcal M_n|) - H(X_n) + 2) \\&= \log \log (|\mathcal M_n|) - 1 \end{aligned}$$

By the rate property of $({{\,\textrm{Enc}\,}}_n, {{\,\textrm{Dec}\,}}_n)$, $\lim _{n \rightarrow \infty }\frac{1}{n}\log |\mathcal M_n| = R$, so for large enough n,

$$\begin{aligned}\log |\mathcal M_n| \ge \frac{nR}{2}\end{aligned}$$

Thus, for large enough n,

$$\begin{aligned}\tilde{H}_\infty (X_n \mid Z_n) \ge \log \left( \frac{nR}{2}\right) - 1 = \log (nR) - 2\end{aligned}$$

Then since $\textrm{Ext}$ is an $(\ell (n), \log (nR) - 2, 1, (nR)^{-1/4})$-average case extractor, for large enough n, we have

$$\begin{aligned} \Delta ((V_n, \textrm{Ext}(X_n; V_n), Z_n), (V_n, U, Z_n)) \le (nR)^{-1/4} \end{aligned}$$

Claim B.12

For large n,

$$\begin{aligned} \max _f\Pr [f(\textsf{ChE}({{\,\textrm{Enc}\,}}_n'(B))) = B] \le \frac{1}{2} + (nR)^{-1/4} \end{aligned}$$

where f is taken over all functions.

Proof

By Lemma B.9 and the definition of ${{\,\textrm{Enc}\,}}_n'$, we have

$$\begin{aligned}&\max _f\Pr [f(\textsf{ChE}({{\,\textrm{Enc}\,}}_n'(B))) = B]\\&= \frac{1}{2} + \Delta ((B, \textsf{ChE}({{\,\textrm{Enc}\,}}_n'(B))), (U, \textsf{ChE}({{\,\textrm{Enc}\,}}_n'(B))))\\&= \frac{1}{2} + \Delta ((B, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, V_n, \textrm{Ext}(X_n; V_n) \oplus B)), Z_n), \\&\quad (U, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, V_n, \textrm{Ext}(X_n; V_n) \oplus B)), Z_n)) \end{aligned}$$

Then, by Lemma B.10,

$$\begin{aligned}&\Delta ((B, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, V_n, \textrm{Ext}(X_n; V_n) \oplus B)), Z_n),\\&\quad (U, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^n, V_n, \textrm{Ext}(X_n; V_n) \oplus B)), Z_n))\\&\le \Delta ((B, V_n, \textrm{Ext}(X_n; V_n) \oplus B, Z_n), (U, V_n, \textrm{Ext}(X_n; V_n) \oplus B, Z_n))\\&= \Delta ((B, V_n, \textrm{Ext}(X_n; V_n), Z_n), (U, V_n, \textrm{Ext}(X_n; V_n) \oplus B \oplus U, Z_n)) \end{aligned}$$

Furthermore, since (B, U) is independent of $(V_n, \textrm{Ext}(X_n; V_n), Z_n)$, we have

$$\begin{aligned}&\Delta ((B, V_n, \textrm{Ext}(X_n; V_n), Z_n), (U, V_n, \textrm{Ext}(X_n; V_n) \oplus B \oplus U, Z_n))\\&= \Delta ((B, V_n, \textrm{Ext}(X_n; V_n), Z_n), (B, V_n, \textrm{Ext}(X_n; V_n) \oplus U \oplus B, Z_n))\\&= \Delta ((B, V_n, \textrm{Ext}(X_n; V_n), Z_n), (B, V_n, U, Z_n))\\&= \Delta ((V_n, \textrm{Ext}(X_n; V_n), Z_n), (V_n, U, Z_n)) \\&\le (nR)^{-1/4} \end{aligned}$$

and the claim follows. $\square $

Thus, for large enough $n^*$, we have that $\max _f\Pr [f(\textsf{ChE}({{\,\textrm{Enc}\,}}_{n^*}'(B))) = B] \le \frac{1}{2} + 0.01$.

Rate: For any $b \in \{0,1\}$, for some fixed $n^*$,

$$\begin{aligned}{{\,\textrm{Enc}\,}}^*(b) = {{\,\textrm{Enc}\,}}'_{n^*}(b) = (\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^{n^*}, v, \textrm{Ext}_{n^*}(x; v) \oplus b), {{\,\textrm{Enc}\,}}_{n^*}(x))\end{aligned}$$

and it is then easy to observe that $|{{\,\textrm{Enc}\,}}^*(b)|$ is a constant.

$4 \Rightarrow 6$. Let $(\textsf{ChB}, \textsf{ChE})$ be a wiretap channel. We claim that the following construction is a statistically secure wiretap coding scheme for general messages space for $(\textsf{ChB}, \textsf{ChE})$ with positive constant rate.

Construction 1

We will construct (6) from the following ingredients:

A wiretap coding $({{\,\textrm{Enc}\,}}^*, {{\,\textrm{Dec}\,}}^*)$ satisfying
- Rate: For all $b \in \{0,1\}, |{{\,\textrm{Enc}\,}}^*(b)| = c$ for some constant c.
- Correctness: For all $b \in \{0,1\}$,
  $$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}^*(\textsf{ChB}({{\,\textrm{Enc}\,}}^*(b))) = b] \ge 0.95\end{aligned}$$
- Security:
  $$\begin{aligned}\tilde{H}_\infty (B \mid \textsf{ChE}({{\,\textrm{Enc}\,}}^*(B))) \ge 0.95\end{aligned}$$
  where B is uniform over $\{0,1\}$.
Note that a wiretap coding $({{\,\textrm{Enc}\,}}^*, {{\,\textrm{Dec}\,}}^*)$ satisfying (4) also satisfies this definition as
$$\begin{aligned}\max _f\Pr [f(\textsf{ChE}({{\,\textrm{Enc}\,}}^*(B))) = B] \le \frac{1}{2} + 0.01\end{aligned}$$
implies by Lemma B.9 that
$$\begin{aligned}\tilde{H}_\infty (B \mid \textsf{ChE}({{\,\textrm{Enc}\,}}^*(B))) = -\log (\max _f\Pr [f(\textsf{ChE}({{\,\textrm{Enc}\,}}^*(B))) = B]) \ge 0.95\end{aligned}$$
An error-correcting code $\textsf{ECC}= (\textsf{ECC}.{{\,\textrm{Enc}\,}}, \textsf{ECC}.{{\,\textrm{Dec}\,}})$ for single bit messages for $\textsf{ChB}$ such that for $b \in \{0,1\}$,
$$\begin{aligned}\Pr [\textsf{ECC}.{{\,\textrm{Dec}\,}}(1^\lambda , \textsf{ChB}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^\lambda , b)] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$
and
$$\begin{aligned}|\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^\lambda , b)| = d\lambda \end{aligned}$$
for some constant d.
A universal hash family $\mathcal H_\lambda \triangleq \left\{ H_k: \{0,1\}^\lambda \rightarrow \{0, 1\}^{0.6\lambda } \right\} _{k \in \mathcal K_\lambda }$ where $\log (|\mathcal K_\lambda |) = O(\lambda )$.
An efficient average-case $(\lambda , 0.35\lambda , 0.1\lambda , 2^{-0.1\lambda })$-strong extractor $\textrm{Ext}_\lambda : \{0,1\}^\lambda \times \{0,1\}^{r_\lambda } \rightarrow \{0,1\}^{0.1\lambda }$ that take $r_\lambda = O(\lambda )$ bits of randomness. Such an extractor exists by Corollary B.5 since
$$\begin{aligned}0.1\lambda \le 0.35\lambda - 2\log (2^{0.1\lambda }) + 2 = 0.35\lambda - 0.2\lambda + 2 = 0.15\lambda + 2\end{aligned}$$

We now define our wiretap encoding scheme which has message length $\ell (n) = 0.1\lambda $.

Correctness: We need to show that for all messages $m \in \{0,1\}^{\ell (\lambda )}$,

$$\begin{aligned}\Pr [{{\,\textrm{Dec}\,}}(1^\lambda , \textsf{ChB}({{\,\textrm{Enc}\,}}(1^\lambda , m))) = m] \ge 1 - \textsf{negl}(\lambda )\end{aligned}$$

First, we assume that the decoder correctly recovers $(k, v, y = H_k(x), p = (\textrm{Ext}_\lambda (x; v) \oplus m))$. By our choice of error-correcting code $\textsf{ECC}$ for $\textsf{ChB}$, this occurs with overwhelming probability. We will also assume $x \in T_{\hat{x}}$ since by a Chernoff bound, if $\hat{x} = {{\,\textrm{Dec}\,}}^*(\textsf{ChB}(c_2)) = {{\,\textrm{Dec}\,}}^*(\textsf{ChB}({{\,\textrm{Enc}\,}}^*(x)))$, by the 0.95 correctness of $({{\,\textrm{Enc}\,}}^*, {{\,\textrm{Dec}\,}}^*)$, $\Delta _{H}(\hat{x}, x) < 0.1\lambda $ with overwhelming probability so $x \in T_{\hat{x}}$ with overwhelming probability. We now claim that $T_{\hat{x}}$ is a singleton element $x^* = x$ with all but negligible probability. Observe by definition of $T_{\hat{x}}$ that

$$\begin{aligned}|T_{\hat{x}}| \le \left( {\begin{array}{c}\lambda \\ 0.1\lambda \end{array}}\right) \le \left( \frac{e\lambda }{0.1\lambda }\right) ^{0.1\lambda } = (10e)^{0.1\lambda } \le 2^{0.5\lambda }\end{aligned}$$

Then, for any fixed x and for any $x' \in \{0,1\}^\lambda $, since $\mathcal H$ is a universal hash function, we have

$$\begin{aligned}\Pr _{k \leftarrow \mathcal K_\lambda }[H_k(x) = H_k(x')] \le 2^{-0.6\lambda }\end{aligned}$$

Therefore, by a union bound,

$$\begin{aligned}\Pr _{k \leftarrow \mathcal K_\lambda }[\exists x' \in T_{\hat{x}} \mid x' \ne x \wedge H_k(x') = H_k(x)] \le 2^{-0.6\lambda }\cdot 2^{0.5\lambda } = 2^{-0.1\lambda } = \textsf{negl}(\lambda )\end{aligned}$$

Thus, with overwhelming probability, $T_{\hat{x}}$ is a singleton element $x^* = x$, which means that the decoder outputs $\textrm{Ext}_\lambda (x^*; v) \oplus p = \textrm{Ext}_\lambda (x^*; v) \oplus \textrm{Ext}_\lambda (x;v) \oplus m = m$ with overwhelming probability.

Security: We need to show that for all adversaries $\mathcal A$ and all messages $m_0 \ne m_1 \in \{0,1\}^{\ell (n)}$,

$$\begin{aligned}\Pr [\mathcal A(1^\lambda , m_0, m_1, \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , m_B))) = B] \le \frac{1}{2} + \textsf{negl}(\lambda )\end{aligned}$$

where B is uniformly distributed over $\{0,1\}$. Let $(m_0, m_1)$ be any two messages of length $\ell (n)$, and let $\mathcal A$ be any adversary. Let B and U be uniform random variables over $\{0,1\}$. Let $X_\lambda = (X_\lambda ^{(1)}, \ldots , X_\lambda ^{(\lambda )})$ where each $X_\lambda ^{(i)}$ is an independently and identically distributed uniform random variable over $\{0,1\}$, and let $Z_\lambda = (Z_\lambda ^{(1)}, \ldots , Z_\lambda ^{(\lambda )})$ where $Z_\lambda ^{(i)} = \textsf{ChE}({{\,\textrm{Enc}\,}}^*(X_\lambda ^{(i)}))$. Let $K_\lambda , V_\lambda $ be uniform random variables over $\mathcal K_\lambda $ and $\{0,1\}^{r_\lambda }$ respectively, and let $Y_\lambda = H_{K_\lambda }(X_\lambda )$. First we show the following claim:

Claim B.13

$$\begin{aligned}\Delta ((K_\lambda , Y_\lambda , V_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ), Z_\lambda ), (K_\lambda , Y_\lambda , V_\lambda , U_{0.1\lambda }, Z_\lambda )) \le 2^{-0.1\lambda }\end{aligned}$$

where $U_{0.1\lambda }$ is uniform over $\{0,1\}^{0.1\lambda }$.

Proof

Since $\textrm{Ext}_\lambda $ is a $(\lambda , 0.35\lambda , 0.1\lambda , 2^{-0.1\lambda })$-average case extractor, it suffices to prove that

$$\begin{aligned}\tilde{H}_\infty (X_\lambda \mid K_\lambda , Y_\lambda , Z_\lambda ) \ge 0.35\lambda \end{aligned}$$

Now, since $|Y_\lambda | = 0.6\lambda $, by Lemma B.8,

$$\begin{aligned} \tilde{H}_\infty (X_\lambda \mid K_\lambda , Y_\lambda , Z_\lambda ) \ge \tilde{H}_\infty (X_\lambda \mid K_\lambda , Z_\lambda ) - 0.6\lambda \end{aligned}$$

Then since $K_\lambda $ is independent of $(X_\lambda , Z_\lambda )$, we have

$$\begin{aligned}\tilde{H}_\infty (X_\lambda \mid K_\lambda , Z_\lambda ) = \tilde{H}_\infty (X_\lambda \mid Z_\lambda )\end{aligned}$$

Then by Lemma B.6 and by the security property of $({{\,\textrm{Enc}\,}}^*, {{\,\textrm{Dec}\,}}^*)$,

$$\begin{aligned}\tilde{H}_\infty (X_\lambda \mid Z_\lambda ) = \sum _{i = 1}^n \tilde{H}_\infty (X_{\lambda }^{(i)} \mid Z_{\lambda }^{(i)}) \ge 0.95\lambda \end{aligned}$$

Therefore, we get

$$\begin{aligned}\tilde{H}_\infty (X_\lambda \mid K_\lambda , Y_\lambda , Z_\lambda ) \ge 0.95\lambda - 0.6\lambda = 0.35\lambda \end{aligned}$$

$\square $

By Lemmas B.9 and B.10 and since (B, U) is independent of $(X_\lambda , V_\lambda , K_\lambda , Z_\lambda )$, we have

$$\begin{aligned}&\Pr [\mathcal A(1^\lambda , m_0, m_1, \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , m_B))) = B]\\&\le \max _{\mathcal A}\Pr [\mathcal A(1^\lambda , m_0, m_1, \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , m_B))) = B] \\&= \max _{\mathcal A}\Pr [\mathcal A(1^\lambda , m_0, m_1, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^\lambda , K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ) \oplus m_B)), Z_\lambda ) = B] \\&= \frac{1}{2} + \Delta ((B, 1^\lambda , m_0, m_1, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^\lambda , K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ) \oplus m_B)), Z_\lambda ),\\&\hspace{1.8cm}(U, 1^\lambda , m_0, m_1, \textsf{ChE}(\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^\lambda , K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ) \oplus m_B)), Z_\lambda ))\\&\le \frac{1}{2} + \Delta ((B, K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ) \oplus m_B, Z_\lambda ), (U, K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ) \oplus m_B, Z_\lambda ))\\&= \frac{1}{2} + \Delta ((B, K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ), Z_\lambda ), (U, K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ) \oplus m_B \oplus m_U, Z_\lambda ))\\&= \frac{1}{2} + \Delta ((B, K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ), Z_\lambda ), (B, K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ) \oplus m_U \oplus m_B, Z_\lambda )) \end{aligned}$$

Then, using Claim B.13 and the fact that B is independent of $(K_\lambda , Y_\lambda , V_\lambda , Z_\lambda )$, we have that

$$\begin{aligned}\Delta ((B, K_\lambda , Y_\lambda , V_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ), Z_\lambda ), (B, K_\lambda , Y_\lambda , V_\lambda , U_{0.1\lambda }, Z_\lambda ))\le 2^{-0.1\lambda }\end{aligned}$$

and similarly that

$$\begin{aligned}\Delta ((B, K_\lambda , Y_\lambda , V_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ) \oplus m_B \oplus m_U, Z_\lambda ), (B, K_\lambda , Y_\lambda , V_\lambda , U_{0.1\lambda }, Z_\lambda )){\le } 2^{-0.1\lambda }\end{aligned}$$

Therefore,

$$\begin{aligned}{} & {} \Delta ((B, K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda ), Z_\lambda ), (B, K_\lambda , V_\lambda , Y_\lambda , \textrm{Ext}_\lambda (X_\lambda ; V_\lambda )\\ {}{} & {} \quad \oplus m_U \oplus m_B, Z_\lambda )) \le 2\cdot 2^{-0.1\lambda }\end{aligned}$$

and so

$$\begin{aligned}\Pr [\mathcal A(1^\lambda , m_0, m_1, \textsf{ChE}({{\,\textrm{Enc}\,}}(1^\lambda , m_B))) = B] \le \frac{1}{2} + 2\cdot 2^{-0.1\lambda } = \frac{1}{2} + \textsf{negl}(\lambda )\end{aligned}$$

Rate For a message $m \in \{0,1\}^{0.1(\lambda )}$, the encoding of m is $(c_1, c_2) = (\textsf{ECC}.{{\,\textrm{Enc}\,}}(1^\lambda , k, v, y = H_k(x), p = (\textrm{Ext}_\lambda (x; v) \oplus m)), {{\,\textrm{Enc}\,}}^*(x))$. Then, we have

$|k| = O(\lambda )$
$|v| = O(\lambda )$
$|y| = 0.6\lambda $
$|p| = 0.1\lambda $
Thus, since $\textsf{ECC}$ is a constant rate error correcting code, we have $|c_1| = O(\lambda )$.
Since for any bit b, $|{{\,\textrm{Enc}\,}}^*(b)|$ is constant and since $|x| = \lambda $, then $|c_2| = |{{\,\textrm{Enc}\,}}^*(x)| = O(\lambda )$.

Therefore, $|c_1, c_2| = O(\lambda )$. Thus, the rate is a positive constant.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Reprints and permissions

About this article

Cite this article

Ishai, Y., Korb, A., Lou, P. et al. Beyond the Csiszár–Körner Bound: Best-Possible Wiretap Coding via Obfuscation. J Cryptol 37, 1 (2024). https://doi.org/10.1007/s00145-023-09482-2

Download citation

Received: 01 September 2022
Revised: 30 August 2023
Accepted: 04 September 2023
Published: 18 October 2023
DOI: https://doi.org/10.1007/s00145-023-09482-2

Beyond the Csiszár–Körner Bound: Best-Possible Wiretap Coding via Obfuscation

Abstract

Similar content being viewed by others

Beyond the Csiszár-Korner Bound: Best-Possible Wiretap Coding via Obfuscation

Hash-then-Encode: A Modular Semantically Secure Wiretap Code

A Virtual Wiretap Channel for Secure Message Transmission

1 Introduction

1.1 Our Contributions

Theorem 1.1

Theorem 1.2

1.2 Related Works

2 Technical Overview

Definition 2.1

Definition 2.2

Definition 2.3

Definition 2.4

Definition 2.5

3 Preliminaries

Notation

Definition 3.1

Lemma 3.2

Remark 3.3

3.1 Channel Definitions

Definition 3.4

Notation

Definition 3.5

Definition 3.6

3.1.1 Less Noisy and Channel Degradation

Definition 3.7

Definition 3.8

Definition 3.9

Remark 3.10

Theorem 3.11

3.1.2 Limiting Channel Degradation

Definition 3.12

Lemma 3.13

Proof

Lemma 3.14

Proof

4 Wiretap Channels

4.1 Wiretap Channel Definitions

Definition 4.1

Definition 4.2

Definition 4.3

Notation

Definition 4.4

4.2 Ideal Obfuscation Model

Definition 4.5

Definition 4.6

Remark 4.7

4.3 Wiretap Feasibility in the Information Theoretic Setting

Theorem 4.8

Definition 4.9

Definition 4.10

Theorem 4.11

Definition 4.12

Definition 4.13

Theorem 4.14

Remark 4.15

Theorem 4.16

Theorem 4.17

Proof

4.4 Rate and General Message Spaces

Remark 4.18

Definition 4.19

Remark 4.20

5 Constructing Bounded Query Secure Wiretap Coding Schemes in the Ideal Obfuscation Model

5.1 Construction

Definition 5.1

Definition 5.2

Theorem 5.3

Proof

Corollary 5.4

Remark 5.5

5.2 Correctness

Definition 5.6

Lemma 5.7

Proof

Claim 5.14

Proof