Mar 11, 2013 - wireless communications, and the growing significance of wireless networks. Wyner [1] first introduced the .... The disk Ds â R2 with...

2 downloads 12 Views 168KB Size

Secure Wireless Communications via Cooperative Transmitting Toni Draganov Stojanovski

Ninoslav Marina

University for Information Science and Technology ”St. Paul the Apostle” Ohrid, Macedonia Email: toni [email protected]

Ecole Polytechnique Federale de Lausanne Lausanne, Switzerland Email: [email protected]

Abstract—Information theoretic secrecy is combined with cryptographic secrecy to create a secret-key exchange protocol for wireless networks. A network of transmitters, which already have cryptographically secured channels between them, cooperate to exchange a secret key with a new receiver at a random location, in the presence of passive eavesdroppers at unknown locations. Two spatial point processes: homogeneous Poisson process and independent uniformly distributed points are used for the spatial distributions of transmitters and eavesdroppers. We analyse the impact of the number of cooperating transmitters and the number of eavesdroppers on the area fraction where secure communication is possible. Upper bounds on the probability of existence of positive secrecy between the cooperating transmitters and the receiver are derived. The closeness of the upper bounds to the real value is then estimated by means of numerical simulations. Simulations also indicate that a deterministic spatial distribution for the transmitters e.g. hexagonal and square lattices, increases the probability of existence of positive secrecy capacity compared to the random spatial distributions. For the same number of friendly nodes, cooperative transmitting provides a dramatically larger secrecy region than cooperative jamming and cooperative relaying.

I. I NTRODUCTION Information theoretic secrecy has attracted a significant interest in recent years due to its possible applications in wireless communications, and the growing significance of wireless networks. Wyner [1] first introduced the concept of wiretap channel in 1975. For discrete memoryless channels, he has determined that a message can be transmitted reliably from a transmitter to a receiver without revealing any information on the message to the eavesdropper provided that the transmitter operates at rates smaller than the secrecy capacity. If the main channel and the wiretap channel are additive white Gaussian noise channels, then the secrecy capacity is equal to the difference of the capacities of the two channels as shown by Leung-Yan-Cheong and Hellman in [2]. Csisz´ar and K¨orner [3] extended the previous results to the case of a broadcast channel with confidential messages. Secrecy capacity can be improved using cooperation with friendly nodes. In the cooperative jamming [4], friendly nodes, which are close to the eavesdropper, jam the eavesdropper to help increase the achievable secrecy rates for the transmitter by decreasing the signal-to-noise (SNR) ratio at the eavesdropper. In the cooperative relaying [5], [6], friendly nodes which are closer to the receiver than to the eavesdropper are used as

relays. The relays increase SNR more at the receiver than at the eavesdroppers. Information theory achieves perfect secrecy as opposed to the computational secrecy provided by cryptographic algorithms. Here we examine the possibility for mutual applications of cryptographic secrecy and information-theoretic secrecy. A set of transmitters (e.g. base stations) have already cryptographically secured the communication channels between them. When a transmitter wants to communicate securely with a new receiver (e.g. a mobile station), a presecret key message is created by the transmitter, broken into several data blocks, and a separate block is encrypted and sent to each of the other transmitters. Then each transmitter sends its data block to the receiver. The transmitters ensure that all the data blocks are received correctly at the receiving node, which is required for the computation of the secret key at the receiver. The secret key is securely and cooperatively transmitted to the receiver (without being divulged to the eavesdroppers) if the secrecy capacity is positive for the communication channel between at least one transmitter and the receiver. As the number of transmitters grows, the eavesdroppers are facing a more difficult task of being able to intercept a larger number of transmitters. Once the secret key is exchanged, the legitimate parties can start communicating at the maximum data rate since their communication channel is cryptographically protected achieving computational secrecy [7]. Here is the overview of this paper. In Section II we present the system model. In Section III we address the main research questions of this paper: (i) evaluation of the impact of the spatial distribution of transmitters and eavesdroppers on the secrecy region fraction, and derivation of upper bounds for this fraction; and (ii) comparison with cooperative relaying and cooperative jamming. Section IV concludes the paper. II. N ETWORK

MODEL

We consider two-dimensional wireless networks with the following communication nodes: A network of LT cooperating transmitters, a single receiver, and a network of LE passive eavesdroppers. The passive eavesdroppers do not transmit any signal, and try to intercept the information that is transmitted between the pairs of legitimate nodes, hence reducing the secrecy capability of the network. Their locations are unknown

