Printer Friendly

Wiretap channel in the presence of action-dependent states and noiseless feedback.

1. Introduction

Equivocation was first introduced into channel coding by Wyner in his study of wiretap channel [1], see Figure 1. It is a kind of degraded broadcast channels. The object is to transmit messages to the legitimate receiver, while keeping the wiretapper as ignorant of the messages as possible.

After the publication of Wyner's work, Csiszar and Korner [2] investigated a more general situation: the broadcast channels with confidential messages, see Figure 2. The model of [2] is to transmit confidential messages to receiver 1 at rate [R.sub.1] and common messages to both receivers at rate [R.sub.0], while keeping receiver 2 as ignorant of the confidential messages as possible. Measuring ignorance by equivocation, a single-letter characterization of all the achievable triples ([R.sup.1], [R.sub.e], [R.sub.0]) was provided in [2], where [R.sub.e] is the second receiver's equivocation to the confidential messages. Note that the model of [2] is also a generalization of [3], where no confidentiality condition is imposed. In addition, Merhav [4] studied a specified wiretap channel and obtained the capacity region, where both the legitimate receiver and the wiretapper have access to some leaked symbols from the source, but the channels for the wiretapper are more noisy than the legitimate receiver, which shares a secret key with the encoder.

In communication systems there is often a feedback link from the receiver to the transmitter, for example, the two-way channels for telephone connections. It is well known that feedback does not increase the capacity of discrete memoryless channel (DMC). However, does the feedback increase the capacity region of the wiretap channel? In order to solve this problem, Ahlswede and Cai studied the general wiretap channel (the wiretap channel does not need to be degraded) with noiseless feedback from the legitimate receiver to the channel encoder [5](see Figure 3), and both upper and lower bounds of the secrecy capacity were provided. Specifically, for the degraded case, they showed that the secrecy capacity is larger than that of Wyner's wiretap channel (without feedback). In the achievability proof, Ahlswede and Cai [5] used the noiseless feedback as a secret key shared by the transmitter and the legitimate receiver, while the wiretapper had no additional knowledge about the key except his own received symbols. Based on the work of [5], Dai et al. [6] studied a special case of the general wiretap channel with noiseless feedback and found that the noiseless feedback enhances the secrecy capacity of the nondegraded wiretap channel. Besides Ahlswede and Cai's work, the wiretap channel with noisy feedback was studied in [7], and the wiretap channel with secure rate-limited feedback was studied in [8], and both of them focused on bounds of the secrecy capacity. Since the feedback in the model of wiretap channel is often used as a shared secret key, the techniques used in the secret sharing scheme play an important role in the construction of the practical secure communication systems, see [9-11].

Communication through state-dependent channels, with states known at the transmitter, was first investigated by Shannon [12]in 1958. In [12], the capacity of the discrete memoryless channel with causal (past and current) channel state information at the encoder was totally determined. After that, in order to solve the problem of coding for a computer memory with defective cells, Kuznecov and Cybakov [13] considered a channel in the presence of noncausal channel state information at the transmitter. They provided some coding techniques without the determination of the capacity.

The capacity was found in 1980 by Gel'efand and Pinsker [14]. Furthermore, Costa [15] investigated a power-constrained additive noise channel, where part of the noise is known at the transmitter as side information. This channel is also called dirty paper channel. The assumption in these seminar papers, as well as in the work on communication with state dependent channels that followed, is that the channel states are generated by nature and cannot be affected or controlled by the communication system.

In 2010, Weissman [16]revisited the above problem setting for the case where the transmitter can take actions that affect the formation of the states, see Figure 4. Specifically, Weissman considered a communication system where encoding is in two parts: given the message, an action sequence is created. The actions affect the formation of the channel states, which are accessible to the transmitter when producing the channel input sequence. The capacity of this model is totally determined both for the case where the channel inputs are allowed to depend noncausally on the state sequence and the case where they are restricted to causal dependence. Meanwhile, Weissman [16] found that the feedback from the channel output to the channel encoder cannot increase the channel capacity. This framework captures various new channel coding scenarios that may arise naturally in recording for magnetic storage devices or coding for computer memories with defects.

Inspired by the above works, Mitrpant et al. [17]studied the transmission of confidential messages through the channels with channel state information (CSI). In [17], an inner bound on the capacity-equivocation region was provided for the Gaussian wiretap channel with CSI. Furthermore, Chen and Vinck [18] investigated the discrete memoryless wiretap channel with noncausal CSI (see Figure 5) and also provided an inner bound on the capacity-equivocation region. Note that the coding scheme of [18] is a combination of those in [1, 14]. Based on the work of [18], Dai and Luo [19] provided an outer bound on the wiretap channel with noncausal CSI and determined the capacity-equivocation region for the memoryless case.

In this paper, we study the wiretap channel in the presence of action-dependent states and noiseless feedback, see Figure 6. This work is inspired by the wiretap channel with CSI [18], the channel with action-dependent CSI [16], and the wiretap channel with noiseless feedback [5]. The motivation of this work is to investigate the transmission of confidential messages through the channel with action-dependent CSI and noiseless feedback.

More concretely, in Figure 6, the transmitted message W is encoded as an action sequence [A.sup.N], and [A.sup.N] is the input of a discrete memoryless channel (DMC). The output of this DMC is the channel state sequence [S.sup.N]. The main channel is a DMC with inputs [X.sup.N] and [S.sup.N] and output [Y.sup.N]. The wiretap channel is also a DMC with input [Y.sup.N] and output [Z.sup.N]. Moreover, there exists a noiseless feedback from the output of the main channel to the channel encoder; that is, the inputs of the channel encoder are the transmitted message W, the state sequence [S.sub.N], and the noiseless feedback, while the output is [X.sub.N]. Since the action-dependent state captures various new coding scenarios for channels with a rewrite option that may arise naturally in storage for computer memories with defects or in magnetic recording, it is natural to ask the following two questions.

(i) How about the security of these channel models in the presence of a wiretapper?

(ii) What can the noiseless feedback do in the model of wiretap channel with action-dependent CSI?

Measuring wiretapper's uncertainty about the transmitted message by equivocation, the capacity-equivocation regions of the model of Figure 6 are provided both for the case where the channel input is allowed to depend noncausally on the state sequence and the case where it is restricted to causal dependence.

The contribution of this paper is as follows.

(i) Compared with the existing model of wiretap channel with side information [18](see Figure 5), the channel state information in [18] is a special case of that in our new model; that is, the model of [18] is included in the model of Figure 6. Therefore, our result generalizes the result of[18].

(ii) Our new model also extends the model of Figure 4 by considering an additional secrecy constraint, and therefore our result also generalizes the result of [16].

In this paper, random variab1es, sample values, and alphabets are denoted by capital letters, lowercase, letters and calligraphic letters, respectively. A similar convention is applied to the random vectors and their sample values. For example, [U.sup.N] denotes a random N-vector ([U.sub.1],..., [U.sub.N]), and [u.sup.N] = ([u.sub.1],..., [u.sub.N]) is a specific vector value in [U.sup.N], that is the, Nth Cartesian power of U. [U.sup.N.sub.1] denotes a random N - i + 1 vector ([U.sub.i],..., [U.sub.N]), and [u.sup.N.sub.i] = ([u.sub.i],..., [u.sub.N]) is a specific vector value in [U.sup.N.sub.i]. Let [p.sub.v](v) denote the probability mass function Pr{V = v}. Throughout the paper, the logarithmic function is taken to the base 2.

