On Secure Source Coding with Side Information at the Encoder

We consider a secure source coding problem with side information (S.I.) at the decoder and the eavesdropper. The encoder has a source that it wishes to describe with limited distortion through a rate limited link to a legitimate decoder. The message sent is also observed by the eavesdropper. The encoder aims to minimize both the distortion incurred by the legitimate decoder; and the information leakage rate at the eavesdropper. When the encoder has access to the uncoded S.I. at the decoder, we characterize the rate-distortion-information leakage rate (R.D.I.) region under a Markov chain assumption and when S.I. at the encoder does not improve the rate-distortion region as compared to the case when S.I. is absent. When the decoder also has access to the eavesdroppers S.I., we characterize the R.D.I. region without the Markov Chain condition. We then consider a related setting where the encoder and decoder obtain coded S.I. through a rate limited helper, and characterize the R.D.I. region for several special cases, including special cases under logarithmic loss distortion and for special cases of the Quadratic Gaussian setting. Finally, we consider the amplification measures of list or entropy constraint at the decoder, and show that the R.D.I. regions for the settings considered in this paper under these amplification measures coincide with R.D.I. regions under per symbol logarithmic loss distortion constraint at the decoder.

A particular distortion measure that we will focus on in this paper is the logarithmic loss (log-loss) distortion measure, first proposed in [10]. Log-loss has the interesting property that S.I. at the encoder does not improve the rate-distortion region, with respect to the Wyner-Ziv setting [11] where S.I. is absent at the encoder. This property will be key in establishing the results in this paper. Following [12] and [13], we will also extend our work to consider source amplification measures for our setting. We consider the amplification measures of list constraint [14], and the block entropy constraint, H(X n |M, Y n )/n, at the decoder. Interestingly, we find, for our settings, that the R.D.I. region is the same regardless of whether one uses symbol by symbol log-loss or the above amplification measures.
The rest of this paper is as follow. We first provide formal definitions in Section II. Our main results are then given in the subsequent sections and summarized here: • In Section III, we consider our setting in Figure 1 when the eavesdropper's S.I. is not available at the legitimate decoder. General inner and outer bounds are given for this setup and the R.D.I. region is characterized when these conditions hold: (i) a Markov Chain X − Y − Z between the source and the side informations; and (ii) S.I. at the encoder does not improve the rate distortion region. • Section IV considers the setting where the eavesdropper's S.I. is available at the decoder ( Figure 1 with the switch closed). We characterize the R.D.I. region when S.I. at the encoder does not improve the rate distortion region. • Section V considers the setting in Figure 2, where the encoder and decoder obtain coded S.I. sent by a helper via a rate-limited link. We present a general achievability scheme for this setting and show that the achievability scheme is optimal for some distortion measures when the source and S.I.s satisfy certain Markov Chain conditions. We also extend our analysis for this setting to the Quadratic Gaussian case, and characterize the R.D.I. regions for some special cases. • In Section VI, we consider the amplification measures listed in the previous paragraph, and show that the R.D.I. regions under the amplification measures are the same as that under log-loss for the settings considered in this paper. Finally, we conclude the paper in Section VII.

II. DEFINITIONS
We will follow the notation in [15]. Throughout this paper, source and side informations (X n , Y n , Z n , W n ) are assumed to be i.i.d.; i.e. p(x n , y n , z n , w n ) = n i=1 p(x i , y i , z i , w i ). We now give definitions for the case when the switch is opened; i.e. only Y n is available at the decoder.
A. Uncoded S.I. case ( Figure 1) An (n, 2 nR ) code for this setup consists of • A stochastic encoder F e that takes (X n , Y n ) as input and generates M ∈ [1 : 2 nR ] according to a conditional pmf p(m|x n , y n ); and • A decoder f D : M × Y n →X n . The expected distortion incurred by the code is given by E d(X n ,X n ) := n i=1 Ed(X i ,X i )/n, where d : X ×X → [0, ∞) is the per symbol distortion measure. The information leakage rate at the eavesdropper is given by I(X n ; M, Z n )/n. A (R, D, ∆) R.D.I. tuple is said to be achievable if there exists a sequence of (n, 2 nR ) codes such that lim sup n→∞ I(X n ; Z n , M ) n ≤ ∆. Enc. Eaves.
Dec. X n R Z n Y nX n I(X n ;M,Z n ) n Fig. 1: Uncoded S.I. at the encoder. When the switch is opened, this figure corresponds to the setting described in Section II-A. When the switch is closed, this figure corresponds to the setting described in Section II-B Enc. Eaves.
Dec. The rate-distortion-information leakage rate (R.D.I.) region is then defined as the closure of all achievable (R, D, ∆) tuples. Remark 2.1: Another definition of uncertainty used by some authors in the case of discrete memoryless sources is the equivocation rate, defined by H(X n |M, Z n )/n. Our information leakage rate definition is equivalent to the equivocation rate, since H(X n )/n = H(X) is fixed.

B. When Z n is also available at the decoder
This setting refers to Figure 1 with the switch closed. When Z n is also available at the encoder, all of the definitions remain the same with the exception of the decoding function, which is now changed to f D : M × Y n × Z n →X n , since the S.I. Z n is also available at the decoder.

C. Rate limited helper case (Figure 2)
The rate limited helper setting is shown in Figure 2. An (n, 2 nR , 2 nRh ) code for this setup consists of • A stochastic helper encoder F h that takes Y n as input and outputs M h ∈ [1 : 2 nRh ] according to the conditional pmf p(m h |y n ); • A stochastic encoder F e that takes (X n , M h ) as input and generates M ∈ [1 : 2 nR ] according to the conditional pmf p(m|x n , m h ); • A decoder f D : M × M h × Z n →X n . The definitions of expected distortion incurred by the decoder and information leakage rate at the eavesdropper are the same as previous setting, with Z n replaced by W n for the information leakage rate. A (R, R h , D, ∆) tuple is said to be achievable if there exists a sequence of (n, 2 nR , 2 nRh ) codes such that (1) and (2) are satisfied. The R.D.I. region is then defined as the closure of all achievable (R, R h , D, ∆) tuples.
Remark 2.2: It should be noted that the rate limited helper setting does not include the previous setting as a special case. The helper encoder is a stochastic encoder. Hence, it can choose to send independent randomness instead of transmitting the Y n sequence to the encoder and the decoder.

D. Side information and rate distortion region
LetỸ n be another i.i.d. random variable such that (X n ,Ỹ n ) ∼ n i=1 p(x i ,ỹ i ). Let R WZ (D) be the rate-distortion function for the Wyner-Ziv setting (see [15,Chapter 11]) where S.I.Ỹ n is available at the decoder only. Let R SI−Enc (D) be the rate-distortion function whenỸ n is also available at the encoder. We say that S.I. at the encoder does not improve the rate-distortion region for side informationỸ n if R WZ (D) = R SI−Enc (D) for all D ≥ D min , where D min is the minimum achievable distortion. We denote this condition by R WZ (Ỹ ) = R SI−Enc (Ỹ ), where R WZ (Ỹ ) is the rate distortion region whenỸ n is available at the decoder only, and R SI−Enc (Ỹ ) is the rate distortion region whenỸ n is available at both the encoder and the decoder. Equivalently, we have R WZ (Ỹ ) ⊆ R SI−Enc (Ỹ ) and R SI−Enc (Ỹ ) ⊆ R WZ (Ỹ ).
The following information-theoretic characterization of R WZ (Ỹ ) = R SI−Enc (Ỹ ) will be useful in the sequel.