to the transmitters. Each transmitter is equipped with only a single omni-directional antenna. In the sequel, we use the following notation: L(A) The area of a region A ∈ R2 ; LT A random variable which denotes the number of transmitters in a region A; LE A random variable which denotes the number of eavesdroppers in a region A; b||c A concatenation of two data blocks b and c; V, Ve The additive noise at receiver and eavesdropper, which are independent zero mean Gaussian random variables with variance σ 2 ; Ct,r Capacity of the communication channel between transmitter t and receiver r; Cs:t,r Secrecy capacity between transmitter t and receiver r; Cs Secrecy capacity between a set of cooperating transmitters and a receiver; dj,i The distance between nodes i and j. We use the additive white Gaussian noise model. Then, the received signal at the receiver r from the transmitter t is −β/2

Y = dt,r

X + V.

where X is the transmitted signal from the transmitter t, and β is the path-loss coefficient [8]. The received signal at the eavesdropper e from the transmitter t equals −β/2

Ze = dt,e

X + Ve .

The point to point capacities between transmitter t and receiver r, and between transmitter t and eavesdropper e are given by [2] ! Pt d−β 1 t,r Ct,r = log2 1 + 2 σ2 ! Pt d−β 1 t,e (1) log2 1 + Ct,e = 2 σ2

allows them to communicate secretly with receivers positioned in a larger region. III. C OOPERATIVE

TRANSMITTING

The set of transmitters have already established a cryptographic secret key, and they can cryptographically protect their mutual communication channels. Let assume that transmitter ti and a new communicating node/receiver r want to communicate. ti generates a pre-secret key message B with arbitrary length, which it then divides into LT blocks b1 , b2 , . . . , bLT . Each block is sent to a a different transmitter via a cryptographically secured channel. Then each transmitter ti sends its block bi to the receiver. The intended receiver correctly receives all blocks b1 , b2 , . . . , bLT , and restores the pre-secret key message B = b1 ||b2 || . . . ||bLT . Both ti and r use a cryptographic hash function H to calculate the mutual secret key K = H(B), which is then used to cryptographically protect their mutual communication. The eavesdroppers have to be able to intercept the transmission from all LT transmitters. If at least one data block out of LT data blocks is not intercepted, then the secret key K can not be computed at the eavesdropper. We call this strategy for cooperation - cooperative transmitting. Using cooperative transmitting a transmitter can exchange a secret key with a receiver if the receiver is inside any of the secrecy disks for all LT transmitters. The impact of cooperative transmitting is quantitatively measured through the fraction Fs (A) of a region A covered by the union of secrecy disks. In other words, fraction Fs (A) is equal to the probability of securely exchanging a secret-key with a receiver that is randomly positioned inside the region A Fs (A) ≡ P{Cs > 0} . The coverage problem by secrecy disks was studied by Sarkar and Haenggi [9]. They studied the covered volume fraction and the asymptotic conditions for complete coverage in one and two dimensions. Figure 1 illustrates the concept of cooperative transmitting on a sample network. Receiver r is inside the secrecy disk of transmitter t4 , and therefore block b4 can not be intercepted by any of the eavesdroppers.

Exhaustive cooperative jamming

where Pt is the transmitter’s power. If the point to point capacity between the transmitter and the eavesdropper Ct,e is larger than the capacity of the channel between the two communicating nodes Ct,r , then Cs:t,r = 0. Otherwise, Cs:t,r > 0 [2]: Cs:t,r = max{Ct,r − Ct,e , 0} From Eq. (1) it follows that Cs:t,r > 0 if the receiver r is closer to the transmitter than the eavesdropper, that is, dt,r < dt,e . The disk Ds ⊂ R2 with center at the transmitter and radius equal to the distance between the transmitter and the nearest eavesdropper is called secrecy disk of the transmitter. If a receiver is inside the secrecy disk, then the secrecy capacity between the transmitter and the receiver is positive. Receivers which are outside the secrecy disk for a given transmitter can not communicate securely with that transmitter. In the next section we explain a type of cooperation for a set of friendly transmitter that combines their secrecy disks and thus

Pre-secret key message b1||b2||b3||b4 f

t2

e2

e1

b2 t1

b1 e3

b3

t3

r b4

t4

Secret key K

Fig. 1. Sample network with four transmitters, one new receiver, and three eavesdroppers.

