Mutual Information Games in Multi-user Channels with Correlated Jamming ∗ Shabnam Shafiee Sennur Ulukus 6 Department of Electrical and Computer Engineering 0 0 University of Maryland, College Park, MD 20742 2 sshafi[email protected] [email protected] n a J February 1, 2008 7 2 ] Abstract T I . We investigate the behavior of two users and one jammer in an AWGN channel with and s c withoutfadingwhentheyparticipateinanon-cooperativezero-sumgame, withthechannel’s [ input/output mutual information as the objective function. We assume that the jammer can 2 eavesdrop the channel and can use the information obtained to perform correlated jamming. v 0 We also differentiate between the availability of perfect and noisy information about the 1 user signals at the jammer. Under various assumptions on the channel characteristics, and 1 1 the extent of information available at the users and the jammer, we show the existence, 0 or otherwise non-existence of a simultaneously optimal set of strategies for the users and 6 0 the jammer. In all the cases where the channel is non-fading, we show that the game / s has a solution, and the optimal strategies are Gaussian signalling for the users and linear c jamming for the jammer. In fading channels, we envision each player’s strategy as a power : v allocation function over the channel states, together with the signalling strategies at each i X channel state. We define sub-games at each channel state, given any set of power allocation r functions for the players. Based on our results in the non-fading channels, the sub-games a always have a solution which is Gaussian signalling for the users and linear jamming for the jammer. Given the solution of the sub-games, we reduce the game solution to a set of power allocation functions for the players and show that when the jammer is uncorrelated, the game has a solution, but when the jammer is correlated, a set of simultaneously optimal power allocation functions for the users and the jammer does not always exist. In this case, we characterize the max-min user power allocation strategies and the corresponding jammer power allocation strategy. Index terms: Zero-sum games, eavesdropping, correlated jamming, wireless multi-user secu- rity. ∗ This work was supported by NSF Grants ANI 02-05330, CCR 03-11311, CCF 04-47613 and CCF 05- 14846; and ARL/CTA Grant DAAD 19-01-2-0011,and presented in part at the Conference on Information SciencesandSystems,Baltimore,MD,March2005[1]andtheMilitaryCommunicationConference,Atlantic City, NJ, October 2005 [2]. 1 1 Introduction Correlated jamming, the situation where the jammer has full or partial knowledge about the user signals has been studied in the information-theoretic context under various assumptions [3–5]. In [3] the best transmitter/jammer strategies are found for an AWGN channel with one user and one jammer who participate in a two person zero-sum game with the mutual information as the objective function. The jammer is power constrained and has full or partial knowledge of the transmitted signal which may be obtained through eavesdropping. In [4], the problem is extended to a single-user MIMO fading channel with the assumption that the jammer has full knowledge of the user signal. This model has been further extended in [5] to consider fading in the channel between the jammer and the receiver. In [5] various assumptions are made on the availability of the user channel state at the user, and the jammer channel state at the jammer. In this paper, we study a multi-user system under correlated jamming. Without loss of generality, we consider a system of two users and one jammer who has full or partial knowledge of the user signals through eavesdropping, and examine the existence of optimum user and jammer strategies towards achieving maximum mutual information. In the non- fadingtwouserchannel, weshowthatthegamehasasolutionwhichisGaussiansignallingfor the users, and linear jamming for the jammer. Here we define linear jamming as employing a linear combination of the available information about the user signals plus Gaussian noise, where the available information is the user signals in the case of perfect information, and a noisy version of the user signals in the case of eavesdropping. We show that the power that the jammer allocates for jamming each user’s signal is proportional to that user’s power. We then consider fading in the user channels. As opposed to [5], where the user channel states could only be known at the users, we assume the possibility of the jammer gaining information about the user channel states by eavesdropping the feedback channel from the receiver to the users. We show that if the jammer is not aware of the user channel states, it would disregard its eavesdropping information and only transmit Gaussian noise. If the jammer knows the user channel states but not theuser signals, thegamehas a solutionwhich is composed of the optimal user and jammer power allocation strategies over the channel states, together with Gaussian signalling and linear jamming at each channel state. The optimal power allocations in this case are such that only one user transmits at any given channel state. If the jammer knows the user channel states and the user signals, the game doesnotalwayshaveaNashequilibriumsolution, inwhichcase, wecharacterizethemax-min user strategies, and the corresponding jammer best response. The max-min user strategy corresponds to the user’s best move, in a situation where the user chooses its strategy only once, while after the user chooses its strategy, the jammer can observe it and choose the corresponding best jamming. Note that if the game had a solution, max-min and min-max strategies would have been the same, and would also be the same as the game solution. 2 The term capacity will hereafter always refer to the channel’s informationcapacity, which is defined as the channel’s maximum input/output mutual information [7]. 2 System Model Figure1shows a communication system withtwo users andonejammer. Weconsider several different settings based on the channel characteristics and the jammer’s information. In the absence of fading, the attenuations of the user channels are known to everyone. Therefore, we can assume that the attenuations are scalars. The AWGN channel with two users and one jammer is modelled as Y = h X + h X +√γJ +N (1) 1 1 2 2 p p where X is the ith user’s signal, h is the attenuation of the ith user’s channel, J is the i i jammer’s signal, γ is the attenuation of the jammer’s channel and N is a zero-mean Gaussian random variable with variance σ2 . To model fading in the received powers, we consider h N i and γ as fading random variables, and to further model the phase of the channel coefficients, we substitute the scalar attenuations √h and √γ, with complex fading random variables H i i for the amplitude fading coefficient of the ith user’s channel, and Γ for the amplitude fading coefficient of the jammer’s channel Y = H X +H X +ΓJ +N (2) 1 1 2 2 All fading random variables are assumed to be i.i.d. The user and jammer power constraints are E[X2] P , i = 1,2 (3) i ≤ i E[J2] P (4) J ≤ Regarding the knowledge of the jammer about the transmitted signals, we analyze both cases of perfect information and imperfect information gained through eavesdropping. In the first case, we assume that the jammer knows the signals of the users perfectly, i.e., it knows X and X at the beginning of its transmission. In the second case, we assume an 1 2 AWGN eavesdropping channel for the jammer Y = √g X +√g X +N (5) e 1 1 2 2 e where Y is thesignal received at thejammer, g is theattenuation of theith user’s eavesdrop- e i ping channel and N is a zero-mean Gaussian random variable with variance σ2. Therefore, e e 3 in this case, the jammer knows a noisy version of a linear combination of the user signals, X 1 and X . To model fading in the received powers, we consider √g as real fading variables, 2 i and to model fading in the received amplitudes, we substitute them with complex amplitude fading random variables G . The receiver is assumed to know the user channel states, while i various assumptions are made on the amount of information that the users and the jammer have about the channel fading realization of the communication and eavesdropping channels; these assumptions are stated at the beginning of each subsection. 3 Jamming in Non-fading Multi-user AWGN Channels In this section, we find the best user/jammer strategies when the channels are non-fading, both when the jammer knows the exact user signals, and when it eavesdrops the users’ channel and obtains a noisy version of a linear combination of the user signals. 3.1 Jamming with Complete Information Here the system model is (1) where the attenuations are constant scalars, and X and 1 X are known to the jammer. The jammer and the two users are involved in a zero-sum 2 game with the input/output mutual information as the objective function. We investigate the existence and uniqueness of a Nash equilibrium solution for this game [8]. A Nash equilibrium is a combination of strategies, one for each player, such that no player has an incentive for unilaterally changing its own strategy, meaning that, no player will gain more, by unilaterally deviating from the Nash equilibrium solution. Note that in a zero- sum game, if the objective function is convex over the set of the strategies of the players that are minimizing it, and concave over the set of the strategies of the players that are maximizing it, then the mathematical saddle point of the objective function corresponds to the game’s Nash equilibrium solution. However, in general, all mathematical saddle points of an objective function may not necessarily correspond to a game solution, e.g., matrix games [8]. The arguments in [7, Theorem 2.7.4] can be easily extended to the two user system to show that if (X ,X ,Y) f(x )f(x )f(y x ,x ), the input/output mutual information 1 2 1 2 1 2 ∼ | I(X ,X ;Y) is a concave function of f(x ) for fixed f(x ) and f(y x ,x ), a concave function 1 2 1 2 1 2 | of f(x ) for fixed f(x ) and f(y x ,x ), and a convex function of f(y x ,x ) for fixed f(x ) 2 1 1 2 1 2 1 | | and f(x ). Due to the convexity/concavity of the mutual information with respect to the 2 channeltransitionprobabilitydistribution/userinputprobabilitydistribution,andgiventhat the set of the user and jammer signallings which satisfy the corresponding power constraints is convex, I(X ,X ;Y) has a saddle point in that set, which is the Nash equilibrium solution 1 2 of the game [9, Theorem 16, page 75], [10, Proposition 2.6.9]. In the sequel, we show that 4 when the users employ Gaussian signalling, the best jamming strategy is linear jamming (linear combination of the user signals plus Gaussian noise), and when the jammer employs linear jamming, the best strategy for the users is Gaussian signalling, which proves that Gaussian input distributions for the users and linear jamming for the jammer is a saddle point of the input/output mutual information, and therefore, a Nash equilibrium solution for the game. Due to the interchangeability property of game solutions [9, Theorem 8, page 48], if there is any other pair of strategies which is a game solution as well, it has to result in the same mutual information value as the game solution corresponding to Gaussian signaling and linear jamming [9, Theorem 7, page 48]. First, assume that the jammer employs linear jamming J = ρ X +ρ X +N (6) 1 1 2 2 J The power constraint on the jammer will force the following condition ρ2P +ρ2P +σ2 P (7) 1 1 2 2 NJ ≤ J Using (1), the output of the channel will be Y = ( h +√γρ )X +( h +√γρ )X +√γN +N (8) 1 1 1 2 2 2 J p p From the users’ perspective, the channel becomes an AWGN multiple access channel, and therefore the best signalling scheme for the users is Gaussian [7]. Next, weshouldshowthatiftheusersperformGaussiansignalling,thenthebestjamming strategyislinearjamming. Thechanneloutputisasin(1),whereX andX areindependent 1 2 Gaussian random variables, and J, the jammer signal, is an arbitrary random variable to be chosen by the jammer. We write the input/output mutual information of the channel I(Y;X ,X ) = h(X ,X ) h(X ,X Y) (9) 1 2 1 2 1 2 − | The jammer’s strategy can only affect the second term above. We develop a sequence of upper bounds on the second term, h(X ,X Y) = h(X a Y,X a Y Y) (10) 1 2 1 1 2 2 | − − | h(X a Y,X a Y) (11) 1 1 2 2 ≤ − − 1 log (2πe)2 Λ (12) ≤ 2 | | (cid:0) (cid:1) where Λ is the covariance matrix of (X a Y,X a Y). The inequalities hold for arbitrary 1 1 2 2 − − a and a . We choose a = E[X Y]/E[Y2] and a = E[X Y]/E[Y2]. We now prove the 1 2 1 1 2 2 5 optimality of linear jamming in two steps. We first consider the set of all jamming signals whichresultinthesameΛ, andshowthatifthissetincludesalinearjammer,thenthatlinear jammer isthe optimaljammer over this set. Then, we consider the set of allfeasible jamming signals and show that for any jamming signal in this set, there exists a linear jammer in this set resulting in the same Λ. Here, the feasibility is in the sense of the jammer’s available power. Consider the set of all jamming signals which result in the same Λ in (12). Assume that there is a linear jamming signal in this set. This jamming signal is jointly Gaussian with X and X , hence X a Y, X a Y and Y are jointly Gaussian. Moreover, a and a are 1 2 1 1 2 2 1 2 − − chosen such that X a Y and X a Y are uncorrelated with Y, therefore, since they are 1 1 2 2 − − all Gaussian, X a Y and X a Y are independent of Y. We conclude that this jamming 1 1 2 2 − − signal achieves both (11) and (12) with equality, therefore, it is optimal over this set. Now we show that any Λ achievable by any feasible jamming signal, is also achievable by a feasible linear jamming signal. For the chosen values of a and a , Λ is 1 2 P E[X1Y]2 E[X1Y]E[X2Y] Λ = 1 − E[Y2] − E[Y2] (13) " −E[X1EY[]YE2[]X2Y] P2 − EE[X[Y2Y2]]2 # Using (1), E[X Y], E[X Y] and E[Y2] can be written in terms of E[X J] and E[X J] as 1 2 1 2 E[X Y] = h P +√γE[X J], i = 1,2 (14) i i i i E[Y2] =hpP +h P +2 h γE[X J]+2 h γE[X J]+σ2 +P (15) 1 1 2 2 1 1 2 2 N J p p Therefore, Λ can be expressed as a function of E[X J] and E[X J]. Consider any jamming 1 2 | | signal J. Define R as E[X J] E[X J] 1 2 R = J X X (16) 1 2 − P − P 1 2 Note that R is uncorrelated with X and X . The power of this jamming signal is 1 2 E[X J]2 E[X J]2 E[J2] = 1 + 2 +E[R2] (17) P P 1 2 For this jamming signal to be feasible, we should have E[X J]2 E[X J]2 1 2 + P (18) J P P ≤ 1 2 Now define a linear jamming signal as in (6), where ρ = E[X J]/P , i = 1,2, and N is an i i i J independent Gaussian random variable with power E[R2]. This linear jammer has the same power as J and therefore is feasible. Moreover, it results in the same Λ value as J. Hence, | | 6 for any signal in the set of feasible jamming signals, there is an equivalent linear jamming signal which results in the same upper bound in (12). This means that, there exists a feasible linear jamming signal which is as effective as any other feasible jamming signal, and this concludes the proof. The next step is to find ρ and ρ for the linear jamming signal in (6) which achieves the 1 2 highest upper bound in (12). Since both (11) and (12) hold with equality, the linear jam- ming parameters that maximize (12), maximize (10), or equivalently, minimize the mutual information in (9). Following the literature [3,4], we call this mutual information value, the capacity. Using (8) 1 (√h +√γρ )2P +(√h +√γρ )2P 1 1 1 2 2 2 C = log 1+ (19) 2 γσ2 +σ2 NJ N ! which is a monotonically increasing function of the SNR, therefore the jammer’s equivalent objective is to minimize the SNR value. We have the following minimization problem (√h +√γρ )2P +(√h +√γρ )2P 1 1 1 2 2 2 min {ρ1,ρ2,σN2J} γσN2J +σN2 s.t. ρ2P +ρ2P +σ2 P (20) 1 1 2 2 NJ ≤ J The Karush-Kuhn-Tucker (KKT) necessary conditions are √γ(√h +√γρ )P 1 1 1 +λρ P = 0 (21) γσ2 +σ2 1 1 NJ N √γ(√h +√γρ )P 2 2 2 +λρ P = 0 (22) γσ2 +σ2 2 2 NJ N (√h +√γρ )2P +(√h +√γρ )2P 1 1 1 2 2 2 γ +λ δ = 0 (23) − (γσ2 +σ2 )2 − NJ N where δ is the complementary slackness variable for σ2 . Equations (21) and (22) have the NJ following solution γP +σ2 ρ = h J N (24) 1 1 − √γ(h P +h P ) 1 1 2 2 p γP +σ2 ρ = h J N (25) 2 2 − √γ(h P +h P ) 1 1 2 2 p Therefore whenever these values of ρ and ρ are feasible, they characterize the best jammer 1 2 strategy. Ultimately, including thelimiting feasiblevalues, theoptimumjammingcoefficients 7 are ( √h1, √h2) if γP h P +h P (ρ ,ρ ) = − √γ − √γ J ≥ 1 1 2 2 (26) 1 2 ( ( ρ√h1, ρ√h2) if γPJ < h1P1 +h2P2 − − where P γP +σ2 ρ = min J , J N (27) (rh1P1 +h2P2 √γ(h1P1 +h2P2)) and the jammer transmits as in (6). We observe that the amount of power the jammer allocates for jamming each user is proportional to that user’s effective received power which is h P for user i, i = 1,2. i i Figure 2 shows an example of the jammer decision regions. In region A, (ρ ,ρ ) = 1 2 ( √h /√γ, √h /√γ) and the jammer only uses enough power to zero out the transmitted 1 2 − − signals. In region B, (ρ ,ρ ) = ( √h , √h ) P /(h P +h P ) and the jammer uses all 1 2 1 2 J 1 1 2 2 − − of its power to cancel the transmitted signals as much as possible. In region C, (ρ ,ρ ) = p 1 2 ( √h , √h )(γP +σ2 )/(√γ(h P +h P ))andthejammer usespart ofitspower tocancel − 1 − 2 J N 1 1 2 2 the transmitted signals, and the rest of its power to add Gaussian noise to the transmitted signal. Therefore, for low channel coefficients where the effective received powers of the users are small, the optimum jamming strategy is to subtract the user signals as much as possible, while in high channel coefficients, the jammer uses its power both for adding Gaussian noise and for correlating with the user signals. 3.2 Jamming with Eavesdropping Information Now suppose that the jammer gains information about the user signals only through an AWGN eavesdropping channel, Y = √g X +√g X +N (28) e 1 1 2 2 e We define linear jamming as transmitting a linear combination of the signal received at the jammer Y and Gaussian noise, i.e., e J = ρY +N (29) e J Here, we will prove that in the eavesdropping case as well, linear jamming and Gaussian signalling is a game solution. The proof of the optimality of Gaussian signalling, when the jammer is linear is similar to the previous section as follows. Using (1), (28) and (29), if the 8 jammer is linear, the received signal is Y = ( h +ρ√γg )X +( h +ρ√γg )X +ρ√γN +√γN (30) 1 1 1 2 2 2 e J p p which is an AWGN multiple access channel, therefore, the best signalling for the users is Gaussian. However, when it comes to showing the optimality of linear jamming when the users employ Gaussian signalling, the method of the previous section cannot be used, since from (28) and (29), the values of E[X J] and E[X J] that are achievable through linear jamming, 1 2 should further satisfy E[X J] E[X J] 1 2 = (31) √g √g 1 2 Therefore, linear jamming may not achieve all Λ values in (12) that are allowed under | | the power constraints. Here, we show the optimality of linear jamming, by setting up an equivalent multiple access channel. Define random variables Z and Z in terms of X and 1 2 1 X as 2 √g 2 Z = X + X (32) 1 1 2 √g 1 √g g P g P 1 2 2 1 1 Z = X + X (33) 2 1 2 −g P +g P g P +g P 1 1 2 2 1 1 2 2 It is straightforward to verify that Z and Z are uncorrelated, and hence, independent 1 2 Gaussian random variables. Moreover, since the two pairs have a one-to-one relation, they result in the same input/output mutual information, i.e., I(X ,X ;Y) = I(Z ,Z ;Y) [7]. 1 2 1 2 Therefore, the game’s objective function can be replaced with I(Z ,Z ;Y). Now, using (1), 1 2 (32) and (33), we can rewrite Y in terms of Z and Z as 1 2 Y = u Z +u Z +√γJ +N (34) 1 1 2 2 where √g 1 u = ( g h P + g h P ) (35) 1 1 1 1 2 2 2 g P +g P 1 1 2 2 √pg p 2 u = h h (36) 2 2 1 − √g 1 p p We can also write the eavesdropping signal received at the jammer using (28), (32) and (33) 9 as Y = √g Z +N (37) e 1 1 e Note that Y is independent of Z . Equations (34) and (37) define a two user, one jammer e 2 system, depicted in Figure 3, where the jammer has eavesdropping information only about one of the users, which is the key in proving the optimality of linear jamming as follows. We rewrite the equivalent input/output mutual information as I(Z ,Z ;Y) = h(Z ,Z ) h(Z ,Z Y) (38) 1 2 1 2 1 2 − | The jammer’s strategy can only affect the second term above, h(Z ,Z Y) = h(Z a Y,Z a Y Y) (39) 1 2 1 1 2 2 | − − | h(Z a Y,Z a Y) (40) 1 1 2 2 ≤ − − 1 log(1+ Σ ) (41) ≤ 2 | | where Σ isthecovariance matrix ofZ a Y andZ a Y.Following steps similar tothose in 1 1 2 2 − − the previous section, when the users are Gaussian, employing linear jamming together with a good choice of a and a can make both inequalities hold with equality, and Σ will only 1 2 | | be a function of E[Z J] and E[Z J]. However, Z and J are independent and E[Z J] = 0, 1 2 2 2 therefore, Σ is only a function of E[Z J]. In the sequel, we show that all E[Z J] values 1 1 | | that are achievable by all feasible jamming signals, are also achievable by some feasible linear jamming signal, and therefore, linear jamming achieves (40) and (41) with equality and also achieves the largest possible upper bound in (41). Using (37), the linear least squared error (LLSE) estimate of Z from Y is [11] 1 e E[Z Y ] Z˜ (Y ) = 1 e Y (42) 1 e E[Y2] e e √g E[Z2] = 1 1 Y (43) σ2 +g E[Z2] e Ne 1 1 and the LLSE estimate error is σ2 E[Z2] E[(Z˜ (Y ) Z )2] = Ne 1 (44) 1 e − 1 σ2 +g E[Z2] Ne 1 1 SinceZ andN areGaussian,thisestimateisalsotheminimummeansquarederror(MMSE) 1 e estimate of Z , therefore, any other estimate of Z results in a higher mean squared error. 1 1 Now consider any jamming signal J which is a function of Y , i.e., J = f(Y ), where f is a e e 10