III. UNCODED S.I. AT ENCODER AND DECODER WITH SWITCH OPENED
In this section, we present results for the setting in Figure 1 with the switch opened.

A. General inner and outer bounds
Proposition 1: An outer bound to the R.D.I. region for the setting in Figure 1 with the switch opened is given by for some p(x, y, z)p(u, v|x, y) and reconstruction functionx(Y, U, V ) satisfying E d(X,x(Y, U, V )) ≤ D. The cardinalities of U and V may be upper bounded by |U | ≤ |X ||Y| + 2 and |V| ≤ |X ||Y| + 2. Proof of this Proposition is given in Appendix A.
We now present an inner bound (achievability scheme) for this setting.

Proposition 2:
An inner bound to the R.D.I. region for the setting in Figure 1 with the switch opened is given by Proof of Proposition 2 is given in Appendix B. Here, we give some intuition behind the general achievability scheme. The encoder sends two layers of descriptions U n and V n to the decoder, which decodes by successive decoding. This results in rates of I(X; U |Y ) for the first U n layer and I(V ; X|U, Y ) for the second layer. We assume that the eavesdropper is able to decode the U n codeword, resulting in side information (Z n , U n ) at the eavesdropper. S.I. Y n is binned to 2 nRK bins to generated a secret key. This key can be kept secret from the eavesdropper if R K ≤ H(Y |U, V, X, Z), and it is then used to scramble the message sent to the decoder about the V n layer of codewords. This operation increases the uncertainty that the eavesdropper has about the V n codewords. The information leakage rate is then upper bounded by I(X; Z, U ) plus is an upper bound on the leakage rate due to the V n codeword if no scrambling was done, while −R K represents the reduction in the leakage rate due to the secret key scrambling operation.
Remark 3.1: The reader may ask why we did not scramble the first layer of codewords. A straightforward way of scrambling the first layer of codewords as well as the second layer is to define in the inner bound U = ∅ and V ′ = (V, U ). Such a scheme leads to the following R.D.I. trade-off.
Remark 3.2: As a sanity check, it is easy to see that if we set Y = ∅, Propositions 1 and 2 allow us to recover a special case of the result in [3], where S.I. is not available at the encoder. The R.D.I. region in this case is given as for some p(x, y, z)p(v|x, y) and reconstruction functionx(Y, V ) satisfying E d(X,x(Y, V )) ≤ D. The cardinality of V may be upper bounded by |V| ≤ |X ||Y| + 2.

B. R.D.I. regions
Proposition 3: For the setting in Figure 1 with the switch opened, if X − Y − Z and R SI−Enc (Y ) = R WZ (Y ), the R.D.I. region is given by Here, R SI−Enc (D) = min p(x|x,y):E d(X,X)≤D I(X;X|Y ).
Proof of this Proposition follows from tightening the outer bound in Proposition 1 using the two conditions and showing achievability using Proposition 2.
Proof: From Proposition 1, we have (a) follows from the Markov Chain assumption; (b) follows fromX being a function of (V, U, Y ); the final step follows from the fact that R SI−Enc (D) = min p(x|x),E d(X,X) I(X;X|Y ). Similarly, from Proposition 1, a lower bound on R is given by This completes the proof of converse.
Achievability follows from Proposition 2 and the assumption that It is now straightforward to verify that the R.D.I. region stated in the Proposition can be achieved by setting U = ∅, V = V * and using the Markov relation V * − X − (Y, Z). Remark 3.3: The S.I. at the encoder has, in general, dual uses. One use is to allow the encoder to reduce the rate needed to achieve a level of distortion at the decoder, and the other use here is to generate a secret key. There is, in general, a tension between these two uses of the S.I.. The assumption of R SI−Enc (Y ) = R WZ (Y ) removes some of this tension, allowing us to characterize the R.D.I. region under certain conditions. This is a recurring theme in this paper.

C. Examples
We now provide two examples involving canonical sources and distortion measures in information theory that satisfy the two assumptions stated in the previous subsection.
Corollary 1: Let X − Y − Z and Y be an erased version of X. That is Y = X with probability 1 − p e , and e with probability p e . Let |X | = |X | and the distortion measure be the Hamming distance: Then, the R.D.I. region is given by Proof: The proof follows from an application of Proposition 3 and a result in [16,Theorem 6]. Since X − Y − Z by assumption, it remains to check that R SI−Enc (Y ) = R WZ (Y ), which follows from [16,Theorem 6]. Further, [16,Theorem 6] states that R SI−Enc (D) = p e min p(x|x):E d(X,X)≤D/pe I(X;X).
Corollary 2: Let X − Y − Z and let the distortion measure be given by the log-loss distortion [10]. That is, the reconstruction alphabet is a vector representing the set of probability distributions of the source X. Thus,x(x), 1 ≤ x ≤ |X |, represents the x component of the vectorx that gives the estimated probability of X = x. Then, the log-loss measure is defined by With this distortion measure, the R.D.I. region is given by Proof: This result follows again from a straightforward application of Proposition 3. The fact that R SI−Enc (Y ) = R WZ (Y ) for arbitrary discrete memoryless X, Y under logarithmic loss follows from results in [10]. Further, [10] showed that R SI−Enc (D) = [H(X|Y ) − D] + . Remark 3.4: Technically, our proof of achievability in Proposition 2 holds only for bounded distortion measures, and log-loss is not a bounded distortion measure. The proof of achievability can be readily extended to log-loss by perturbing the reconstruction probability distribution, as was done in an earlier version of [17]. Fix a desired p(u, v|x, y) in Proposition 2. For every u ∈ U , v ∈ V and y ∈ Y, define X 1 (u, v, y) := {x : p(x|u, v, y) > 0} and X 0 (u, v, y) := {x : p(x|u, v, y) = 0}. Further, let ǫ > 0 be a number such that ǫ < (1 − ǫ) min u,v,y,x∈X1(u,v,y) p(x|u, v, y). Then, we definê It is then easy to see that the maximum distortion we incur is upper bounded by log(|X |/ǫ). The proof in Proposition 2 can then be applied with this reconstruction function. Following the proof in Proposition 2, let p (n) e be the probability of "error"; that is, the probability that the chosen codewords are not jointly typical with (X n , Y n ) or that the decoder makes an error. Then, for n sufficiently large, the expected distortion under log-loss with the chosen reconstruction function is upper bounded by Since p (n) e → 0 as n → ∞, this completes the proof for the case of log-loss. Remark 3.5: For the case of log-loss, by letting D → 0, we can also recover the lossless source coding case. That is, when the criteria at the decoder is the block error probability P(X n = X n ) → 0 as n → ∞. Proof of this claim follows from Proposition 13 in Section V relating log-loss in this setting to list decoding.
1) Numerical example for Corollary 1: The R.D.I. region is given by for D ≤ p e /2. For D > p e /2, R = 0 and ∆ = 1 − H 2 (p e /2). Here, H 2 (.) represents the binary entropy function. 2) Numerical example for Corollary 2: The R.D.I. region is given by for D ≥ 0. The optimal information leakage rate-distortion tradeoffs for both examples are plotted in Fig. 3.