In the remainder of this paper, we analyse the dependence of P{Cs > 0} on the spatial distributions of transmitters and eavesdroppers. We analyse both random and deterministic models for the spatial distribution of transmitters and eavesdroppers. Two simple models for random spatial processes for the transmitters and the eavesdroppers will be used. The first model is homogeneous Poisson process on the plane characterised by the mean number of points λ in a unit area, called also rate or density of the Poisson Process. The number of points l inside a region A follows the Poisson probability distribution law with parameter λL(A) (2)

In the second model a fixed number of points are independently and uniformly distributed (IUD) in a certain region of the plane, characterised by s single parameter - the fixed number of points. These models are widely used in the literature on information theoretic secrecy [9], [10], [11], the reason being twofold. They provide a good first-order approximation for the spatial distribution of communication nodes in real networks. Second, simplicity of the homogeneous Poisson process and IUD process allows for an analytical analysis of information security-related metrics e.g. fraction Fs (A). For the spatial distribution of the transmitters we will also investigate two deterministic models: hexagonal lattice and square lattice. A. IUD transmitters and IUD eavesdroppers In the first case, the position of the transmitters in a region A ∈ R2 obeys a IUD process with parameter nT . Similarly, a fixed number of eavesdroppers nE are positioned according to an IUD process in the same region A. If nT = 1, then Cs > 0 if the receiver is inside the secrecy disk of the transmitter, that is, it is closer to the transmitter than any of the nE eavesdroppers: 1 P{Cs > 0} = 1 + nE

1 0.9 0.8 0.7 0.6

>0}

(λL(A))l −λL(A) e l!

P{Cs>0}

PL (l) =

grows infinitely and the densities of transmitters and eavesdroppers remain constant. Then knE nE = 1 − e−k lim P{Cs > 0} ≤ lim 1 − nE →∞ nE →∞ 1 + nE (5) In order to evaluate the closeness of the upper bounds (4) and (5) to the real value, we have numerically estimated the value for P{Cs > 0}. Figure 2 depicts the dependence of P{Cs > 0} on nT and nE as obtained from the numerical simulations. Each point on the curves is obtained from 100,000 network simulations.

0.5 0.4 0.3 0.2 0.1 0 1

3

5

where the overlapping area of the two secrecy disks is neglected in the upper bound. One can generalise for nT > 1 thus obtaining nT nE P{Cs > 0} ≤ 1 − (4) 1 + nE Next we consider the case when both nT and nE grow infinitely, while their ratio remains constant k = nnET . This is a good first order approximation when the area of region A

11

13

15

17

19

1

nE=1

0.8

nE=5

P{Cs>0}

0.7

1 − P{Cs:1,r

nT

Figure 3 shows the closeness between upper bound given by Eq. (4) and the real values for P{Cs > 0}, which are estimated through numerical simulations. Relative gap between the upper bound and the real values grows for larger nT due to the increasing number of overlapping secrecy disks.

(3)

P{Cs > 0} = 1 − P{Cs < 0} ≤ 2 nE < 0}P{Cs:2,r < 0} ≤ 1 − 1 + nE

9

Fig. 2. Dependence of P{Cs > 0} on the number of transmitters nT with nE as the curves’ parameter. The lowest curve corresponds to nE = 10, and the highest curve is for nE = 1.

0.9

For nT > 1, we establish an upper bound for P{Cs > 0} as follows. For nT = 2, the secrecy region of the two transmitters is union of their secrecy disks:

7

0.6

nE=10

0.5 0.4 0.3 0.2 0.1 0 1

3

5

7

9

nT

11

13

15

17

19

Fig. 3. Closeness between the real value for P{Cs > 0} (circles) and the upper bound (squares) given by Eq. (4).

Figure 4 shows the closeness between the upper bounds (4) and (5), and the numerically estimated values for P{Cs > 0}. Relative gap between the upper bounds and the real values gets smaller for smaller k (larger nE ) since the secrecy disks as well as their overlaps become smaller in size.

1 0.9

0.9

0.8

0.85

0.7

0.8

0.6

P{Cs>0}

P{Cs>0}

1 0.95

0.75

0.7

nE=10

0.4 0.3

0.6

0.2

0.55

0.1

0

0.5 2

3

4

5

k

6

7

8

9

Fig. 4. Closeness between the real value for P{Cs > 0} (circles), and the upper bounds given by Eqs. (4) (squares) and (5) (triangles). nT = 10 and nE = 1, 2, . . . , 10.