The remainder of this paper is organized as follows. In Section 2, we present the basic definitions and the main result on the capacity-equivocation region of wiretap channel with action-dependent channel state information and noiseless feedback. In Section 3, we provide a binary example of the model of Figure 6. Final conclusions are presented in Section 4.

2. Notations, Definitions, and the Main Results

In this section, the model of Figure 6 is considered into two parts. The model of Figure 6 with noncausal channel state information is described in Section 2.1, and the causal case is described in Section 2.2, see the following.

2.1. The Model of Figure 6 with Noncausal Channel State Information. In this section, a description of the wiretap channel with noncausal action-dependent channel state information is given by Definition 1 to Definition 5. The capacity-equivocation region [C.sup.n] composed of all achievable (R, [R.sup.e]) pairs is given in Theorem 6, where the achievable (R, [R.sup.e]) pair is defined in Definition 5.

Definition 1 (action encoder). The message W takes values in W, and it is uniformly distributed over its range. The action encoder is a deterministic mapping:

[f.sup.N.sub.1]: W [right arrow] [A.sup.N]. (1)

The input of the action encoder is W, while the output is [A.sup.N].

The channel state sequence [S.sup.N] is generated by a DMC with input [A.sup.N] and output [S.sup.N]. The transition probability distribution is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

Note that the components of the state sequence [S.sup.N] may not be i.i.d. random variables, and this is due to the fact that [A.sup.N] is not i.i.d. generated. The transmission rate of the message is log [parallel]W[parallel]/N.

Definition 2 (channel encoder and the main channel). The main channel is a DMC with finite input alphabet X x S, finite output alphabet y, and transition probability [Q.sub.M](y | x, s), where x [member of] X, s [member of] S, y [member of] y. [Q.sub.M]([y.sup.N]|[x.sup.N], [s.sup.N]) = [[PI].sup.N.sub.n = 1][Q.sub.M]([y.sub.n] |[x.sub.n], [s.sub.n]). The inputs of the main channel are [X.sup.N] and [S.sup.N], while the output is [Y.sup.N].

There is a noiseless feedback from the output of the main channel to the channel encoder. At the ith time, the feedback [Y.sup.i - 1] (where 2 [less than or equal to] i [less than or equal to] N and [Y.sup.i - 1] takes values in [y.sup.i - 1]) is the previous i-1 time output of the main channel. Since the channel encoder knows the state sequence [s.sup.N] in a noncausal manner, at the ith time, the inputs of the channel encoder are W, [Y.sup.i - 1], and [S.sup.N], while the output is [X.sub.i]; that is, the ith time channel encoder is a conditional probability (xi \w, [s.sup.N], [y.sup.i - 1]) that the message w, the feedback [y.sup.i - 1], and the channel state sequence [s.sup.N] are encoded as the ith time channel input [x.sub.i].

Definition 3 (wiretap channel). The wiretap channel is also a DMC with finite input alphabet y, finite output alphabet Z, and transition probability [Q.sub.W](z | y), where y [member of] Y, z [member of] Z. The input and output of the wiretap channel are [Y.sup.N] and [Z.sup.N], respectively. The equivocation to the wiretapper is defined as

[DELTA] = H(W | [Z.sup.N])/N. (3)

The cascade of the main channel and the wiretap channel is another DMC with transition probability:

[Q.sub.MW](z | x, s) = [summation over (y [member of] Y)] [Q.sub.W](z | y) [Q.sub.M](y | x, s). (4)

Note that W [right arrow] [A.sup.N] [right arrow] ([X.sup.N], [S.sup.N]) [right arrow] [Y.sup.N] [right arrow] [Z.sup.N] is a Markov chain in the model of Figure 6.

Definition 4 (decoder). The decoder for the legitimate receiver is a mapping [f.sub.D] : [Y.sup.N] [right arrow] W, with input [Y.sup.N] and output [??]. Let [P.sub.e] be the error probability of the receiver, and it is defined as Pr{W [not equal to] [??]}.