IV. UNCODED S.I. AT ENCODER AND DECODER WITH SWITCH CLOSED
We now turn our attention to the case where the eavesdropper's side information is also available at the decoder. We note here that this setting is closely related to the setting considered in the previous section. However, this setting cannot be recovered as a special case of the setting in the previous section. One cannot, for example, defineỸ = (Y, Z) as a super-source since that would mean that the eavesdropper's side information would also be available at the encoder. Using the results of this section and the previous section, we show that when R WZ (Y, Z) = R SI−Enc (Y, Z), knowledge of the eavesdropper's side information at the encoder does not change the R.D.I. region (for the setting in Figure 1 with the switch closed).

A. Inner and outer bounds
We first start with an inner bound. Proposition 4: An inner bound to the R.D.I. region for the setting in Figure 1 with the switch closed is given by where R K = min{I(V ; X|U, Y, Z), H(Y |U, V, X, Z)} for p(u, v)p(u, v|x, y) and reconstruction function We omit the proof of this proposition here, as the achievability scheme is largely similar to the achievability scheme of Proposition 2, with the difference being that the decoder has access to side informations (Y n , Z n ). Hence, the decoder uses the side informations Y n and Z n in decoding the codeword from the encoder, as opposed to just using the side information Y n . Similarly, Z n is also used in the reconstruction. The rest of the achievability scheme follows the same steps as that in Proposition 2.
Next, we turn to an outer bound for this setting. Proposition 5: An outer bound to the R.D.I. region for the setting in Figure 1 with the switch closed is given by for some p(x, y, z)p(v|x, y) and reconstruction functionx(Y, The cardinality of V may be upper bounded by |V| ≤ |X ||Y| + 2. Proof of this Proposition is given in Appendix D.

B. R.D.I. regions
Using Propositions 4 and 5, we characterize the R.D.I. regions for sources and distortion measures satisfying R WZ (Y, Z) = R SI−Enc (Y, Z).
Proposition 6: For the setting in Figure 1 with the switch closed, when R WZ (Y, Z) = R SI−Enc (Y, Z), the R.D.I. region is given by Here, R SI−Enc (D) = min p(x|x,y,z):E d(X,X)≤D I(X;X|Y, Z).
Proof: From the outer bound in Proposition 5, we have Similarly, we have Achievability of this outer bound then follows from Proposition 4 and the assumption that We then set U = ∅ and V = V * in the inner bound in Proposition 4 to show the achievability of the outer bound.
Under the condition that R WZ (Y, Z) = R SI−Enc (Y, Z), Proposition 6 and Proposition 3 allow us to show that the R.D.I. region of the setting in Figure 1 does not change even if the eavesdropper's S.I. is available to both the encoder and the decoder. This is stated in the next proposition.
Proposition 7: For the setting in Figure 1 with the switch closed, if R WZ (Y, Z) = R SI−Enc (Y, Z), the R.D.I. region remains unchanged even if Z n is available at the encoder.
Proof: Proof of this Proposition follows quite straightforwardly from Proposition 3. We let the side information observed by the decoder be the super sourceỸ n = (Y n , Z n ). Observe that since X −Ỹ − Z and R WZ (Y, Z) = R SI−Enc (Y, Z) implies that R WZ (Ỹ ) = R SI−Enc (Ỹ ), the results of Proposition 3 holds and the eavesdropper's S.I. Z n now becomes available to both the encoder and the decoder. It is now straightforward to see from Proposition 3 that the R.D.I. region is the same as that given in Proposition 6.

C. Examples
We now give examples of sources and distortion measures satisfying the condition R WZ (Y, Z) = R SI−Enc (Y, Z).
Corollary 3: Let X − Z − Y and Z be an erased version of X. That is Z = X with probability 1 − p e , and e with probability p e . Let |X | = |X | and the distortion measure be the Hamming distance, as defined in Corollary 1. Then, the R.D.I. region is given by Proof: Proof of this Corollary follows similar lines to that of Corollary 1. However, we first show that knowledge of S.I. Y n at both the encoder and the decoder does not improve the rate-distortion region, when S.I. Z n is also known at the encoder and decoder and X −Z −Y form a Markov Chain. When S.I.s Z n and Y n are known at both the encoder and the decoder, the rate distortion function, R SI−Enc (D), is given as where the minimization is over p(x|x, y, z) satisfying E d(X,X) ≤ D. Note now that using the Markov Chain X − Z − Y , we have that I(X;X|Y, Z) ≥ I(X;X|Z). Since I(X;X|Z) and E d(X,X) depend on only the marginal p.m.f. p(x, z,x), the rate distortion function can be equivalently written as Hence, S.I. Y n does not improve the rate-distortion region when the Markov Chain X − Z − Y holds, and we have Finally, we apply Proposition 6 and [16, Theorem 6] to obtain the R.D.I. region in Corollary 3. Remark 4.1: In this example, the eavesdropper's S.I., Z n , is of higher quality than the S.I. observed by the encoder and decoder, Y n . Y n therefore plays no role in reducing the achievable rate for a given distortion. However, because Y n is observed at both the encoder and decoder, it can still help to reduce the information leakage rate, despite it being a degraded version of Z n . Our next example deals with the case where both Y and Z are erased versions of X.
Corollary 4: Let Y be an erased version of X. That is Y = X with probability 1 − p e,y , and e with probability p e,y . Similarly, let Z be an erased version of X, independent of Y conditioned on X. That is Z = X with probability 1 − p e,z , and e with probability p e,z . Let |X | = |X | and the distortion measure be the Hamming distance as defined in Corollary 1. Then, the R.D.I. region is given by Proof: Similar to Corollary 3, we use Proposition 6 to prove this result. It remains to check that R SI−Enc (Y, Z) = R WZ (Y, Z) when Y and Z are both erased versions of X. This fact is a straightforward extension of the arguments in [16,Theorem 6]. We therefore omit it here.
Remark 4.2: It may be of interest to compare Corollary 4 to the setting in Figure 1 when the switch is opened, with the side information at the decoder being replaced by the following erased side information: Y = X with probability 1 − p e,y p e,z and e with probability p e,y p e,z , and X −Ỹ − Z. In this case, from Corollary 1, the R.D.I. region is given by R open ≥ p e,y p e,z I(X;X), ∆ open ≥ max{I(X; Z), I(X; Z) + p e,y p e,z I(X;X) − H(Ỹ |X, Z)} for 0 ≤ D ≤ p e,y p e,z , p(x|x) such that E d(X,X) ≤ D/(p e,y p e,z ). In this case, the expression for R open is the same as that for R in Corollary 4. This is to be expected since, for rate distortion, observing two erased side informations Y and Z is equivalent to observing a higher quality erased side informatioñ Y . However, the information leakage rate expressions are different, since H(Ỹ |X, Z) is in general not equal to H(Y |Z). Hence, due to the required Markov Chain assumption (X −Ỹ − Z) in Corollary 1, the result in Corollary 4 cannot be recovered from Corollary 1 by simply assuming a higher quality erased side information at the decoder.
Our final example deals with the setting under log-loss. Corollary 5: For the setting in Figure 1 with the switch closed, let the distortion measure be given by the log-loss distortion as defined in Corollary 2. The R.D.I. region is given by Proof: The proof follows similar lines to the proof in Corollary 2, with the role of Proposition 3 being replaced by Proposition 6. The fact that R SI−Enc (Y, Z) = R WZ (Y, Z) follows again from results in [10], by consider (Y, Z) as a super sourceỸ . Further, using the results in [10]

Numerical examples for Corollaries 3, 4 and 5
We now give numerical examples for the three corollaries. For all three examples, we assume that X ∼ Bern(0.5).
1) Numerical example for Corollary 3: We let Z = X with probability 1 − p e and e with probability p e , with p e = 0.8. Y ∈ {0, 1} with P(Y = 0|Z = 0) = 1, P(Y = 1|Z = 1) = 1 and P(Y = 0|Z = e) = 0.9. The R.D.I. region is given by for D ≤ p e /2. R = 0 and ∆ = 1 − p e for D > p e /2. 2) Numerical example for Corollary 4: We let Z = X with probability 1 − p e,z and e with probability p e,z , with p e,z = 0.8. We let Y = X with probability 1 − p e,y and e with probability p e,y , with p e,y = 0.9. The R.D.I. region is given by for D ≤ p e,y p e,z /2. R = 0 and ∆ = 1 − p e,z for D > p e,y p e,z /2. 3) Numerical example for Corollary 5: We let Z = X with probability 1 − p e,z and e with probability p e,z , with p e,z = 0.8. We let Y = X with probability 1 − p e,y and e with probability p e,y , with p e,y = 0.9. The R.D.I. region under log-loss is given by The optimal information leakage rate-distortion tradeoffs for all three examples are plotted in Fig. 4.