3

5

7

9

l

11

13

15

17

19

T

Fig. 5. Closeness between the real value for P{Cs > 0}, and the upper bound given by Eq. (6).

fraction is given by

B. Poisson transmitters and IUD eavesdroppers Next we consider the case where transmitters are positioned according to a Poisson spatial process with rate λT . Without lose of generality of the results, we assume that L(A) = 1 and thus the average number of transmitters in the region A is λL(A) = λ. Eavesdroppers’ positions obey an IUD process and the number of eavesdroppers in the region A is nE . If the number of transmitters LT is 1, then Eq. (3) holds. For LT > 1, the upper bound given by Eq. (4) is valid. Then an upper bound for P{Cs > 0} can be derived as an average value of functions (3) and (4) for the random variable LT : P{Cs > 0} = E [P{Cs > 0|LT }] lT ! lT ∞ X λT −λT nE 1 −λT + 1− λT e e 1 + nE 1 + nE lT ! lT =2

−λT

1 − e 1+nE

1

10

(6)

P{Cs > 0} = E

C. IUD transmitters and Poisson eavesdroppers A fixed number of transmitters nT are positioned at IUD points in a region A ∈ R2 . Positions of eavesdroppers follow a Poisson spatial process with average rate λE . For sake of simplicity we again assume that l(A) = 1 Then the number of eavesdroppers in A is a Poisson random variable LE with average value λE . Its probability distribution function is given by Eq. (2) where λ = λE . For nT = 1, the secrecy region

1 1 + LE

=

1 (1 − e−λE ) λE

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3

0.2 0.1 0 1

Figure 5 shows the closeness between the upper bound (6), and the numerically calculated values for P{Cs > 0}. Similar to Fig. 3, accuracy of the upper bound decreases for larger λT as a consequence of the increasing number of intersecting secrecy disks. Numerical simulation of a Poisson spatial process was done according to [12]. In order to generate a Poisson process with rate λ in a region A, we first randomly select a value l for a Poisson variable with mean λL(A), and then we randomly position l IUD points in A. Observed dependence of P{Cs > 0} on λT and nE was similar to the one depicted in Fig 2.

For nT > 1 we ran numerical simulations, and the results are given in Fig. 6. Note the similarity with Fig. 2.

P{Cs>0}

1

=

nE=5

0.5

0.65

≤

nE=1

3

5

7

9

nT

11

13

15

17

19

Fig. 6. Dependence of P{Cs > 0} on the number of transmitters nT with λE as the curves’ parameter. The lowest curve corresponds to λE = 10, and the highest curve is for λE = 1.

For sake of completeness, we have also numerically analysed the case when a homogeneous Poisson process in a region A ∈ R2 is assumed for both transmitters and eavesdroppers. Again we have obtained very similar results to the previously analysed three combinations of IUD and Poisson spatial processes for transmitters and eavesdroppers. Following slight differences were observed. IUD spatial process for the transmitters gives slightly higher values for P{Cs > 0} than the Poisson spatial processes. On the contrary, the Poisson spatial process for the eavesdroppers gives slightly higher values for P{Cs > 0} than the IUD spatial processes. D. Transmitters in deterministic lattice and UID eavesdroppers Next we analysed the case when the transmitters are positioned on a deterministic lattice, and the eavesdroppers

obey a UID process. By means of numerical simulations we examined a square lattice and a hexagonal lattice. We observed similar shapes to the curves shown in Fig. 2 and Fig. 6 for stochastic spatial processes for the transmitters. P{Cs > 0} is higher for a deterministic lattice compared to a stochastic spatial processes for the transmitters (see Fig. 7) due to the lower variations in the overlap between the secrecy disks of individual transmitters. For a stochastic spatial process, there are areas which can be covered by multiple overlapping secrecy disks of nearby transmitters. At the same time in the regions with sparse transmitters, it is more probable to find subregions not covered by any secrecy disk. 1

Square lattice

0.9

Hexagonal lattice

0.8

P{Cs>0}

0.7

Poisson and IUD spatial processes

0.6