Definition 5 (achievable (R, [R.sub.e]) pair in the model of Figure 6). A pair (R, [R.sub.e]) (where R, [R.sub.e] > 0) is called achievable if, for any [epsilon] > 0 (where e is an arbitrary small positive real number and [epsilon] [right arrow] 0), there exist channel encoders decoders (N, [P.sub.e]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

The capacity-equivocation region [R.sup.n] is a set composed of all achievable (R, [R.sub.e]) pairs, and it is characterized by the following Theorem 6. The proof of Theorem 6 is in Appendices A and B.

Theorem 6. A single-letter characterization of the region [R.sup.n] is as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

where [p.sub.UASXYZ](u, a, s, x, y, z) = [p.sub.Z|Y](z | y)[p.sub.Y|X, S](y | x, s) [p.sub.UAXS](u, a, x, s), which implies that (A, U) [right arrow] (X, S) [right arrow] Y [right arrow] Z.

Remark 7. There are some notes on Theorem 6, see the following.

(i) The region [R.sup.(n)] is convex, and the proof is directly obtained by introducing a time-sharing random variable into Theorem 6, and, therefore, we omit the proof here.

(ii) The range of the random variable U satisfies

[parallel]U[parallel] [less than or equal to] [parallel]X[parallel][parallel]A[parallel][parallel]S[parallel] + 1. (7)

The proof is in Appendix C.

(iii) Without the equivocation parameter, the capacity of the main channel with feedback is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

The formula (8) is proved by Weissman [16], and it is omitted here.

(iv) Secrecy capacity: the points in [R.sup.(n)] for which [R.sub.e] = R are of considerable interest, which imply the perfect secrecy H(W) = H(W|[Z.sup.N]).

Definition 8 (the secrecy capacity [C.sup.(n).sub.s]). The secrecy capacity [C.sup.(n).sub.s] of the model of Figure 6 with noncausal channel state information is denoted by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

Clearly, we can easily determine the secrecy capacity C" of the model of Figure 6 with noncausal channel state information by

[C.sup.n.sub.s] = max min {I(U; Y) - I(U; S | A), H(Y | Z), H(A | Z)}. (10)

Proof of (10). Substituting [R.sub.e] = R into the region [R.sup.(n)] in Theorem 6, we have

R [less than or equal to] H(Y|Z), R [less than or equal to] I(U;Y) - I(U;S | A), R [less than or equal to] H(A|Z). (11)

Therefore, the secrecy capacity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus the proof is completed.

2.2. The Model of Figure 6 with Causal Channel State Information. The model of Figure 6 with causal channel state information is similar to the model with noncausal channel state information in Section 2.1, except that the state sequence [S.sup.N] in Definition 1 is known to the channel encoder in a causal manner, that is, at the ith time (1 [less than or equal to] i [less than or equal to] N), the output of the encoder [x.sub.i] = [f.sub.2, i](w, [s.sup.i], [y.sup.i - 1]), where [s.sup.i] = ([s.sub.1], [s.sub.2],..., [s.sub.i]) and [f.sub.2, i] is the probability that the message w, the feedback [y.sup.i - 1], and the state [s.sup.i] are encoded as the channel input [x.sub.i] at time i.

The capacity-equivocation region [R.sup.c] for the model of Figure 6 with causal channel state information is characterized by the following Theorem 9, and it is proved in Appendices D and E.

Theorem 9. A single-letter characterization of the region [R.sup.c] is as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (12)

where [p.sub.UASXYZ](u, a, s, x, y, z) = [p.sub.Z|Y](z | y)[p.sub.Y|X, S](y | x, s)[p.sub.UAXS](u, a, x, s), which implies that (A, U) [right arrow] (X, S) [right arrow] Y [right arrow] Z.

Remark 10. There are some notes on Theorem 9, see the following.

(i) The region [R.sup.(c)] is convex.

(ii) The range of the random variable U satisfies

[parallel]U[parallel] [less than or equal to] [parallel]X[parallel][parallel]A[parallel][parallel]S[parallel]. (13)

The proof is similar to that in Theorem 6, and it is omitted here.

(iii) Without the equivocation parameter, the capacity of the main channel with feedback is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

The formula (14) is proved by Weissman [16], and it is omitted here.

(iv) Secrecy capacity: the points in [R.sup.(c)] for which [R.sub.e] = R are of considerable interest, which imply the perfect secrecy H(W) = H(W|[Z.sup.N]).

Definition 11 (the secrecy capacity [C.sup.(c).sub.s]). The secrecy capacity of the model of Figure 6 with causal channel state information is denoted by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (15)

Clearly, we can easily determine the secrecy capacity [C.sup.(c).sub.s] of the model of Figure 6 with causal channel state information by

[C.sup.(c).sub.s] = max min {I(U; Y), H(Y|Z), H(A|Z)}. (16)

Proof of (16). Substituting [R.sub.e] = R into the region [R.sup.(c)] in Theorem 9, we have

R [less than or equal to] H(Y|Z), R [less than or equal to] I(U;Y), R [less than or equal to] H(A|Z). (17)

Therefore, the secrecy capacity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus The proof is completed.

3. A Binary Example for the Model of Figure 6 with Causal Channel State Information

In this section, we calculate the secrecy capacity of a special case of the model of Figure 6 with causal channel state information.

Suppose that the channel state information [S.sup.N] is available at the channel encoder in a casual manner. Meanwhile, the random variables U, A, X, S, Y, and Z take values in {0, 1}, and the transition probability of the main channel is defined as follows.

When s = 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (18)

When s = 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (19)

Note that here 0 [less than or equal to] p [less than or equal to] 1.

The wiretap channel is a (binary symmetric channel) BSC with crossover probability q (0 [less than or equal to] q [less than or equal to] 1/2), that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (20)

The channel for generating the state sequence [S.sup.N] is a BSC with crossover probability r (0 [less than or equal to] r [less than or equal to] 1), that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (21)

From Remark 10 we know that the secrecy capacity for the causal case is given by

[C.sup.c.sub.s] = max min {I(U;Y), H(Y|Z), H(A|Z)}. (22)

Note that max I(U;Y), max H(A | Z), and max H(Y | Z) are achieved if A is a function of U and X is a function of U and S, and this is similar to the argument in [16]. Define a = g(u) and x = f(u, s), then (22)can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (23)

and this is because the joint probability distribution [p.sub.AUSXTZ](a, u, s, x, y, z) can be calculated by

[p.sub.AUSXYZ](a, u, s, x, y, z) = [p.sub.Z|Y](z | y) [p.sub.Y|X, S](y | x, s) [1.sub.x = f(u, s)][p.sub.S|A] x (s|a) [1.sub.a = g(u)][p.sub.U](u). (24)

Since A is a function of U, we have

H(A\Z) = H(U\Z). (25)

Then, it is easy to see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (26)

Now it remains to calculate the characters [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; see the remaining of this section.

Let U take values in {0, 1}. The probability of U is defined as follows: [p.sub.U](0) = [alpha] and [p.sub.U](l) = 1 - [alpha].

In addition, there are 16 kinds of f and 4 kinds of g. Define the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (27)

The character I(U; Y) depends on the joint probability mass functions pVY(u, y), and we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (28)

The character H(U | Z) depends on the joint probability mass functions [p.sub.UZ](u, z), and we have

[p.sub.UZ](u, z) = [summation over y][p.sub.UYZ](u, y, z) = [summation over y][p.sub.Z|Y](z | y)[p.sub.U, Y](u, y). (29)

The character H(Y | Z) depends on the joint probability mass functions [p.sub.YZ](u, z), and we have

[p.sub.YZ](y, z) = [summation over y][p.sub.UYZ](u, y, z) = [sup.(a)][summation over u][p.sub.Z|Y](z | y)[p.sub.U, Y](u, y), (30)

where (a) is from U [right arrow] Y [right arrow] Z.

By choosing the above f, g, and [alpha], we find that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (31)

where h(p + q - 2pq) = (p + q - 2pq) log(1/(p + q - 2pq)) + (1- p - q + 2pq) log(1/(1 - p - q + 2pq)). Moreover, h(p + q - 2pq) is achieved when f = [f.sup.(7)], g = [g.sup.(2)] and [alpha] = 1/2. On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (32)

and "=" is achieved if f = [f.sup.(7)], g = [g.sup.(2)] and [alpha] = 1/2.

Moreover,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (33)

and "=" is achieved if f = [f.sup.(7)], g = [g.sup.(2)] and [alpha] = 1/2.

Therefore, the secrecy capacity for the causal case is given by

[C.sup.c.sub.s] = min {h(p + q - 2pq), 1 - h(p), h(q)}. (34)

Figures 7, 8, and9 give the secrecy capacity of the model of Figure 6 with causal channel state information for several values of q. It is easy to see that the secrecy capacity [C.sup.c.sub.s] is increasing while q is getting larger.

4. Conclusion

In this paper, we study the model of the wiretap channel with action-dependent channel state information and noiseless feedback. The capacity-equivocation regions are provided both for the case where the channel inputs are allowed to depend noncausally on the state sequence and the case where they are restricted to causal dependence. Furthermore, the secrecy capacities for both cases are formulated, which provide the best transmission rate with perfect secrecy. The result is further explained via a binary example.

The contribution of this paper is as follows.

(i) Compared with the existing model of wiretap channel with side information [18] (see Figure 5), the channel state information in [18] is a special case of that in our new model; that is, the model of [18] is included in the model of Figure 6. Therefore, our result generalizes the result of [18].

(ii) Our new model also extends the model of Figure 4 by considering an additional secrecy constraint, and therefore our result also generalizes the result of [16].

Appendices

A. Proof of the Direct Part of Theorem 6

In this section, we will show that any pair (R, [R.sub.e]) [member of] [R.sup.n] is achievable. Gel'efand-Pinsker's binning, block Markov coding, and Ahlswede-Cai's secret key on the feedback system are used in the construction of the code book.

Now the remainder of this section is organized as follows. The code construction is in Appendix A.1. The proof of achievability is given in Appendix A.2.

A.1. Code Construction. Since [R.sub.e] [less than or equal to] H(Y | Z), [R.sub.e] [less than or equal to] H(A|Z) and [R.sub.e] [less than or equal to] R [less than or equal to] I(U; Y) - I(U; S | A), it is sufficient to show that the pair (R, [R.sub.e]) = min{H(Y | Z), H(A | Z), I(U;Y) - I(U;S | A)} is achievable, and note that this implies that R [greater than or equal to] [R.sub.e] = min{H(Y | Z), H(A | Z), I(U; Y) - I(U; S | A)}.

The construction of the code and the proof of achievability are considered into two cases.

(i) Case 1: I(U; Y) - I(U; S | A) [greater than or equal to] min{H(Y | Z), H(A | Z)}.

(ii) Case 2: I(U; Y) - I(U; S | A) [less than or equal to] min{H(Y | Z), H(A | Z)}.

We use the block Markov coding method. The random vectors [U.sup.N], [A.sup.N], [S.sup.N], [X.sup.N], [Y.sup.N], and [Z.sup.N] consist of n blocks of length IV. The message for n blocks is [W.sup.n] [??] ([W.sub.2], [W.sub.3],..., [W.sub.n]), where [W.sub.i] (2 [less than or equal to] i [less than or equal to] n) are i.i.d. random variables uniformly distributed over W. Note that in the first block, there is no [W.sub.1].

Let [[??].sub.i] (1 [less than or equal to] i [less than or equal to] n) be the output of the wiretap channel for block i, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, [Y.sup.n] = ([[??].sub.1],..., [[??].sub.n]), and [[??].sub.i] (1 [less than or equal to] i [less than or equal to] n) is the output of the main channel for block i. The specific values of the above random vectors are denoted by lowercase letters.

(i) Code Construction for Case 1.Given a pair (R, [R.sub.e]), choose a joint probability mass function [p.sub.U, A, S, X, Y, Z](u, a, s, x, y, z) such that

0 [less than or equal to] [R.sub.e] [less than or equal to] R, R [less than or equal to] I(U; Y) - I(U; S | A), [R.sub.e] = min {H(Y | Z), H(A | Z)}. (A.1)

The message set W satisfies the following condition:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (A.2)

where [gamma] is a fixed positive real numbers and

0 [less than or equal to] [gamma] [less than or equal to] [sup.(a)] I(U; Y) - I(U; S | A) - min {H(Y | Z), H(A | Z)}. (A.3)

Note that (a) is from R [greater than or equal to] [R.sub.e] = min{H(Y | Z), H(A | Z)} and (A.2). Let W = {1, 2,..., [2.sup.NR]}.

Code-book generation:

(a) Construction of [A.sup.N] and [S.sup.N]. In the first block, generate a i.i.d. sequence [a.sup.N] according to the probability mass function [p.sub.A](a), and choose it as the output of the action encoder. Let [s.sup.N] be the state sequence generated in response to the chosen action sequence [a.sup.N].

For the ith block (2 [less than or equal to] i [less than or equal to] n), generate [2.sup.NR] i.i.d. sequences [a.sup.N], according to the probability mass function [p.sub.A](a). Index each sequence by i e {1, 2,..., [2.sup.NR]}. For a given message [w.sub.i] ([w.sub.i] [member of] W), choose a corresponding [a.sup.N]([w.sub.i]) as the output of the action encoder. Let [s.sup.N] be the state sequence generated in response to the action sequence [a.sup.N]([w.sub.i]).

(b) Construction of the Secret Key. For the ith block (2 [less than or equal to] i [less than or equal to] n), firstly we generate a mapping [g.sub.f] : [Y.sup.N] [right arrow] W (note that [parallel]Y[[parallel].sup.N] [greater than or equal to] [parallel]W[parallel]). Define a random variable [K.sub.i] = [g.sub.f]([[??].sub.i - 1]) (2 [less than or equal to] i [less than or equal to] n), which is uniformly distributed over W, and [K.sub.i] is independent of [W.sub.i]. Reveal the mapping [g.sub.f] to both receivers and the transmitter.

Then, when the transmitter receives the output [[??].sub.i - 1] of the i-1th block, he computes [k.sub.i] = [g.sub.f]([[??].sub.i - 1]) [member of] W as the secret key used in the ith block.

(c) Construction of [U.sup.N]. In the first block, for the transmitted action sequence a and the corresponding state sequence [s.sup.N], generate a i.i.d. sequence [u.sup.N] according to the probability mass function [p.sub.U|A, S]([u.sub.i] | [a.sub.i], [s.sub.i]). Choose [u.sup.N] as a realization of [U.sup.N] for the first block.

For the ith block (2 [less than or equal to] i [less than or equal to] n), given the transmitted action sequence [a.sup.N]([w.sub.i]) and the corresponding state sequence [s.sup.N], generate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] i.i.d. sequences [u.sup.N], according to the probability mass function [p.sub.U | A, S]([u.sub.i] | [a.sub.i]([w.sub.i]), [s.sub.i]). Distribute these sequences at random into [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] bins such that each bin contains [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] sequences. Index each bin by i [member of] {1, 2,..., [2.sup.NR]}.

For a given [w.sub.i], [a.sup.N]([w.sub.i]), [s.sup.N], and a secret key [k.sub.i], the transmitter chooses a sequence [u.sup.N]([w.sub.i] [direct sum] [k.sub.i], [j.sup.*]) from the bin [w.sub.i] [direct sum] [k.sub.i] (where [direct sum] is the modulo addition over W) such that ([u.sup.N]([w.sub.i] [direct sum] [k.sub.i], [j.sup.*]), [a.sup.N]([w.sub.i]), [s.sup.N]) [member of] [T.sup.N.sub.US|A]([epsilon]). If such multiple sequences in bin [w.sub.i] [direct sum] [k.sub.i] exist, choose the one with the smallest index in the bin. If no such sequence exists, declare an encoding error.

(d) Construction of [X.sup.N]. For each block, the [x.sup.N] is generated according to a new discrete memoryless channel (DMC) with inputs [u.sup.N], [s.sup.N], and output [x.sup.N]. The transition probability of this new DMC is [p.sub.X | U, S](x | u, s), which is obtained from the joint probability mass function [p.sub.U, A, S, X, Y, Z](u, a, s, x, y, z).

The probability [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is calculated as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A.4)

Decoding. For the ith block (2 [less than or equal to] i [less than or equal to] n), given a vector [y.sup.N] [member of] [Y.sup.N] and a secret key [k.sub.i] ([k.sub.i] is known by the receiver), try to find a sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [T.sup.N.sub.UY]([[epsilon].sub.3]). If there exist sequences with the same [[??].sub.i] [direct] [k.sub.i], by using the secret key [k.sub.i], put out the corresponding [[??].sub.i]. Otherwise, that is, if no such sequence exists or multiple sequences have different message indices, declare a decoding error.

(ii) Code Construction for Case 2.Given a pair (R, [R.sub.e]), choose a joint probability mass function [p.sub.U, A, S, X, Y, Z](u, a, s, x, y, z) such that

0 [less than or equal to] [R.sub.e] < R, R = I(U; Y) - I(U; S | A), [R.sub.e] = I(U; Y) - I(U; S | A). (A.5)

The message set W satisfies the following condition:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A.6)

