I Introduction
Producing an approximation of a desired statistic at a channel output via application of minimal randomness at its input has emerged as a useful building block for many problems in information theory, including source coding [1], rate distortion theory [2], coordination [3] and strong secrecy [4, 5, 6, 7, 8]. The origins of this problem can be traced back to Wyner’s work [9]
on the characterization of common randomness among two dependent random variables, in which he used a normalized
KullbackLeibler (KL) divergence as a measure of approximation. The problem was subsequently formalized and generalized for total variation using informationspectrum methods [10] and the optimal amount of randomness was called channel resolvability. Subsequent works have simplified proofs, both for total variation [3] and KL divergence [11], and studied multiuser settings, such as multipleaccess channels (MACs) with noncooperative encoders [12, 13, 14, 15].This paper studies the channel resolvability region for discrete memoryless multipleaccess channels (MACs) with cooperating encoders; specifically, we focus on a cribbing model [16] in which one encoder has access to the input or output of the other encoder subject to various causality constraints. The cribbing model captures the essence of cooperation and produces results and insights that are independent of cooperation signaling mechanisms. A key contribution of this paper is the characterization of the channel resolvability region for four cribbing situations while approximating the output distribution according to nonnormalized KL divergence: (i) degraded message sets, (ii) noncausal cribbing, (iii) causal cribbing and (iv) strictlycausal cribbing.
In the case of noncausal cribbing, an achievability region is already available from [3, Corollary VII.8] for approximation in terms of total variation, in which case our contribution is only to derive an achievability and matching converse for KL divergence. In the case of causal and strictlycausal cribbing, we not only develop converse results but also propose an achievability scheme that handles the causality constraints with a blockMarkov coding scheme; in particular, we show that the dependencies created by the blockMarkov coding scheme can be hidden through appropriate recycling of secret randomness after identifying a wiretap channel embedded in the model.
In the second part of this paper, strong secrecy [17, 18] achievable rates are obtained for the multipleaccess channel (MAC) with cribbing. We develop a wiretap coding scheme that achieves strong secrecy, fueled by the results in the earlier part of this paper on the resolvability of cribbing MAC. The secrecy rates for MAC with degraded message sets as well as noncausal cribbing follow from corresponding resolvability results without complication. However, a novel approach is needed for the causal and strictly causal cribbing, because the cribbing MAC codebook devised by Willems and van der Muelen [16] is not directly compatible with the randomness recycling in the resolvability codebooks under causality constraints. Accordingly, a notable contribution of this work is a new superposition coding strategy that uses all components of the cribbing signal for cooperation to achieve efficient decoding at the legitimate receiver, while at the same time forcing a part of the randomness within the cribbing signal to remain noncooperative from the viewpoint of the eavesdropper. This feature is needed for randomness recycling and is crucial to avoid secrecy rate loss under strictly causal and causal cribbing.
Strong secrecy for MAC with noncooperating encoders has been studied in [13, 14, 15]. To the best of our knowledge, strong secrecy in multiterminal settings under cooperating encoders has not been comprehensively studied. For completeness we highlight examples of the investigation of weak secrecy under cooperation: MAC with cooperating or partially cooperating encoders [19, 20, 21, 22], interference channel with cooperating encoders [23, 24, 25], relay channel with an external eavesdropper [26, 27] and broadcast channel with cooperating receivers [28]. These works follow the classical approach of Wyner [29] and Csiszár [30] to develop weak secrecy results. To the best of our understanding there has been limited work on any type of cooperative strong secrecy; notable examples are Goldfeld et al. [7] on receive side cooperation in the broadcast channel, Watanabe and Oohama [31] on the cognitive interference channel with confidential messages, and Chou and Yener [32] on Polar coding for the MAC wiretap channel with cooperative jamming.
Ii Notation
Random variables are represented by upper case letters and their realizations by the corresponding lower case letters, e.g., is a realization of the random variable . Superscripts denote the length of a sequence of symbols and subscripts denote the position of a symbol in a sequence. Calligraphic letters represent sets, the cardinality of which is denoted by . For example, where belongs to the alphabet of size . and
denote probability distributions on
and , respectively. We sometimes omit the subscripts in probability distributions if they are clear from the context, i.e., we write instead of .For two distributions and on the same alphabet, the KL divergence is defined by and the variational distance is defined by . Throughout the paper,
denotes the base 2 logarithm. For an i.i.d. vector whose components are distributed according to
, the product distribution is denoted by . The set of stronglytypical sequences of length with respect to is defined as:For a set of random variables indexed over a countable set , denotes the expectation over all random variables with indices in except that with index . is the expectation w.r.t. the random variable and is the indicator function.
Iii Problem Definition and Main Results
Iiia Problem Definition: Channel Resolvability of Mac with Cribbing
We consider four scenarios for the twouser discrete memoryless MAC with cribbing (see Fig. 1). The discrete memoryless MAC consists of finite input alphabets and , and finite output alphabet , together with a channel transition probability . For a joint input distribution on , the output is distributed according to . A channel resolvability code consists of two encoders and with inputs and defined on and . In the four scenarios studied in this paper, the persymbol encoding functions are defined as follows.
In the MAC with degraded message sets (Fig. 1(a)), Encoder 2 has access to the input of Encoder 1
(1) 
In the MAC with noncausal cribbing (Fig. 1(b)), Encoder 2 has noncausal access to the entire current codeword of Encoder 1
(2) 
In the MAC with strictlycausal cribbing (Fig. 1(c)), Encoder 2 has access to the output of Encoder 1 with a onesymbol delay
(3) 
In the MAC with causal cribbing (Fig. 1(d)), Encoder 2 has access to the output of Encoder 1 with zero delay
(4) 
Definition 1.
A rate pair is said to be achievable for the discrete memoryless MAC if for a given^{1}^{1}1Originally in [10] the resolvability rate was defined as “the number of random bits required per channel use in order to generate an input that achieves arbitrarily accurate approximation of the output statistics for any given input process.” More recent works consider a fixed but arbitrary , leaving out the implied intersection of rate regions over different . This is more convenient in several ways, including in the application of resolvability to secrecy problems where only the simulation of a certain is of interest. there exists a sequence of codes such that . The MAC resolvability region is the closure of the set of achievable rate pairs .
IiiB Statement of Main Results
We first recall the known MAC resolvability region with noncooperating encoders, which will serve as a reference to assess the benefits of cooperation.
Theorem 1 ([13]).
The resolvability region for the MAC with noncooperating encoders is the set of rate pairs such that
(5)  
(6)  
(7) 
for some joint distribution
with marginal .The resolvability region in [13] was derived with respect to variational distance approximation.
Theorem 2.
The resolvability region for the MAC with degraded message sets is the set of rate pairs such that
(8)  
(9) 
for some joint distribution with marginal .
Proof.
See Section VA. ∎
The absence of the individual rate constraint is a direct consequence of the degraded message model that allows Encoder 2 to benefit from the randomness provided via , reducing the required individual rate constraint for User 2 to , which is omitted. Another difference between the regions described by Theorem 1 and Theorem 2 is that the former includes a convexifying auxiliary random variable that is missing in the latter. The region described by Theorem 2 is already convex due to the larger set of available input distributions, as proved in Appendix AA.
Theorem 3.
The resolvability region for the MAC with noncausal cribbing is the set of rate pairs such that
(10)  
(11)  
(12) 
for some joint distribution with marginal .
Proof.
See Section VB. ∎
The achievability result was derived in [3, Corollary VII.8] for approximation of the output statistics in terms of variational distance. Our contribution here is to provide achievability and converse proofs for approximation in terms of KL divergence. Compared with the MAC with degraded message sets, more randomness is required as seen by the presence of an individual rate constraint for User 2. As already discussed in [3], this stems from the impossibility for Encoder 2 to extract uniform randomness from the observation of the output of Encoder 1 at a rate exceeding . This rate region is convex (see Appendix AB).
Theorem 4.
The resolvability region for the MAC with strictlycausal cribbing is included in the set of rate pairs such that
(13)  
(14)  
(15) 
for some joint distribution with marginal . An achievable region is characterized by the same rate constraints and distribution, but subject to the additional constraint .
Proof.
See Section VC. ∎
The strict causality constraint leads to the appearance of a new random variable in several terms in the right hand side of the individual rate constraints, thus the individual rate constraints can be larger than Theorem 3, i.e., more needed randomness. The achievable region provided by Theorem 4 does not provably match the outer bound because the set of probability distributions available in the achievable region is smaller than in the converse, due to the additional constraint . The rate regions defined by the inner and outer bounds are convex (see Appendix AC).
Theorem 5.
The resolvability region for the MAC with causal cribbing is the set of rate pairs such that
(16)  
(17)  
(18) 
for some joint distribution with marginal .
Proof.
See Section VD. ∎
Similar to what was observed for the MAC reliability region [16], the MAC resolvability region with causal cribbing is identical to that obtained for noncausal cribbing.
Remark 1.
Theorem 5 is established from Theorem 4 using Shannon strategies as in [16], yet Theorem 5 has an achievable region that is tight against the outer bound when Theorem 4 does not. Perhaps surprisingly, this happens because the choice of random variables in the Shannon strategy automatically satisfies the constraint imposed in the achievability of Theorem 4.
Iv Strong Secrecy from Channel Resolvability
In this section we use the resolvability results to study the multipleaccess wiretap channel with cribbing. For each of the cribbing models previously discussed, an achievable strong secrecy rate region is presented. Consider a MAC with cribbing where and are finite input alphabets, and are the finite output alphabets of the legitimate receiver and the wiretapper, respectively. A code consists of two encoders and and a decoder . The encoders are defined similar to (1)(4) but the functions and are now stochastic and not deterministic. The decoding function at the legitimate receiver is defined as:
(19) 
The probability of error at the legitimate receiver is defined as . The strong secrecy metric adopted in this paper is the total amount of leaked confidential information per codeword, defined as .
Definition 2.
A strong secrecy rate pair is said to be achievable for the discrete memoryless MAC if there exists a sequence of codes such that and vanish as .
Proposition 1.
For the multipleaccess wiretap channel with degraded message sets, the following strongsecrecy rate region is achievable:
(20) 
Proof.
See Appendix CA. ∎
Proposition 2.
For the multipleaccess wiretap channel with noncausal cribbing, the following strongsecrecy rate region is achievable:
(21) 
Proposition 3.
For the multipleaccess wiretap channel with strictlycausal cribbing, the following strongsecrecy rate region is achievable:
(22) 
Remark 2.
Recall the resolvability achievable rate region under the strictly causal cribbing had a constraint on the allowable probability distributions. This constraint is implicit in Proposition 3 in the form of the nonnegativity constraint on .
Proposition 4.
For the multipleaccess wiretap channel with causal cribbing, the following strongsecrecy rate region is achievable:
(23) 
V Proofs of Main Results
Va Theorem 2: Mac with Degraded Message Sets
VA1 Achievability
Consider a distribution such that .

Independently generate codewords each with probability . Label them , .

For every , independently generate codewords each with probability . Label them , .
For and , let and denote the random variables representing the randomly generated codewords. The average KL divergence is:
(24) 
where follows by Jensen’s inequality. We finally write the righthand side of (24) as with
and
where
Combining the bounds on and we obtain exponentially with if and . This implies, by Markov’s inequality, that for a suitable choice of ; for .
VA2 Converse
By assumption,
where (a) follows because conditioning does not increase entropy and (b) follows by Jensen’s Jensen’s inequality and the convexity of with . First, note that
(25)  
Comments
There are no comments yet.