secrecy capacity by increasing SNR at the legitimate receiver more than it increases SNR at the eavesdroppers. We use the value for P{Cs > 0} as a quantitative measure of the positive impact of the different strategies for cooperation. Figure 7 shows that cooperative transmitting offers dramatic improvement in the secrecy region’s size over cooperative jamming and cooperative relaying. IV. C ONCLUSION In this work we propose to combine information theoretic secrecy with cryptographic secrecy to increase the secrecy region, and provide a novel solution to the key-exchange problem. Cooperative transmitting can significantly improve information-theoretic secrecy in wireless networks. The type of cooperation is quite important for the resulting secrecy region. For the same number of friendly nodes, cooperative transmitting provides a larger coverage area than cooperative jamming and cooperative relaying.

0.5

R EFERENCES

0.4

Best jammer 0.3

Best relay UB

0.2

Best relay LB 0.1 0 1

3

5

7

9

nT or l T11

13

15

17

19

Fig. 7. Comparison of stochastic and deterministic positioning of eavesdroppers. Top two curves are for hexagonal and square lattice (IUD eavesdroppers with nE = 5), while middle four curves are for Poisson and IUD spatial processes for the transmitters’ and eavesdroppers’ positions (with λE = 5 or nE = 5). Bottom three curves are for cooperative jamming and cooperative relaying.

E. Comparison with cooperative jamming and cooperative relaying In this section we compare cooperative transmitting with two other strategies for cooperation in wireless networks. Cooperative relaying and cooperative jamming increase the secrecy capacity by means of widening the gap between the SNR at the legitimate receiver and the SNR at the eavesdroppers. In the single hop cooperation with the best relay [13], [14] only the strongest relay is selected from the set of UID randomly positioned relays, which is the relay node which most improves the secrecy capacity. In the ”single hop cooperation with the best jammer” [13], [14] a single node from the set of friendly nodes is selected to act as a jammer. Cooperative jamming aims to reduce the SNR at the legitimate receiver, but at the same time it reduces the SNR even more at the eavesdroppers. On the contrary, the best relay increases the

[1] A. D. Wyner, “The wire-tap channel,” Bell Syst. Tech. J., vol. 54, no. 8, pp. 2–10, October 1975. [2] S. K. Leung-Yan-Cheong and M. E. Hellman, “The Gaussian wire-tap channel,” IEEE Trans. Inf. Theory, vol. 24, no. 4, pp. 451–456, July 1978. [3] I. Csisz´ar and J. K¨orner, “Broadcast channels with confidential messages,” IEEE Trans. Inf. Theory, vol. 24, no. 3, pp. 339–348, May 1978. [4] E. Tekin and A. Yener, “The Gaussian multiple access wire-tap channel: wireless secrecy and cooperative jamming,” Information Theory and Applications Workshop 2007, pp. 404–413, 2007. [5] L. Lai and H. E. Gamal, “The relay-eavesdropper channel: Cooperation for secrecy,” IEEE Trans. Inform. Theory, vol. 54, no. 9, pp. 4005–4019, Sep. 2008. [6] N. Marina, R. Bose, and A. Hjørungnes, “Increasing the secrecy capacity by cooperation in wireless networks,” in Proc. IEEE Symp. Personal and Indoor Mobile Radio Communications (PIMRC), 2009, pp. 1978–1982. [7] C. E. Shannon, “Communication theory of secrecy systems,” Bell Syst. Tech. J., vol. 28, pp. 656–715, pt. I, Oct. 1949. [8] T. S. Rappaport, Wireless Communications: Principles and Practice. Prentice Hall, 1996. [9] A. Sarkar and M. Haenggi, “Secrecy coverage,” in Signals, Systems and Computers (ASILOMAR), 2010 Conference Record of the Forty Fourth Asilomar Conference on, nov. 2010, pp. 42 –46. [10] ——, “Percolation in the secrecy graph,” available online: arXiv:1107.4613v1, Jul 2011. [11] P. C. Pinto, J. Barros, and M. Z. Win, “Wireless physical-layer security: The case of colluding eavesdroppers,” in Proc. IEEE Int. Symp. Inf. Theory, Seoul, Korea, 2009, pp. 2442–2446. [12] D. Moltchanov, “Distance distributions in random networks,” Ad Hoc Networks, vol. 10, no. 6, pp. 1146–1166, Aug. 2012. [13] N. Marina, T. Stojanovski, and H. V. Poor, “Improvement of informationtheoretic secrecy by smart cooperation,” in Information Theory and its Applications (ITA 2012) Workshop, La Jolla, CA, February 2012. [14] ——, “Increasing the information-theoretic secrecy by cooperative relaying and jamming,” in 50th Annual Allerton Conference on Communication, Control, and Computing, October 2012, pp. 42–46.