Let W = {1, 2,..., [2.sup.NR]}.

Code-book generation:

(a) Construction of [A.sup.N] and [S.sup.N]. In the first block, generate a i.i.d. sequence [a.sup.N] according to the probability mass function [p.sub.A](a), and choose it as the output of the action encoder. Let [s.sup.N] be the state sequence generated in response to the chosen action sequence [a.sup.N].

For the ith block (2 [less than or equal to] i [less than or equal to] n), generate [2.sup.NR] i.i.d. sequences [a.sup.N], according to the probability mass function [p.sub.A](a). Index each sequence by i [member of] {1, 2,..., [2.sup.NR]}. For a given message [w.sub.i] ([w.sub.i] [member of] W), choose a corresponding [a.sup.N]([w.sub.i]) as the output of the action encoder. Let [s.sup.N] be the state sequence generated in response to the action sequence [a.sup.N]([w.sub.i]).

(b) Construction of the Secret Key. For the ith block (2 [less than or equal to] i [less than or equal to] n), firstly we generate a mapping [g.sub.f] : [Y.sup.N] [right arrow] W (note that [parallel]Y[[parallel].sup.N] [greater than or equal to] [parallel]W[parallel]). Define a random variable [K.sub.i] = [g.sub.f]([[??].sub.i - 1])(2 [less than or equal to] i [less than or equal to] n), which is uniformly distributed over W, and [K.sub.i] is independent of [W.sub.i]. Reveal the mapping [g.sub.f] to both receivers and the transmitter.