V. RATE-LIMITED HELPER SETTING
In this section, we consider the rate-limited helper setting in Figure 2.

A. General inner bound
Proposition 8: An inner bound to the R.D.I. region for the rate limited helper setting in Figure 2 is given by Proof of this proposition is given in Appendix E. Here, we give an outline of the proof. The proof follows similar lines to that in Proposition 2, with the encoder sending two layers of descriptions U n and V n to the decoder. The main differences are in the actions of the helper and how the secret key is being generated. To reduce R, the helper sends a description U n h to both the encoder and the decoder. To ensure that both the encoder and the decoder can decode U n h , we require The secret key is generated in two parts. The first part of the secret key comes from the codeword U n h . A secret key of rate R K can be generated by random binning of the U n h codewords if Next, the helper can also use its own randomness and the remaining rate to send to the encoder and the decoder a uniform random variable of size up to 2 n(Rh−max{I(Uh;Y |Z),I(Uh;Y |X))} as a second secret key. Hence, These two keys are then used to scramble the message sent on the rate limited link about the second layer of description V n , which is of rate I(X; V |U h , Z, U ), resulting in the requirement that R K + R ′ K ≤ I(X; V |Z, U h , U ). In this achievability scheme, there is a tradeoff between the amount of secret key generated and the quality of the description that the helper sends to reduce the rate required by the encoder. The independent randomness sent on the helper link reduces the amount of information leakage through secret key scrambling, but does not help to reduce the distortion at the decoder. While we can generate another secret key using the helper codeword, U n h , the rate of the key that can be generated is usually not as large as it would be if uniform randomness is used. In some cases such as those in the next subsection, the tradeoff is tight.

B. R.D.I. regions for discrete memoryless source and S.I.s
We now consider some special cases in which the achievability scheme in Proposition 8 is optimal. Proposition 9: For the setting in Figure 2, if Y − X − Z − W and the distortion measure is log-loss distortion (see definition in Corollary 2), then the R.D.I. region is given by This result generalizes some of the results found in [2]. By setting W = ∅ and D = 0 1 , we recover [2, Theorem 4] and by setting Z = ∅ as well, we recover [2, Theorem 2].
Proof: Achievability of the R.D.I. region in Proposition 9 for D ≤ H(X|U h , Z) follows from Proposition 8 by setting U = ∅, V to be the following random variable The reconstruction function is given byx(u h , v, z) := p(x|u h , v, z) and it can be verified that this The achievable leakage rate is then given by For the proof of the converse, the identification of the auxiliary random variable U h and lower bounds for the rates R and R h follow steps similar to those in [18]. Further, we will use the following lemma for log-loss found in [17].
Given an (n, 2 nR , 2 nRh ) code that achieves 1 See Remark 3.5 and Proposition 13 (a) follows from the Markov chain can be readily shown using techniques in [18].
The last step follows from an application of Lemma 1. For the information leakage term, we have (a) follows from the Markov Chain assumption Y n − X n − Z n − W n ; i.e.
Chain. Noting that ǫ n → 0 as n → ∞, we arrive at the required bound stated in the Proposition. The cardinality bound on U h follows from standard techniques [15,Appendix C].
The next result presents another case in which Proposition 8 is optimal under a different Markov Chain condition, and for a class of distortion measures that include log-loss.
Proposition 10: For the setting in Figure 2 , then the R.D.I. region is given by Here, R SI−Enc (D) = min p(x|x,z):E d(X,X)≤D I(X;X|Z). Proof of this proposition is given in Appendix G. In this setting, side information at the decoder is of higher quality than the side information at the encoder. Since we assume that R WZ = R(SI − Enc), any side information sent by the helper does not help to reduce the rate required to achieve a required distortion at the decoder. The helper's only role is to generate a secret key to reduce the information leakage rate. Hence, in this case, there is no tradeoff in the role of the helper between sending a higher quality description versus sending a secret key to reduce the information leakage rate.
Remark 5.1: It may be of interest to note that the achievability scheme in this proposition relies on a helper with enough independent randomness to generate a secret key of size 2 nRh . The side information Y n is completely ignored. If, however, the helper is stochastically constrained, in the sense of [19], then Y n may be used to generate an additional secret key. A complete characterization of the R.D.I. region for the case of a stochastically constrained helper is, however, an open question to the best of our knowledge.
Using Proposition 10, we have the following two examples for erased side information and Hamming distortion, and log-loss distortion.
Corollary 6: For the setting in Figure 2, if Y − W − Z − X, Z = X with probability 1 − p e and Z = e with probability p e and the distortion measure is Hamming distortion, then the R.D.I. region is given by Proof: The proof follows straightforwardly from Proposition 10. The fact that R SI−Enc (Z) = R WZ (Z) and R SI−Enc (D) = min p(x|x):E d(X,X)≤D/pe p e I(X;X) follow from [16].

C. Quadratic Gaussian setting
Following the approach in [20] (see also [18]), we can extend this setting and analysis to the Quadratic Gaussian case. In this subsection, we consider the sources as zero mean Gaussian sources satisfying the Markov Chain assumption, and the distortion measure is given by the squared distortion measure.
In a close analog to the case of Proposition 9 for log-loss, we have the following result for the Quadratic Gaussian setting.
Proposition 11: For the setting in Figure 2 To avoid degenerate cases, we assume that σ 2 W , σ 2 A , σ 2 B , σ 2 C > 0. Let the distortion measure be the squared distortion d(x,x) := (x −x) 2 . Then, for fixed R h and D, the R.D.I. region is given by Proof: We begin with the converse. For any sequence of (n, 2 nR , 2 nRh ) code that achieves distortion D, the minimum rate required in the absence of any information leakage constraint is lower bounded by [18, Corollary 12] On the other hand, consider now a sequence of (n, 2 nR , 2 nRh ) codes that achieves (D, ∆). For an (n, 2 nR , 2 nRh ) code that achieves (D + ǫ n , ∆ + ǫ n ), we have the straightforward bound of We also have, following the same arguments as in the converse proof for Proposition 9 (see inequality (3)), n∆ + nR h + nǫ n ≥ I(X n ; W n ) + I(X n ; M, M h |Z n ).
We now further lower bound this term by Hence, h(X −X) ≤ 1 2 log 2πeD + ǫ n . Finally, since ǫ n → 0 as n → ∞, we obtain the following bound on ∆.
We now turn to the achievability proof for the lower bounds for R and ∆ in inequalities (4) and (5), respectively. We use Proposition 8 and set are independent Gaussian random variables. These definitions result in the Markov Chain V − X − (U h , Y, Z, W ). We setX = E(X|U h , V, Z). It suffices to consider only the case of X|Uh,Z − D With these definitions, we have the following quantities.
It is now straightforward to verify that the achievability scheme in Proposition 8 achieves the outer bound with these choice of auxiliary random variables, which completes the proof.
Similarly, in a close analog to Corollary 7, we have the following R.D.I. characterization for another Quadratic Gaussian setting. Proposition 12: For the setting in Figure 2, let X ∼ N (0, σ 2 X ), Z = X + A, W = Z + B, Y = W + C, and A ∼ N (0, σ 2 A ), B ∼ N (0, σ 2 B ) and C ∼ N (0, σ 2 C ) be mutually independent Gaussian random variables, and the distortion measure be squared loss. To avoid degenerate cases, we assume that Then, the R.D.I. region is given by Proof of this Proposition is given in Appendix H.

VI. AMPLIFICATION MEASURES
We now turn our attention to source amplification measures at the decoder. Instead of symbol by symbol distortion measures like those considered in the previous sections, we consider the following two amplification measures. Let U n dec be the overall information at the decoder, which includes the decoder's S.I. and the message(s) received.
• List constraint: Based on the decoder's information, it forms a list, L(U n dec ), of x n sequences such that |L(U n dec )| ≤ 2 nD and P(X n ∈ L(U n dec )) → 1 as n → ∞. The list constraint is a straightforward generalization of lossless source coding, with D = 0 corresponding to the lossless case.
• Entropy constraint: Here, we wish to ensure that lim sup n→∞ 1 n H(X n |U n dec ) ≤ D. The entropy constraint can be shown to be equivalent to block log-loss constraint [12]. That is, the decoder's reconstruction vector is the set of all probability distributions over |X | n , and the distortion is measured by log(1/x(x n ))/n, wherex(x n ) is the estimated probability of X n = x n . Block log-loss is a strengthening of the symbol-by-symbol log-loss distortion measure defined in Corollary 2 since it allows more general probability distributions over |X | n instead of only product distributions (in the case of symbol by symbol log loss). We now consider how the R.D.I. regions change when we replace log-loss distortion constraint with the amplification measures.
Proposition 13: For the settings in Corollaries 2, 5 and 7, and Proposition 9, the R.D.I. regions remain unchanged if the log-loss distortion measure at the decoder is replaced by a list or entropy constraint.
For the case of entropy constraint (or block log-loss), Proposition 13 states that even if we allow more general probability distributions than the product distributions for symbol-by-symbol log-loss, there is no gain in the R.D.I. regions for our settings. In the case of list constraint, it relates achievable distortion under log-loss to the exponent of the achievable list size, and also provides a way of recovering results for lossless source coding from results for log-loss distortion measure with D set to zero.
Proof: In our proof, we will use the following lemma found in [14], adapted to our notation. Lemma 2: Let L(U n dec ) be a sequence of list decoders such that P(X n / ∈ L(U n dec )) → 0 as n → ∞. Then, H(X n |U n dec ) ≤ log |L(U n dec )| + nǫ n , where ǫ n → 0 as n → ∞.

Achievability under list decoding
We now show the achievability of Corollaries 2, 5 and 7, and Proposition 9, when the log-loss constraint at the decoder is replaced by a list constraint, with log |L(U n dec )| ≤ nD. Let V n dec denote all the codewords decoded and the original side information at the decoder for Corollary 2 and Propositions 3 and 4. In the achievability scheme of Corollaries 2, 5 and 7, and Proposition 9, recall that our scheme results in P((V n dec , X n ) ∈ T (n) ǫ ) → 1 as n → ∞. The list decoder forms the following list: L(v n dec ) := {x n : (x n , v n dec ) ∈ T (n) ǫ }. From properties of typical sequences (see [15,Chapter 2]), we have that The last step follows from the choice of auxiliary random variables in Corollaries 2, 5 and 7, and Proposition 9. The requirement that P(X n ∈ L(V n dec )) → 1 as n → ∞ follows from P((V n dec , X n ) ∈ T (n) ǫ ) → 1 as n → ∞ in our achievability scheme.

Achievability under entropy constraint
Achievability under entropy constraint is a straightforward consequence of achievability under list constraint and Lemma 2. Since we have a sequence of list decoders satisfying the conditions in Lemma 2,

Converse
From Lemma 2, any code under list constraint that achieves a list size of D list is also a code that achieves a block log-loss (or entropy constraint) of at most D list − ǫ n . Hence, any outer bound for our settings under entropy constraint is also an outer bound for our settings under the list constraint. We therefore only need to consider outer bounds for our settings under the entropy constraint in the converse.
With the above observation, recall that in our proof of converse for Proposition 9, a key property of log-loss that we used is the fact that log-loss distortion upper bounds the entropy of the source sequence given the overall side information at the decoder (see Lemma 1). Similar to log-loss, given a code with entropy constraint of D entropy , we have, by definition, the following upper bound on the entropy of the source sequence given the overall side information at the decoder.
1 n H(X n |U n dec ) ≤ D entropy .
It can be verified that our converse proof for Proposition 9 continues to hold under the entropy constraint with the upper bound in Lemma 1, 1 n H(X n |U n dec ) ≤ D log−loss , being replaced by inequality (6). For Corollaries 2, 5 and 7, the upper bound 1 n H(X n |U n dec ) ≤ D log−loss was used implicitly in the proofs of converse, and similarly, it can be verified that the proof of converse continues to hold with inequality (6) for the entropy constraint case. The details are given in Appendix I.
Remark 6.1: The property R SI−Enc (Ỹ ) = R WZ (Ỹ ) enjoyed by the log-loss distortion measure was used to obtain the R.D.I. regions under log-loss for Corollaries 2, 5 and 7. Using inequality (6) and Lemma 1, we can show that the same property also holds true under block log-loss or list constraint. This property can also be used to give proofs of converse for Corollaries 2, 5 and 7, similar to what was done in the log-loss case.

VII. CONCLUSION
We considered the setting of secure lossy source coding when either coded or uncoded S.I. is available at the decoder. For the case of uncoded side information, we considered two related settings. Our first setting considered the case where the eavesdropper's S.I. is not available at the decoder. We gave general inner and outer bounds for this setup, and characterized the R.D.I. region for some special cases. We then considered the second uncoded S.I. setting where the eavesdropper's S.I. is also available to the decoder. For this case, we again give general inner and outer bounds for this setting and characterized the R.D.I. region for some special cases. The main idea used in the achievability proofs for these settings is in the generation of a secret key, via binning the S.I. at the encoder and the decoder, to reduce the information leakage rate at the eavesdropper. This idea can also be used in other secure source coding settings [21]. A recurring theme in the special cases for which we were able to find the R.D.I. regions is that the source, S.I.s and distortion measure satisfy the condition that S.I. at the encoder does not improve the rate-distortion region.
We then considered the case of coded S.I. at the encoder and decoder. For this case, we gave an achievability scheme for the general setting that used the idea of generating a secret key from the coded S.I., as well as the helper generating an independent secret key for both the encoder and the decoder. We characterized the R.D.I. regions for several settings and recovered previous results in the literature as special cases of our settings. Finally, we considered two amplification measures for the decoder, listdecoding and entropy minimization, and showed that the R.D.I. regions under these measures coincide with the R.D.I. region under per symbol log-loss for the cases we considered in this paper. Given a (n, 2 nR ) code that achieves (D + ǫ n , ∆ + ǫ n ), define the auxiliary random variables A lower bound on the rate is then given by nR ≥ H(M ) The last step follows from the definition of U i and V i . (a) follows from (X n , Y n ) being generated i.i.d. and (b) follows from the Markov Chain Z n i+1 − (M, X n i+1 , Y n i+1 , Y i ) − X i . For the information leakage term, we have n∆ + ǫ n = I(X n ; M, Z n ) (a) follows from the Csiszár Sum lemma. The lower bound is straightforward to show. Now, let Q ∼ U [1 : n] be the time-sharing random variable that is independent of all other random variables. Finally, we consider the bound on distortion. We have Hence, the choice of auxiliary random variables satisfy the distortion constraint with reconstruction functionx ′ . Next, noting that ǫ n → 0 as n → ∞ then gives us the required bound. The Markov Chain condition (U, V ) − (X, Y ) − Z follows from the definition of the auxiliary random variables and is straightforward to verify.
It remains to give upper bounds on the cardinalities of U and V . The stated bounds follow straightforwardly from the cardinality bounding techniques in [15, Appendix C] and we omit them here.

APPENDIX B PROOF OF PROPOSITION 2
We give a proof of the lower bound, with details for the fairly standard decoding steps left out of the proof. In our proof, we will use the following lemma.
Lemma 3: Fix ǫ > 0. Let Y n ∼ n i=1 p(y i ) and let W n be a random variable such that P((Y n , W n ) ∈ T (n) ǫ (Y, W )) → 1 as n → ∞. Bin the set of all |Y| n sequences to 2 nRK bins uniformly at random, and let K be the bin index such that Y n ∈ B(K).
Proof of this lemma is given in Appendix C. We note here that the special case of R K = 0 will be used several times in the proofs of this proposition and Proposition 8.

Codebook generation
We generate two codebooks, the rate-distortion codebook and the key generation codebook. We first start with the rate distortion codebook, C RD .
• Randomly and uniformly bin the set of Y n sequences to 2 nRK bins, B K (m k ), where R K := min{H(Y |U, V, X, Z), I(V ; X|U, Y )} and m k ∈ [1 : 2 nRK ]. We use C := {C RD , C K } to denote the combined codebook.

Encoding
• Given sequences (x n , y n ), the encoder first looks for a sequence u n (l 0 ) such that (u n (l 0 ), x n , y n ) ∈ T (n) ǫ . If there is more than one such sequence, the encoder selects one sequence uniformly at randomly from the set of jointly typical u n sequences. If there is none, the encoder randomly and uniformly selects a sequence u n from the set of all sequences. • Next, the encdoer looks for a v n (l 1 , l 0 ) such that (v n (l 1 , l 0 ), u n (l 0 ), x n , y n ) ∈ T (n) ǫ . If there is more than one such sequence, the encoder selects one sequence uniformly at random from the set of jointly typical v n sequences. If there is none, the encoder randomly and uniformly selects a sequence v n from the set of all sequences. • The encoder then looks for the index m k such that y n ∈ B K (m k ).
• Finally, the encoder sends out the indices m 0 , m 1o and m 1s ⊕ m k 2 , resulting in a rate of I(X; U, V |Y ) + 6δ(ǫ).

Analysis of distortion
Since the decoder has the sequence y n , it first finds m k to unscramble m 1s ⊕ m k , thereby recovering the index m 1 . It then decodes the codewords u n (L 0 ) and v n (L 0 , L 1 ) using successive decoding. That is, it first looks for al 0 such that (u n (l 0 ), y n ) ∈ T (n) ǫ and u n (l 0 ) ∈ B(m 0 ). An error occurs if there is no suchl 0 . Next, it then looks for al 1 such that (v n (l 1 ,l 0 ), u n (l 0 ), y n ) ∈ T (n) ǫ and v n (l 0 ,l 1 ) ∈ B(m 1 ,l 0 ). Similarly, an error occurs if there is no suchl 1 . The analysis of the probability of error follows quite straightforwardly from the analysis for the Wyner-Ziv setting in [15,Chapter 11], and we will omit it here. From the rates given in the codebook generation and encoding process, it can be shown that the probability of error (l 0 = L 0 orl 1 = L 1 ), averaged over codebooks, goes to zero as n → ∞.

Analysis of information leakage rate
For notational convenience, we will use δ(ǫ) to denote all terms that go to zero as ǫ → 0, or n → ∞.
We now bound each of the terms separately.
The final step uses the Markov relation U − (X, Y )− Z. In (a), we applied Lemma 3 to H(Z n |U n (L 0 )). The condition that P((U n (L 0 ), Z n ) ∈ T (n) ǫ ) → 1 as n → ∞ follows from the rates given, the codebook generation and encoding process, and the conditional typicality lemma and covering lemma in [15]. For the second term, we have In (a), we apply Lemma 3 to H(Y n |X n , Z n , U n (L 0 ), V n (L 0 , L 1 ), M k ). To check that the conditions for applying Lemma 3 are satisfied, observe that ǫ ) → 1 follows again from the rates given and the encoding process. In the final step, we upper bound H(L 1 |X n , Z n , L 0 , C) as follow. ≤ nI(V ; X, Y |U ) + H(X n , Z n |U n (L 0 ), V n (L 0 , L 1 )) − nH(X, Z) + nI(U ; X, Y ) (a) and (b) follow from applying Lemma 3 to the terms H(X n , Z n |U n (L 0 ), V n (L 0 , L 1 )) and H(Y n |U n (L 0 ), X n , Z n ) respectively. The final step uses the Markov condition (V, U ) − (X, Y ) − Z and hence, I(V, U ; X, Y ) = I(V, U ; X, Y, Z). (8) and (9) into (7) then leads us to

Combining the bounds in
Hence, any ∆ ′ > ∆ is achievable.

APPENDIX D PROOF OF PROPOSITION 5
Given a (n, 2 nR ) code that achieves (D + ǫ n , ∆ + ǫ n ), define the auxiliary random variables where (a) follows from the fact that the sources are i.i.d.. Next, for the information leakage rate n∆ + nǫ n = I(X n ; M, Z n ) = I(X n ; Z n ) + I(X n ; M |Z n ) = I(X n ; Z n ) + I(X n ; M, Y n |Z n ) − I(X n ; Y n |M, Z n ) = I(X n ; Z n ) + I(X n ; Y n |Z n ) + I(X n ; M |Y n , Z n ) − I(X n ; Y n |M, Z n ) = I(X n ; Z n ) + I(X n ; M |Y n , Z n ) + I(X n ; Y n |Z n ) − I(M, X n ; Y n |Z n ) + I(M ; Y n |Z n ) Next, we let Q ∼ U [1 : n] and define V = (V Q , Q), X Q = X, Y Q = Y , Z Q = Z. For the distortion, we have Then, noting that ǫ n → 0 as n → ∞ and using the i.i.d. property of the source and S.I., we obtain the bounds stated in the proposition. The Markov Chain condition V − (X, Y ) − Z follows from the definition of V and is easy to verify. The cardinality bound for V follows from standard arguments [15, Appendix C] and we omit it here.

APPENDIX E PROOF OF PROPOSITION 8
We first state the following lemma that we will use in our analysis of information leakage rate in our proof. The proof of this lemma is given in Appendix F.
Lemma 4: Fix ǫ > 0. Let U n (l), l ∈ [1 : 2 nR ] be generated according to n i=1 p(u i ). LetW n be a random variable and assume that there exists a random variable L ∈ [1 : 2 nR ] such that P((U n (L),W n ) ∈ T (n) ǫ ) → 1 as n → ∞. Bin the U n (l) sequences uniformly at random to 2 nRK bins, B(k), k ∈ [1 : 2 nRK ]. Let K be the index such that U n (L) ∈ B(K). For n sufficiently large, let δ 1 (ǫ ′ ) be a function of ǫ ′ , where ǫ ′ > ǫ, such that: We will also use Lemma 3, stated in Appendix B, in our analysis. Now, we turn to the achievability proof. We assume in our proof that I(U h ; Y |Z) ≥ I(U h ; Y |X). The proof when the inequality is reversed follows the same arguments, and is omitted.

Codebook generation
We start with the codebook generation at the helper.

Probability of error in encoding
In our achievability scheme, we require that P((U n h (L h ), U n (L 0 ), V n (L 0 , L 1 ), X n , Y n , Z n , W n ) ∈ T (n) ǫ ) → 1 as n → ∞. Let E 1 denote the event (U n h (L h ), U n (L 0 ), V n (L 0 , L 1 ), X n , Y n , Z n , W n ) / ∈ T (n) ǫ . Therefore, P(E 1 ) denotes the probability of overall encoder error. Let E 0 denote the event that We know from the preceding analysis that To do so, we will use the Markov lemma in [15,Chapter 12] stated as follow.

