Covert communication refers to scenarios in which reliable communication over a channel must occur while simultaneously ensuring that a separate channel output at a node called the warden has a distribution identical to that induced by an inactive channel symbol [1]- [4]. For discrete memoryless channels (DMC), the inactive input symbol is denoted x 0 . It is known that in a point-to-point DMC without state, if the output distribution (at the warden) induced by x 0 is a convex combination of the output distributions generated by the other input symbols, then it is possible to achieve a positive rate; otherwise the number of possible bits that can be reliably and covertly communicated over n channel transmissions scales at most as O( √ n). This result has motivated the study of other models in which positive rates are achievable.
Of particular relevance to the present work, Lee et al. [5] have considered the problem of covert communication over a state dependent channel in which the channel state is known to the transmitter but unknown to the receiver and the warden. The authors derived the covert capacity when the transmitter and the receiver share a sufficiently long secret key and also derived a lower bound on the minimum length of the secret key needed to achieve the covert capacity. Given the presence of a channel state, one can wonder if covert communication
The work of H. ZivariFard and A. Nosratinia is supported by National Science Foundation (NSF) grant 1514050. The work of M. R. Bloch is supported by National Science Foundation (NSF) grant 1527387.
with positive rate is still possible without requiring an external secret key. In particular, several works demonstrate the benefits of exploiting common randomness and channel states to generate secret keys. For instance, the problem of stealth secret key generation from correlated sources has been studied in [6], [7] and covert secret key generation has been studied in [8], [9]. Most importantly, the usefulness of exploiting states for secrecy has been extensively investigated. The discrete memoryless wiretap channel with random states was first studied by Chen and Han Vinck [10], who studied a scenario in which the CSI is available only at the encoder. They established a lower bound on the secrecy-capacity based on a combination of wiretap coding with Gelfand-Pinsker coding. Generally speaking, the coding scheme with Channel State Information (CSI) outperforms the one without CSI, because perfect knowledge of the CSI not only enables the transmitter to beamform its signal toward the legitimate receiver but also provides a source of common randomness from which to generate a common secret key and enhance the secrecy capacity. Khisti et al. [11] studied the problem of secret key generation from the channel state and established the secret key capacity. Chia and El Gamal studied the state-dependent wiretap channel with weak secrecy, proposing a scheme in which the transmitter and the receiver extract a key from the state, and protect the confidential message via a onetime-pad driven with the extracted key [12] (see also [13] and [14]). Han and Sasaki [15] subsequently extended the coding scheme to achieve strong secrecy. Goldfeld et al. [16] proposed a superposition coding scheme for the problem of transmitting a semantically secure message over a state dependent channel while the channel state is available noncausally at the transmitter.
We study here the problem of covert communications over a state dependent discrete memoryless channel with channel state available non-causally at both the transmitter and the receiver (see Fig. 1). The main innovation of this work is to show that the channel state can be used to simultaneously and efficiently accomplish two necessary tasks: using the channel state for a Gelfand-Pinsker style encoding to assist covert communication while also extracting shared randomness at the two legitimate terminals that is kept secret from the warden, to resolve the multiple codebooks that are necessary for covert communication. The shared randomness extracted from the state effectively takes the place of the external secret key in other models, thus generalizes and expands the applicability of covert communication. We derive an inner bound on the covert capacity of this problem, as well as a condition that shows when this scheme results in a positive rate.
Throughout this paper, random variables are denoted by capital letters and their realizations by lower case letters. The set of -strongly jointly typical sequences of length n, according to P X,Y , is denoted by T
(n) (P X,Y ). For convenience, whenever there is no danger of confusion, typicality will reference the random variables rather than the distribution, e.g., we write T
denote the dimension of a vector, e.g., X n . The integer set {1, . . . , M } is denoted by 1, M , and
The total variation between probability mass functions (pmfs) is defined as ||q-p|| 1 = 1 2
x |p-q| and the Kullback-Leibler (KL) divergence between pmfs is defined as D(P ||Q) =
x p(x) log p(x) q(x) . The support of a probability distribution P is denoted by supp(P ). The n-fold product distribution constructed from the same distribution P is denoted
Consider a discrete memoryless state-dependent channel as shown in Fig. 1. The finite sets (X , S, Y, Z) and the transition probability distribution W Y,Z|X,S are the constitutive components of this channel. Here, X is the channel input, Y and Z are the channel outputs at the legitimate receiver and the warden, respectively. All of these alphabets are finite. Let x 0 ∈ X be a symbol corresponding to the case in which the transmitter is not communicating with the receiver. We assume that the channel state is independent and identically distributed (i.i.d.) and drawn according to
We define a non-negative cost g(x) for every channel input x ∈ X . The average cost of an input sequence
The channel state is available non-causally at both the transmitter and the receiver (see Fig. 1) while the warden does not have access to it. An (|M|, n) code consists of an encoder that maps (M, S n ) to X n ∈ X n , and a decoder at the receiver that maps Y n to M ∈ M. The transmitter and the receiver want to design a code that is both reliable and covert. The code is defined to be reliable if the probability of error P (n) e = P ( M = M ) goes to zero when n → ∞. The code is covert if the warden cannot determine whether communication is happening (hypothesis H 1 ) or not (hypothesis H 0 ). The probabilities of false alarm (accepting H 1 when the transmitter is not sending a meaningful information) and missed detection (accepting H 0 when the transmitter is sending a meaningful information), are denoted by α and β, respectively. We know that a blind test without looking at the channel output satisfies α + β = 1. If P Z n denotes the distribution induced at the warden's output when the transmitter sends a message, the optimal hypothesis test by the warden satisfies α + β ≥ 1 -D(P Z n ||Q n 0 ) [17]. Therefore, to show that the communication is covert it is sufficient to show that D(P
Consequently, our goal is to design a sequence of (2 nR , n) codes such that
We define the covert capacity as the supremum of all achievable covert rates and denote it by C NC .
Our main result is a lower bound for the covert capacity, obtained by designing a coding scheme in which the transmitter not only generates a key from S but also selects its codeword according to S by using a likelihood encoder [18].
Theorem 1. The covert capacity of DMC W Y,Z|S,X with noncausal CSI at the transmitter and the receiver is lowerbounded as
where the maximum is distributions of the form
such that
Remark 1. Theorem 1 suggests that the key rate that we extract from channel state (i.e. H(S|Z)) should be at least as large as the Right Hand Side (RHS) of the (6).
Proof. We adapt a block-Markov encoding scheme over B > 0 consecutive and dependent blocks. This scheme involves the transmission of B -1 independent messages over B channel block transmissions each of length r, indexed by j = 1, 2, ..., B, such that n = rB. Here, we assume B and B -1 are fixed and sufficiently large positive integers. Therefore, the warden's channel output observation Z n can be described as Z n = (Z r 1 , . . . , Z r B ) in which each Z r j for j ∈ 1, B indicates the channel output in block j. Hence, the induced distribution by the coding scheme at output of the
Fig. 2. Functional dependence graph for the block-Markov encoding scheme warden is P Z n P Z r 1 ,...,Z r B and the target output distribution is
where Z B,r j+1 = {Z r j+1 , . . . Z r B }. Therefore, to show
As shown in the following, we achieve this by constructing a code that approximates Q r Z in each block and show that the dependencies across blocks, created by block-Markov coding, can be eliminated. The random code generation is as follows:
Fix P U (u), P U |S (u|s), x(u, s), P S,U,X,Y,Z (s, u, x, y, z) = Q S (s)P U |S (u|s)1 {x(u,s)=x} W Y,Z|X,S , and
Codebook for Key Generation: For each block j ∈ 1, B , to generate an efficient key K j of rate R K by using the channel state S r j , we create a function Φ(S r j ) ∈ 1, 2 rR K through random binning. The key K j = Φ(S r j ) obtained in block j ∈ 1, B is used to assist the encoder in the next block.
Codebook for Message Transmission: For each block j ∈ 1, B and for each k j-1 ∈ 1, 2 rR k , m j ∈ 1, 2 rR , and j ∈ 1, 2 rR , randomly and independently generate 2 rR codewords u r (k j-1 , m j , j ) according to r i=1 p(u i ). These constitute the codebook C n . The indices (k j-1 , m j , j ) can be seen as a two layer binning. We define an ideal Probability Mass Function (PMF) for codebook C n as
) where W Z|U,S is the marginal distribution of W Y,Z|U,S in (5).
Encoding: In the first block, we choose a codeword randomly and transmit it over the channel and use the CSI to generate a key k 1 for the next block. In block j ∈ 2, B , the codeword U r will be chosen based on message, key and the current CSI; simultaneously we generate a key from CSI for the next block.
For the first block, the transmitter generates a key from CSI and the encoder chooses (k 0 , m 1 , 1 ) uniformly at random and finds codeword u r (k 0 , m 1 , 1 ) according to these indices. It then transmits a codeword x r where
For block j ∈ 2, B , to send message m j according to the generated key k j-1 from the previous block and the CSI of the current block, the encoder selects index j from bin (k j-1 , m j ) according to the distribution
where p r S|U is defined from the ideal PMF in (8). Each coordinate of the transmitted signal is a function of the state, as well as the corresponding sample of the transmitter codeword u i , i.e., x i = x(u i (k j-1 , m j , j ), s i ).
For a fixed codebook C n , the induced joint distribution is
Covertness Analysis: Now, we show that this coding scheme guarantees that 19, eq. (323)]. From the expansion in (7), note that for every j ∈ 2, B ,
where (a) is because Z r j -K j -Z B,r j+1 forms a Markov chain as seen in the functional dependence graph depicted in Fig. 2. Next, note that
where Q Kj is the uniform distribution on 1, 2 rR K and (b) follows from
Therefore by combining ( 12) and ( 7), we have
By using the triangle inequality we have:
To bound the first term on the RHS of (15) note that
where ( 18) is due to (9). Hence,
where (c) follows from the symmetry of the codebook construction with respect to M and K j-1 . Based on the soft covering lemma [20,Corollary VII.5] the RHS of (21) vanishes if
To bound the second term on the RHS of (15) note that
where W r S,Z|U = P r S|U W r Z|U,S . Using Pinsker's inequality, it is sufficient to bound
where ( 28) is redundant because of (27).
Decoding and Error Probability Analysis: By following the same steps as in [5], the probability of error vanishes when n grows if
Input Cost Analysis: The proof follows similar lines to [5, Sec V].
The region in Theorem 1 is derived by remarking that the scheme requires R K ≥ R k and applying Fourier-Motzkin to (22), (27), and (29).
S r ,Z r ,U r (s r j , z r j , u r (k j-1 , m j , j )) × 1 2 rR K × log W r S,Z|U (s r j , z r j |u r (k j-1 , m j , j )) 2 r(R k +R+R -R K ) Q r Z (z r j ) + (k j-1 ,m j , j ) =(kj-1,mj , j )
Q r S,Z (s r j , z r j ) 2 r(R k +R+R -R K ) Q r Z (z r j ) + sr j =s r j W r S,Z|U (s r j , z r j |u r (k j-1 , m j , j )) 2 r(R k +R+R ) Q r Z (z r j )
Ψ 1 = kj kj-1 mj j 1 2 r(R k +R+R +R K ) (s r j ,z r j ,u r (kj-1,mj , j ))∈T S r ,Z r ,U r (s r j , z r j , u r (k j-1 , m j , j ))
× log W r S,Z|U (s r j , z r j |u r (k j-1 , m j , j )) 2 r(R k +R+R -R K ) Q r Z (z r j ) + (k j-1 ,m j , j ) =(kj-1,mj , j )
Q r S,Z (s r j , z r j ) 2 r(R k +R+R -R K ) Q r Z (z r j ) + sr j =s r j W r S,Z|U (s r j , z r j |u r (k j-1 , m j , j )) 2 r(R k +R+R ) Q r Z (z r j ) + 1
≤ log 2 rR K 2 -r(1-)H(S,Z|U ) 2 r(R k +R+R ) 2 -r(1+ )H(Z) + 2 rR K 2 -r(1-)H(S,Z) 2 -r(1+ )H(Z) + 2 -r(1-)H(Z|U ) 2 r(R k +R+R ) 2 -r(1+ )H(Z) + 1 (25)
S r ,Z r ,U r (s r j , z r j , u r (k j-1 , m j , j ))
× log W r S,Z|U (s r j , z r j |u r (k j-1 , m j , j )) 2 r(R k +R+R -R K ) Q r Z (z r j ) + (k j-1 ,m j , j ) =(kj-1,mj , j )
Q r S,Z (s r j , z r j ) 2 r(R k +R+R -R K ) Q r Z (z r j ) + sr j =s r j W r S,Z|U (s r j , z r j |u r (k j-1 , m j , j )) 2 r(R k +R+R ) Q r Z (z r j ) + 1