Then, when the transmitter receives the output [[??].sub.i - 1] of the i-1th block, he computes [k.sub.i] = [g.sub.f]([[??].sub.i - 1]) [member of] W as the secret key used in the ith block.

(c) Construction of [U.sup.N]. In the first block, for the transmitted action sequence [a.sup.N] and the corresponding state sequence [s.sup.N], generate a i.i.d. sequence [u.sup.N] according to the probability mass function [p.sub.U | A, S]([u.sub.i] | [a.sub.i], [s.sub.i]). Choose [u.sup.N] as a realization of [U.sup.N] for the first block.

For the ith block (2 [less than or equal to] i [less than or equal to] n), given the transmitted action sequence [a.sup.N]([w.sub.i]) and the corresponding state sequence [s.sup.N], generate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] i.i.d. sequences [u.sup.N], according to the probability mass function [p.sub.U | A, S]([u.sub.i] | [a.sub.i]([w.sub.i]), [s.sub.i]). Distribute these sequences at random into [2.sup.NR] = [2.sup.N(I(U;V)-I(U;S | A))] bins such that each bin contains [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] sequences. Index each bin by i [member of] {1, 2,..., [2.sup.NR]}.

For a given [w.sub.i], [a.sup.N]([w.sub.i]), [s.sup.N], and a secret key [k.sub.i], the transmitter chooses a sequence [u.sup.N]([w.sub.i] [direct sum] [k.sub.i], [j.sub.i]) from the bin [w.sub.i] [direct sum] [k.sub.i] (where [direct sum] is the modulo addition over W) such that ([u.sup.N]([w.sub.i] [direct sum] [k.sub.i], [j.sup.*]), [a.sup.N]([w.sub.i]), [s.sup.N]) [member of] [T.sup.N.sub.US | A]([epsilon]). If such multiple sequences in bin [w.sub.i] [direct sum] [k.sub.i] exist, choose the one with the smallest index in the bin. If no such sequence exists, declare an encoding error.

(d) Construction of [X.sup.N]. The [x.sup.N] is generated the same as that for the case 1, and it is omitted here.

Decoding. For the ith block (2 [less than or equal to] i [less than or equal to] n), given a vector [y.sup.N] [member of] [Y.sup.N] and a secret key [k.sub.i]([k.sub.i] is known by the receiver), try to find a sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If there exist sequences with the same [w.sub.i] [direct sum] [k.sub.*], by using the secret key [k.sub.i], put out the corresponding [[??].sub.i]. Otherwise, that is, if no such sequence exists or multiple sequences have different message indices, declare a decoding error.

A.2. Proof of Achievability. The rate of the message [W.sup.n] is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (A.7)

and it satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A.8)

In addition, note that the encoding and decoding scheme for Theorem 6 is exactly the same as that in [16], except that the transmitted message for the legitimate receiver is w [direct sum] k. Since the legitimate receiver knows, the decoding scheme for Theorem 6 is in fact the same as that in [16]. Hence, we omit the proof of [P.sub.e] [less than or equal to] [epsilon] here.

It remains to show that [lim.sub.N [right arrow] [infinity]] [DELTA] [greater than or equal to] [R.sub.e], see the following.

Since the message is encrypted by W [direct sum] K, the equivocation about is equivalent to the equivocation about the secret key K. There are two ways for the wiretapper to obtain the secret key One way is that he tries to guess the k from its alphabet W. The other way is that he tries to guess the feedback [y.sup.N] ([y.sup.N] is the output of the main channel for the previous block, and k = [g.sub.f]([y.sup.N])) from the conditional typical set [T.sup.N.sub.[Y|Z]]([delta]), and this is because for a given [z.sup.N] and sufficiently large N, Pr{[y.sup.N] [??] [T.sup.N.sub.[Y | Z]]([delta])} [right arrow] 0. Note that there are [2.sup.NH(Y|Z)] sequences [y.sup.N] [member of] [T.sup.N.sub.[Y | Z]]([delta]) when N [right arrow] [infinity] and [delta] [right arrow] 0. Therefore, the equivocation about W is min{(log [parallel]W[parallel])/N = R, H(Y | Z)}, and note that R [greater than or equal to] [R.sub.e] and H(Y | Z) [greater than or equal to] [R.sub.e], and then [lim.sub.N [right arrow] [infinity]] [DELTA] [greater than or equal to] [R.sub.e] is obtained.

The details about the proof are as follows.

First, we will show that [K.sub.i] [direct sum] [W.sub.i] is independent of K* and [W.sub.i], and this is used in the proof of [lim.sub.N [right arrow] [infinity]] [DELTA] [greater than or equal to] [R.sub.e].

Since [K.sub.i] is independent of [W.sub.i] (2 [less than or equal to] i [less than or equal to] n), and all of them are uniformly distributed over W, the fact that [K.sub.i] [direct sum] [W.sub.i] is independent of [K.sub.i] and [W.sub.i] is proved by the following (A.9):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (A.9)

Then, [lim.sub.N [right arrow] [infinity]] [DELTA] [greater than or equal to] [R.sub.e] for both cases is proved by the following (A.10):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (A.10)

where (a) is from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that is a Markov chain, (b) is from [W.sub.i] [right arrow] ([W.sub.i] [direct sum] [K.sub.i], [[??].sup.i - 1]) [right arrow] [[??].sup.i] that is a Markov chain, (c) follows from the fact that [K.sub.i] [direct sum] [W.sub.i] is independent of [K.sub.i] and [[??].sup.i - 1], and (d) is from the fact that the wiretapper can guess the specific vector [[??].sub.i - 1] (corresponding to the key [K.sub.i]) from the conditional typical set [T.sup.N.sub.[Y | Z]]([delta]), and [K.sub.i] is uniformly distributed over W (K* is the key used in block i).

On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (A.11)