Consider now the term
Observe from the encoding process that (V n (L 0 , L 1 ), U n (L 0 )) →Ỹ n →X n . Hence, we now apply the Markov lemma to show that P((V n (L 0 , L 1 ), U n (L 0 ),x n ,ỹ n ) / ∈ T (n) ǫ ) → 0 for every (x n ,ỹ n ) ∈ T (n) ǫ ′ . Condition 1 of the Markov lemma holds since from the rates given, codebook generation process, encoding process and standard analysis using the covering lemma of [15,Chapter 3], P(((V n (L 0 , L 1 ), U n (L 0 ),ỹ n ) ∈ T (n) ǫ ′ ) → 1 as n → ∞. Next, we check that the second condition holds. The analysis closely follows that used in [15,Chapter 12,Lemma 12.3], and we omit the details here. P(V n (L 0 , L 1 ) = v n , U n (L 0 , L 1 ) = u n |ỹ n ) = P(U n (L 0 ) = u n |u n h , x n ) P(V n (L 0 , L 1 ) = v n |u n , u n h , x n ) Hence, P(E 1 |(x n ,ỹ n )) → 0 as n → ∞ and therefore, P(E 1 |E c 0 ) → 0 as n → ∞. We note here that our analysis also implies that P((U n h (L h ), U n (L 0 ), V n (L 0 , L 1 ), X n , Y n , Z n , W n ) ∈ T (n) ǫ ) → 1 as n → ∞. This fact will be used in our analysis of information leakage rate.

Decoding and analysis of distortion
• The decoder first decodes the codeword from the helper by looking for an unique u n h (l h ) such that (u n h (l h ), z n ) ∈ T (n) ǫ , and u n h (l h ) ∈ B h (m h ). The probability of error in this step goes to zero with n since R h > I(U h ; Y |Z).
• The decoder next looks for them k such that u n h (l h ) ∈ B K (m k ). • It then unscrambles the indices m 1s and m ′ 1s by unscrambling m 1s ⊕ m k and m ′ 1s ⊕ m ′ k usingm k and m ′ k respectively. • Finally, the decoder decodes the codewords u n (L 0 ) and v n (L 0 , L 1 ) using the indices m 0 and m 1 by successive decoding (see decoding and analysis of probability of error in proof of Proposition 2). The analysis of the probability of error follows quite straightforwardly from the analysis for a similar setting in [18], and we will omit it here. Finally, for the distortion constraint, similar to the proof in Proposition 2, we note that since the probability of encoding error or decoding error goes to zero as n → ∞, the expected distortion, averaged over codebooks, is less than or equal to D + δ(ǫ) as n → ∞ [15,Chapter 3].

Analysis of information leakage rate
For notational convenience, we will use δ(ǫ) to denote all terms that go to zero as ǫ → 0, or n → ∞. We will also suppress the indices for the codewords. Hence, U n h (L h ) = U n h , U n (L 0 ) = U n and V n (L 0 , L 1 ) = V n . Note also that in our analysis, the manipulation of mutual information and entropy quantities will use the three Markov relations: Z) ) stated in the Proposition. For brevity, we will not state these relations explicitly in the analysis, but indicate by the labels (MC1, MC2, MC3) whether MC1, MC2 or MC3 is used in the steps in the analysis.
Similar to Proposition 2, we analyze the two terms in (12) separately. For the first term, an additional term comes up due to independent randomness.
(13) (a) uses the fact that M ′ 1s ⊕M ′ K is independent of all other random variables due to M ′ K being uniformly distributed and independent of other random variables. (b) follows from application of Lemma 3 (see proof of Proposition 2 in Appendix B) to the third term. The conditions required for application of Lemma 3 are satisfied as, from the rates given and the encoding process, P((U n h , U n , V n , X n , Y n , Z n , W n ) ∈ T (n) For the second term, we have (a) follows from application of Lemma 3 to the third term. It is again straightforward to verify that the conditions required for application of Lemma 3 are satisfied from the rates given and the encoding process.
(b) follows applying Lemma 4 to the last term, withR = I(U h ; Y ) + 3δ(ǫ), R K ≤ I(U h ; Y ) − I(U h ; X, W, U, V ) andW = (X, W, U, V ). The conditions required for application of Lemma 4 in (b) follow from the rates given and the encoding process.
In (c), we upper bound H(L 1 |X n , W n , L 0 , M 1o , M 1s ⊕ M K , C) as follow.
H(L 1 |X n , W n , L 0 , M 1o , M 1s ⊕ M K , C) ≤ H(L 1 |X n , W n , L 0 , C) (i) and (ii) follow from application of Lemma 3. Combining the bounds for the two terms in (13) and (14) into (12) then leads to the upper bound on the information leakage rate, which then completes the proof of achievability for Proposition 8.
and 0 otherwise. Observe that by assumption, P(E 2 = 1) → 0 as n → ∞. We now focus on upper bounding E 1 .
Now, we use a version of the Chernoff bound, found in [15,Appendix B]. Let X 1 , X 2 , X 3 , . . . , X m be i.i.d. binary random variables with P(X j = 1) = p. Then, P   m j=1 X j ≥ m(1 + δ)p   ≤ exp(−δ 2 mp/4) for δ ∈ (0, 1). Now, let m = 2 nR and let X j be the indicator function of the event {U n (j) ∈ B(k), (U n (j),w n ) ∈ T (n) ǫ ′ }. We note that X j s are i.i.d. binary random variables since the binning is done uniformly at random and U n (j) is generated according to n i=1 p(u i ) for all j. Next, since the binning is done uniformly at random, independent of all other random variables, P(X j ) = P(U n (j) ∈ B(k)). P((U n (j),w n ) ∈ T (n) ǫ ′ ). Hence, p = 2 −nRK P((U n (j),w n ) ∈ T (n) ǫ ′ ) ≥ 2 −nRK 2 −n(I(U ;W )+δ1(ǫ ′ )) for n sufficiently large. The second step follows from the statement of lemma 4, which, in turn, follows from the conditional typical lemma [15,Chapter 2].
Applying the Chernoff bound to (15) with a = (1 + δ)mp, we obtain for n sufficiently large.

APPENDIX G PROOF OF PROPOSITION 10
For the converse, consider an (n, 2 nR , 2 nRh ) code achieving (D + ǫ n , ∆ + ǫ n ). The lower bound on R h is trivial. For R, we have I(X i ;X n |Z n , X i−1 ) In (a), we used the Markov Chain assumption Y − W − Z − X. (b) follows from the fact that sources are i.i.d.. For the information leakage rate, the lower bound n∆ + nǫ n ≥ n i=1 I(X i ; W i ) is straightforward to show. We also have n∆ + nR h + nǫ n ≥ I(X n ; M, W n ) + H(M h ) = I(X n ; W n ) + I(X n ; M |W n ) + H(M h ) (a) = I(X n ; W n ) + I(Z n , X n ; M |W n ) + H(M h ) ≥ I(X n ; W n ) + I(X n ; M |Z n , W n ) + H(M h ) ≥ I(X n ; W n ) + I(X n ; M, W n |Z n ) − I(X n ; W n |Z n ) + H(M h )  The last step follows from E n i=1 d(x i ,x i )/n = E d(X,X) ≤ D+ǫ n and the fact that R SI−Enc (D+ǫ n ) = min I(X;X|Z), where we minimize over p(x|x, z) satisfying E d(X,X) ≤ D + ǫ n . Similarly, we have n∆ + nR h + nǫ n ≥ nI(X; W ) + nR SI−Enc (D + ǫ n ).
Finally, noting that ǫ n → 0 as n → ∞ and using the fact that R SI−Enc (D) is continuous in D [15,Chapter 11], we obtain the stated bound in the Proposition. This completes the proof of converse.
For the achievability, we use Proposition 8 and set U h = ∅ and U = ∅. Using the assumption that R SI−Enc (Z) = R WZ (Z), there exists an auxiliary random variable V * such that V * − X − Z, I(V * ; X|Z) = R SI−Enc (D) and E d(X,x(V * , Z)) ≤ D for some reconstruction functionx(V * , Z). We set V = V * in Proposition 8. It is now straightforward to verify that Proposition 8 achieves the stated R.D.I. region.

APPENDIX H PROOF OF PROPOSITION 12
For the converse, using the fact that Y − W − Z − X and following the same steps as the proof of converse for Proposition 10 in Appendix G, we can show that Hence, the outer bound reduces to For the achievability, using Proposition 8, we set U = U h = ∅ and let σ 2 X|Z = σ 2 X|Z . Then, we have V − X − (Z, W, Y ) and it is straightforward to verify that the Proposition 8 achieves R.D.I. region with this choice of auxiliary random variables. The case of D > σ 2 X|Z is straightforward and this completes the proof.
The last step uses the Markov Chain assumption X − Y − Z and inequality (6) on H(X n |Y n , M ). Noting that ǫ n → 0 as n → ∞ then completes the proof of converse.
Further, following the same arguments to the proof of converse for Corollary 2 under block log-loss in the previous section, n∆ + nǫ n ≥ nI(X; Z) + nH(X|Y, Z) − nD − nǫ n − nH(Y |X, Z).
Noting that ǫ n → 0 as n → ∞ then completes the proof of converse.

Proof of converse for Corollary 7 under block log-loss
Given a (n, 2 nR , 2 nRh ) code that achieves (D + ǫ n , ∆ + ǫ n ), we have nR h ≥ 0, n∆ + nǫ n ≥ nI(X; Z). The last step follows from Y −W −Z −X and inequality (6). For the information leakage rate, following the proof of converse for Proposition 10 in Appendix G we have n∆ + nR h + nǫ n ≥ I(X n ; W n ) + I(X n ; M, M h |Z n ) ≥ nI(X; W ) + nH(X|Z) − nD − nǫ n .
The last step follows from inequality (6). Noting that ǫ n → 0 as n → ∞ then completes the proof of converse.