where(1) is from thefactthat [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the state sequence for block i, [A.sup.n.sub.2] = ([[??].sub.2],..., [[??].sub.n]) and [[??].sub.i] is a function of [W.sub.i],(2) is from [A.sub.n] and [X.sub.n] that are i.i.d. generated random vectors, and the channels are discrete memoryless.

Therefore, it is easy to see that, for thecase1, [lim.sub.N [right arrow] [infinity]] [DELTA] [greater than or equal to] [R.sub.e] is proved by (A.10) and (A.11). For the case 2, [lim.sub.N [right arrow] [infinity]] [DELTA] [greater than or equal to] [R.sub.e] is proved by the formula (A.10).

Thus, [lim.sub.N [right arrow] [infinity]] [DELTA] [greater than or equal to] [R.sub.e] for both cases is proved. Thep roof of Theorem 6 is completed.

B. Proof of the Converse Part of Theorem 6

In this section, we prove the converse part of Theorem 6: all the achievable (R, [R.sub.e]) pairs are contained in the set [R.sup.(n)]. Suppose that (R, [R.sub.e]) is achievable; that is, for any given [epsilon] > 0, there exists a channel encoder-decoder (N, [DELTA], [P.sub.e]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (B.1)

Then we will show the existence of random variables (A, U) [right arrow] (X, S) [right arrow] Y [right arrow] Z such that

0 [less than or equal to] [R.sub.e] [less than or equal to] R, (B.2)

R [less than or equal to] I(U; Y) - I(U; S | A), (B.3)

[R.sub.e] [less than or equal to] H(Y | Z), (B.4)

[R.sub.e] [less than or equal to] H(A | Z). (B.5)

Since W is uniformly distributed over W, we have H(W) = log[parallel]W[parallel]. The formulas (B.3), (B.4), and (B.5) are proved by Lemma B.1; see the following.

Lemma B.1. The random vectors [Y.sup.N] and [Z.sup.N] and the random variables W, U, A, S, X, Y, and Z of Theorem 6 satisfy

1/N(W) [less than or equal to] I(U; Y) - I(U; S | A) + 1/N [delta]([P.sub.e]), (B.6)

1/N H(W | [Z.sup.N]) [less than or equal to] H(Y | Z) + 1/N [delta]([P.sub.e]), (B.7)

1/N H(W | [Z.sup.N]) [less than or equal to] H(A | Z), (B.8)

where [delta]([P.sub.e]) = h([P.sub.e]) + [P.sub.e]log([absolute value of W] - 1). Note that h([P.sub.e]) = -[P.sub.e]log [P.sub.e] - (1 - [P.sub.e]) log(1 - [P.sub.e]).

Substituting H(W) = log [parallel]W[parallel] and (5) into (B.6), (B.7), and (B.8) and using the fact that [epsilon] - 0, the formulas (B.3), (B.4), and (B.5) are obtained. The formula (B.2) is from

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (B.9)

It remains to prove Lemma B.1; see the following.

Proof of Lemma B.1. The formula (B.6) follows from (B.10), (B.13), and (B.21). The formula (B.7) is from(B.11), (B.17) and (B.22). The formula (B.8) is proved by (B.12), (B.18), and (B.23).

Part(i). We begin with the left parts of the inequalities (B.6), (B.7), and (B.8); see the following.

Since W [right arrow] [Y.sup.N] [right arrow] [Z.sup.N] is a Markov chain, for the message W, we have

1/N H(W) = 1/N H(W | [Y.sup.N]) + 1/N I([Y.sup.N]; W) [less than or equal to] [sup.(a)] 1/N [delta]([P.sub.e]) + 1/N I([Y.sup.N]; W). (B.10)

For the equivocation to the wiretapper, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (B.11)

Moreover,

1/N H(W | [Z.sup.N]) = 1/N H([A.sup.N] | [Z.sup.N]). (B.12)

Note that (a) and (b) follow from Fano's inequality, and (B.12) is from the fact that [A.sup.N] is a deterministic function of W.

Part (ii). By using chain rule, the character I([Y.sup.N];W) in formulas (B.10) and (B.11) can be bounded as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (B.13)

where formula (1) follows from that W [right arrow] [A.sup.N] [right arrow] [S.sup.N], and formula (2) follows from that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (B.14)

and formula (3) follows from that [S.sub.i] [right arrow] [A.sub.i] [right arrow] ([S.sup.N.sub.i + 1], [A.sup.i - 1], [A.sup.N.sub.i + 1]).

Proof of (B.14). The left part of (B.14) can be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (B.15)

where (1) is from the fact that [A.sup.N] is a deterministic function of W.

The right part of (B.14) can be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (B.16)

where (2) is from the fact that [A.sup.N] is a deterministic function of W.

The formula (B.14) is proved by (B.15) and (B.16). The proof is completed.

Part (iii). The character H([Y.sup.N] | [Z.sup.N]) in formula (B.11) can be rewritten as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (B.17)

Part (iv). The character H([A.sup.N] | [Z.sup.N]) in formula (B.12) can be rewritten as follows:

1/N H([A.sup.N] | [Z.sup.N]) [less than or equal to] 1/N [N.summation over (i = 1)] H([A.sub.i] | [Z.sub.i]). (B.18)

Part (v) (single letter).Tocompletethe proof, we introduce a random variable J, which is independent of W, [A.sup.N], [X.sup.N], [S.sup.N], [Y.sup.N] and [Z.sup.N]. Furthermore, J is uniformly distributed over {1, 2,..., N}. Define

U = (W, [Y.sup.J - 1], [S.sup.N.sub.J + 1], [A.sup.N], J), (B.19)

X = [X.sub.J], Y = [Y.sub.J], Z = [Z.sub.J], S = [S.sub.J], A = [A.sub.J]. (B.20)

Part (vi). Then (B.13) can be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (B.21)

Analogously, (B.17) is rewritten as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (B.22)

Similarly, (B.18) can be rewritten as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (B.23)

Substituting (B.21), (B.22), (B.23) into (B.10), (B.11), and (B.12), Lemma B.1 is proved.

The proof of Theorem 6 is completed.

C. Size Constraint of the Auxiliary Random Variable in Theorem 6

By using the support lemma (see [20, page 310]), it suffices to show that the random variable U can be replaced by new one, preserving the Markovity (U, A) [right arrow] (X, S) [right arrow] Y [right arrow] Z and the mutual information I(U; Z), I(U; Y), I(U; S | A), and furthermore, the range of the new U satisfies, [parallel]U[parallel] [less than or equal to] [parallel]X[parallel][parallel]S[parallel][parallel]A[parallel] + 1. The proof is in the reminder of this section.

Let

[bar.p] = [p.sub.XSA](x, s, a). (C.1)

Define the following continuous scalar functions of [bar.p]:

[f.sub.XSA]([bar.p]) = [p.sub.XSA](x, s, a), [f.sub.Y]([bar.p]) = H(Y), [f.sub.S | A]([bar.p]) = H(S | A). (C.2)

Since there are [parallel]X[parallel][parallel]S[parallel][parallel]A[parallel] functions of [f.sub.XSA]([bar.p]), the total number of the continuous scalar functions of [bar.p] is [parallel]X[parallel][parallel]S[parallel][parallel]A[parallel] + 1.

Let [p.sub.XSA | U] = Pr{X = x, S = s, A = a | U = u}. With these distributions [[bar.p].sub.XSA | U] = Pr{X = x, S = s, A = a | U = u}, we have

[p.sub.XSA](x, s, a) = [summation over (u [member of] U)]p(U = u) [f.sub.XSA]([[bar.p].sub.XSA | U]), (C.3)

I(U;S | A) = [f.sub.S | A]([bar.p]) - [summation over (u [member of] U)]p(U = u) [f.sub.S | A] ([[bar.p].sub.XSA | U]), (C.4)

H(Y | U) = [summation over (u [member of] U)]p(U = u) [f.sub.Y]([[bar.p].sub.XSA | U]). (C.5)

According to the support lemma ([20, page 310]), the random variable can be replaced by new ones such that the new U takes at most [parallel]X[parallel][parallel]S[parallel][parallel]A[parallel] + 1 different values and the expressions (C.3), (C.4), and (C.5) are preserved.

D. Proof of the Direct Part of Theorem 9

In this section, we will show that any pair (R, [R.sub.e]) [member of] [R.sup.c] is achievable. Block Markov coding and Ahlswede-Cai's secret key on the feedback system are used in the construction of the code-book.

Now the remainder of this section is organized as follows. The code construction is in Appendix D.1. The proof of achievability is given in Appendix D.2.

D.1. Code Construction. Since [R.sub.e] [less than or equal to] H(Y | Z), [R.sub.e] [less than or equal to] H(A | Z), and [R.sub.e] [less than or equal to] R [less than or equal to] I(U; Y), it is sufficient to show that the pair (R, [R.sub.e]) = min{H(Y | Z), H(A | Z), I(U; Y)} is achievable, and note that this implies that R [greater than or equal to] Re = min{H(Y | Z), H(A | Z), I(U; Y)}.

We use the block Markov coding method. The random vectors [U.sup.N], [A.sup.N], [S.sup.N], [X.sup.N], [Y.sup.N], and [Z.sup.N] consist of n blocks of length N. The message for n blocks is [W.sup.n] [??] ([W.sub.2], [W.sub.3],..., [W.sub.n]), where [W.sub.i] (2 [right arrow] i [less than or equal to] n) are i.i.d. random variables uniformly distributed over W. Note that, in the first block, there is no [W.sub.1].

Let [[??].sub.i](1 [less than or equal to] i [less than or equal to] n) be the output of the wiretap channel for block [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, [Y.sup.n] = ([[??].sub.1],..., [[??].sub.n]) and [[??].sub.t] (1 [less than or equal to] i [less than or equal to] n) are the output of the main channel for block i. The specific values of the above random vectors are denoted by lowercase letters.

Given a pair (R, Re), choose a joint probability mass function [p.sub.U, A, S, X, Y, Z](u, a, s, x, y, z) such that

0 [less than or equal to] [R.sub.e] [less than or equal to] R, R [less than or equal to] I(U; Y), [R.sub.e] = min {H(Y | Z), H(A | Z)}. (D.1)

The message set W satisfies the following condition:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (D.2)

where y is a fixed positive real numbers.

Code-book generation:

(i) Construction of [A.sup.N] and [S.sup.N]. In the first block, generate a i.i.d. sequence [a.sup.N] according to the probability mass function [p.sub.A](a), and choose it as the output of the action encoder. Let [s.sup.N] be the state sequence generated in response to the chosen action sequence [a.sup.N].

For the ith block (2 [less than or equal to] i [less than or equal to] n), generate [2.sup.NR] i.i.d. sequences [a.sup.N], according to the probability mass function [p.sub.A](a). Index each sequence by i [member of] {1, 2,..., [2.sup.NR]}. For a given message i ([w.sub.i] [member of] W), choose a corresponding [a.sup.N]([w.sub.i]) as the output of the action encoder. Let [s.sup.N] be the state sequence generated in response to the action sequence [a.sup.N]([w.sub.i]).

(ii) Construction of the Secret Key. For the ith block (2 [less than or equal to] i [less than or equal to] n), firstly we generate a mapping [g.sub.f]: [Y.sup.N] [right arrow] W (note that [parallel]Y[[parallel].sup.N] [greater than or equal to] [parallel]W[parallel]). Define a random variable [K.sub.i] = [g.sub.f]([[??].sub.i - 1]) (2 [less than or equal to] i [less than or equal to] n), which is uniformly distributed over W, and [K.sub.i] is independent of [W.sub.i]. Reveal the mapping [g.sub.f] to both receivers and the transmitter.

Then, when the transmitter receives the output [[??].sub.i - 1] of the i-1th block, he computes [k.sub.i] = [g.sub.f]([[??].sub.i - 1]) [member of] W as the secret key used in the ith block.

(iii) Construction of [U.sup.N]. In the first block, for the transmitted action sequence [a.sup.N] and the corresponding state sequence [s.sup.N], generate a i.i.d. sequence [u.sup.N] according to the probability mass function [p.sub.U | AS]([u.sub.i] | [a.sub.i], [s.sub.i]). Choose [u.sup.N] as a realization of [U.sup.N] for the first block.

For the ith block (2 [less than or equal to] i [less than or equal to] n), given the transmitted action sequence [a.sup.N]([w.sub.i]) and the corresponding state sequence [s.sup.N], generate [2.sup.NR] i.i.d. sequences [u.sup.N], according to the probability mass function [p.sub.U | A, S]([u.sub.i] | [a.sub.i]([w.sub.i]), [s.sub.i]). Index each sequence by i [member of] {1, 2,..., [2.sup.NR]}.

For a given [w.sub.i] and a secret key [k.sub.i], the transmitter chooses a sequence [u.sup.N]([w.sub.i] [direct sum] [k.sub.i]) (where [direct sum] is the modulo addition over W) to transmit.

(iv) Construction of [X.sup.N]. For each block, the [x.sup.N] is generated according to a new discrete memoryless channel (DMC) with inputs [u.sup.N], [s.sup.N], and output [x.sup.N]. The transition probability of this new DMC is [p.sub.X | U, S](x | u, s), which is obtained from the joint probability mass function [p.sub.U, A, S, X, Y, Z](u, a, s, x, y, z).

The probability [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is calculated as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (D.3)

Decoding. For the ith block (2 [less than or equal to] i [less than or equal to] n), given a vector [y.sup.N] [member of] [Y.sup.N] and a secret key [k.sub.i]([k.sub.i] is known by the receiver), try to find a sequence [u.sup.N]([[??].sub.i] [direct sum] [k.sub.*]) such that ([u.sup.N]([[??].sub.i] [direct sum] [k.sub.i]), [y.sup.N]) [member of] [T.sup.N.sub.UY]([[epsilon].sub.3]). If there exist sequences with the same [[??].sub.i] [direct sum] [k.sub.i], by using the secret key [k.sub.i], put out the corresponding [[??].sub.i]. Otherwise, that is, if no such sequence exists or multiple sequences have different message indices, declare a decoding error.

D. 2. Proof of Achievability. The proof of achievability for Theorem 9 is along the lines of that for Theorem 6, and, therefore, we omit the proof here.

The proof of Theorem 9 is completed.

E. Proof of the Converse Part of Theorem 9

In this section, we prove Theorem 9: all the achievable (R, [R.sub.e]) pairs are contained in the set [R.sup.(c)]. Suppose that (R, [R.sub.e]) is achievable; that is, for any given [epsilon] > 0, there exists a channel encoder-decoder (N, A, [P.sub.e]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (E.1)

Then we will show the existence of random variables (A, U) [right arrow] (X, S) [right arrow] Y [right arrow] Z such that

0 [less than or equal to] [R.sub.e] [less than or equal to] R, (E.2)

R [less than or equal to] I(U; Y), (E.3)

[R.sub.e] [less than or equal to] H(Y | Z), (E.4)

[R.sub.e] [less than or equal to] H(A | Z). (E.5)

Since W is uniformly distributed over W, we have H(W) = log [parallel]W[parallel]. The formulas (E.3), (E.4), and (E.5) are proved by Lemma E.1; see the following.

Lemma E.1. The random vectors [Y.sup.N] and [Z.sup.N] and the random variables W, X, U, S, A, Y, and Z of Theorem 9 satisfy

1/N H(W) [less than or equal to] I(U; Y) + 1/N [delta]([P.sub.e]), (E.6)

1/N H(W | [Z.sup.N]) [less than or equal to] H(Y | Z) + 1/N [delta]([P.sub.e]), (E.7)

1/N H(W | [Z.sup.N]) [less than or equal to] H(A | Z), (E.8)

where [delta]([P.sub.e]) = h([P.sub.e]) + [P.sub.e]log([absolute value of W] -1). Note that h([P.sub.e]) = -[P.sub.e] log [P.sub.e] - (1 - [p.sub.e]) log(1 - [P.sub.e]).

Substituting H(W) = log [parallel]W[parallel] and (5) into (E.6), (E.7), and (E.8) and using the fact that [epsilon] [right arrow] 0, the formulas (E.3), (E.4), and (E.5) are obtained. The formula (E.2) is from

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (E.9)

It remains to prove Lemma E.1; see the following.

Proof of Lemma E.1. The formula (E.6) follows from (E.10), (E.13), and (E.17). The formula (E.7) is from (E.11), (e.14), and (E.18). The formula (E.8) is proved by (E.12), (E.15), and (E.19).

Part (i). We begin with the left parts of the inequalities (E.6), (E.7), and (E.8); see the following.

Since W [right arrow] [Y.sup.N] [right arrow] [Z.sup.N] is a Markov chain, for the message W, we have

1/N H(W) = 1/N H(W | [Y.sup.N]) + 1/N I([Y.sup.N]; W) [less than or equal to] [sup.(a)]1/N [delta]([P.sub.e]) + 1/N I([Y.sup.N]; W). (E.10)

For the equivocation to the wiretapper, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (E.11)

1/N H(W | [Z.sup.N]) = 1/N H([A.sup.N] | [Z.sup.N]). (E.12)

Note that (a) and (b) follow from Fano's inequality, and (E.12) is from the fact that [A.sup.N] is a deterministic function of W.

Part (ii). By using chain rule, the character I([Y.sup.N]; W) in formulas (E.10) and (E.11) can be bounded as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (E.13)

Part (iii). Similar to (E.13), the character I(W; [Z.sup.N]) in formula (E.11) can be rewritten as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (E.14)

Part (iv). The character H([A.sup.N] | [Z.sup.N]) in formula (E.12) can be rewritten as follows:

1/N H([A.sup.N] | [Z.sup.N]) [less than or equal to] 1/N [N.summation over (i = 1)]H([A.sub.i] | [Z.sub.i]). (E.15)

Part (v) (single letter). To complete the proof, we introduce a random variable J, which is independent of W, [A.sup.N], [X.sup.N], [S.sup.N], [Y.sup.N], and [Z.sup.N]. Furthermore, J is uniformly distributed over {1, 2,..., N}. Define

U = (W, [Y.sup.J - 1], [S.sup.J - 1], J), X = [X.sub.J], Y = [Y.sub.J], Z = [Z.sub.J], S = [S.sub.J], A = [A.sub.J]. (E.16)

Part (vi). Then (E.13) can be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (E.17)

Analogously, (E.14) is rewritten as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (E.18)

Similarly, (E.15) can be rewritten as follows,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (E.19)

Substituting (E.17), (E.18), and (E.19) into (E.10), (E.11), and (E.12), Lemma E.1 is proved.

The proof of Theorem 9 is completed.

http://dx.doi.org/10.1155/2013/423619

Acknowledgments

The authors would like to thank Professor N. Cai for his help to improve this paper. This work was supported by a sub-project in National Basic Research Program of China under Grant 2012CB316100 on Broadband Mobile Communications at High Speeds, the National Natural Science Foundation of China under Grant 61271222, and the Research Fund for the Doctoral Program of Higher Education of China (no. 20100073110016).

References

[1] A. D. Wyner, "The wire-tap channel," The Bell System Technical Journal, vol. 54, no. 8, pp. 1355-1387, 1975.

[2] I. Csiszar and J. Korner, "Broadcast channels with confidential messages," IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 339-348, 1978.

[3] J. Korner and K. Marton, "General broadcast channels with degraded message sets," IEEE Transactions on Information Theory, vol. 23, no. 1, pp. 60-64, 1977.

[4] N. Merhav, "Shannon's secrecy system with informed receivers and its application to systematic coding for wiretapped channels," IEEE Transactions on Information Theory, vol. 54, no. 6, pp. 2723-2734, 2008.

[5] R. Ahlswede and N. Cai, "Transmission, identification and common randomness capacities for wire-tape channels with secure feedback from the decoder," in General Theory of Information Transfer and Combinatorics, vol. 4123 of Lecture Notes in Computer Science, pp. 258-275, Springer, Berlin, Germany, 2006.

[6] B. Dai, A. J. Han Vinck, Y. Luo, and Z. Zhuang, "Capacity region of non-degraded wiretap channel with noiseless feedback," in Proceedings of the IEEE International Symposiumon Information Theory, Cambridge, Mass, USA, July 2012.

[7] L. Lai, H. El Gamal, and H. V. Poor, "The wiretap channel with feedback: encryption over the channel," IEEE Transactions on Information Theory, vol. 54, no. 11, pp. 5059-5067, 2008.

[8] E. Ardestanizadeh, M. Franceschetti, T. Javidi, and Y.-H. Kim, "Wiretap channel with secure rate-limited feedback," IEEE Transactions on Information Theory, vol. 55, no. 12, pp. 5353-5361, 2009.

[9] G. Chen and C. Chang, "A construction for secret sharing scheme with general access structure," Journal of Information Hiding and Multimedia Signal Processing, vol. 4, no. 1, pp. 1-8, 2013.

[10] R. Nishimura, S. Abe, N. Fujita, and Y. Suzuki, "Reinforcement of VoIP security with multipath routing and secret sharing scheme," Journal of Information Hiding and Multimedia Signal Processing, vol. 1, no. 3, pp. 204-219, 2010.

[11] Z. Wang, C. Chang, H. N. Tu, and M. Li, "Sharing a secret image in binary images with verification," Journal of Information Hiding and Multimedia Signal Processing, vol. 2, no. 1, pp. 78-90, 2011.

[12] C. E. Shannon, "Channels with side information at the transmitter," IBM Journal of Research and Development, vol. 2, pp. 289-293, 1958.

[13] A. V. Kuznecov and B. S. Cybakov, "Coding in a memory with imperfect cells," Problemy Peredachi Informatsii, vol. 10, no. 2, pp. 52-60, 1974.

[14] S. I. Gel'efand and M. S. Pinsker, "Coding for channel with random parameters," Problems of Control and Information Theory, vol. 9, no. 1, pp. 19-31, 1980.

[15] M. H. M. Costa, "Writing on dirty paper," IEEE Transactions on Information Theory, vol. 29, no. 3, pp. 439-441, 1983.

[16] T. Weissman, "Capacity of channels with action-dependent states," IEEE Transactions on Information Theory, vol. 56, no. 11, pp. 5396-5411, 2010.

[17] C. Mitrpant, A. J. HanVinck, and Y. Luo, "An achievable region for the Gaussian wiretap channel with side information," IEEE Transactions on Information Theory, vol. 52, no. 5, pp. 2181-2190, 2006.

[18] Y. Chen and A. J. H. Vinck, "Wiretap channel with side information," IEEE Transactions on Information Theory, vol. 54, no. 1, pp. 395-402, 2008.

[19] B. Dai and Y. Luo, "Some new results on wiretap channel with side information," Entropy, vol. 14, pp. 1671-1702, 2012.

[20] I. Csiszar and J. Korner, Information Theory, Probability and Mathematical Statistics, Academic Press, London, UK, 1981.

Bin Dai, (1) A. J. Han Vinck, (2) and Yuan Luo (3)

(1) School of Information Science and Technology, Southwest JiaoTong University, Chengdu 610031, China

(2) Institute for Experimental Mathematics, Duisburg-Essen University, Ellernstrasse 29, 45326 Essen, Germany

(3) Computer Science and Engineering Department, Shanghai Jiao Tong University, Shanghai 200240, China

Correspondence should be addressed to Bin Dai; daibinsjtu@gmail.com

Received 29 November 2012; Accepted 3 January 2013

Academic Editor: Jin Liang
COPYRIGHT 2013 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Dai, Bin; Vinck, A.J. Han; Luo, Yuan
Publication:Journal of Applied Mathematics
Article Type:Report
Date:Jan 1, 2013
Words:11208
Previous Article:A biobjective fuzzy integer-nonlinear programming approach for creating an intelligent location-aware service.
Next Article:Multiple kernel spectral regression for dimensionality reduction.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |