Wireless Physical Layer Security: an Information Theoretic Approach
In:
Submitted By Words 47476 Pages 190
Wireless Physical Layer Security: An Information Theoretic Approach
DISSERTATION Presented in Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in the Graduate School of The Ohio State University By Onur Ozan K¨yl¨o˘lu, B.S., M.S. o u g Graduate Program in Electrical and Computer Engineering The Ohio State University 2010
Dissertation Committee:
Hesham El Gamal, Adviser C. Emre K¨ksal o Ness B. Shroff Atilla Eryılmaz
c Copyright by Onur Ozan K¨yl¨ o˘lu o u g 2010
ABSTRACT
We are in the midst of wireless revolution, and increasing demand continues for wireless applications. This explosive growth, of wireless communications and services, inevitably renders security into a challenging quality of service constraint that must be accounted for in the network design. The state of the art methods in combating the security threats are usually founded on cryptographic approaches. These techniques typically assume limited computational resources at adversaries, are usually derived from unproven assumptions, and most of the time do not offer a measurable security notion. Information theoretic security, on the other hand, eliminates the aforementioned limitations of the cryptographic techniques at the physical layer of communication systems. In this thesis, we concentrate on both the theoretical and the practical aspects of physical layer security. We first start by analyzing elemental interference networks, in particular, two-user channels with an adversary. The problem here is to characterize the fundamental limits on secure transmission rates. Towards this end, we devise coding schemes, forming inner bounds to the capacity region, and compare the achievable rates with outer bounds. This analysis is useful to explore microscopic gains that can be leveraged by the different coding schemes, and our analysis shows that the inherent interference can in fact be exploited to cooperatively confuse the eavesdropping node. ii
We secondly focus on large networks. As the users interfere, the problem here is to identify the optimal ways of distributing network resources among users under the secrecy constraints. Initially, we consider a network with finite number of nodes in the high signal to noise ratio regime, where the noise impairing each receiver is deemphasized compared to the signal strengths. In this asymptotic scenario, we propose efficient interference alignment techniques along with secrecy pre-coding allowing each user to achieve positive secure degrees of freedom. Next, we investigate the secrecy capacity scaling, i.e., the secure rate per user as the number of users gets large. We propose a novel multi-hop forwarding scheme, and, utilizing tools from the percolation theory, we show that each user can achieve the optimal secure rate scaling under a mild condition on the eavesdropper density. The final attempt is on the design of practical coding schemes for physical layer security. Specifically, we show that polar codes achieve non-trivial perfect secrecy rates for a fairly large set of channels with a low encoding and decoding complexity. We also propose a secret key agreement scheme over fading channels. This technique essentially combines physical layer coding schemes with cryptographic methods, and, establishes key agreement by only requiring the statistical knowledge of the eavesdropper channel state information. These results are encouraging in the sense that a) interference can be exploited to enhance security, b) not only small sized networks, but also large networks can achieve information theoretic security, c) there exists practical coding schemes achieving secrecy for a fairly large set of channels, and d) physical layer security can be implemented together with higher layer cryptographic protocols, and hence, allows for cross-layer security solutions. iii
To my family, for their love and support...
iv
ACKNOWLEDGMENTS
First, I wish to express my sincere gratitude to my advisor, Prof. Hesham El Gamal, for his support and guidance during my graduate studies. Without his encouragement and insightful conversations, it would be harder to complete the Ph.D. program. He was not only a research advisor but also a great person with whom I o can discuss diverse issues. I also would like to thank Prof. Can Emre K¨ksal, Prof. Ness B. Shroff, and Prof. Atilla Eryılmaz for agreeing to be in my thesis committee, and providing their comments and feedback. Secondly, I would like to thank my family. My beloved wife Seda K¨yl¨ o˘lu was o u g with me at every step of the Ph.D. program, and I am thankful for her patience and support. She managed to be with me while she was physically away, and I am lucky to conclude this journey together with her. This degree will be one of the first accomplishments of our small family. I also would like to thank to my mother Dr. ˙ Aysun K¨yl¨ o˘lu, my father Dr. Ziya K¨yl¨ o˘lu, and my sister Z. Irem K¨yl¨ o˘lu o u g o u g o u g for their love and support throughout my educational life. They were there when I needed them throughout the years, and I am blessed to have this loving family. This thesis is dedicated to them. I would also like to thank all the people I have interacted with at the Ohio State University, specifically everyone affiliated with the Information Processing Systems (IPS) Laboratory (and Mrs. Jeri McMichael of IPS for the administrative things). I v
am grateful to my housemates Dr. Serdar Vural and Dr. Onur Cant¨ rk Hamsici, for u their friendship and support. In addition, I would like to thank to all my friends in Columbus and my friends back in Turkey for all the fun we had. I also would like to express my gratitude to my co-authors, chronologically, Prof. Hesham El Gamal, Prof. Lifeng Lai, Prof. H. Vincent Poor, Mohammad Shahmohammadi, Karim Khalil, Prof. Moustafa Youssef, Aly El Gamal, Prof. Can Emre K¨ksal, and Liza Toher, for their energy and time. I would like to thank to my undero graduate advisors Prof. Ezhan Kara¸an and Prof. Erdal Arıkan of Bilkent University s for their guidance and support, which was helpful in advancing my research skills and planning of my career. In addition, I am thankful to all of my teachers throughout the years from elementary school to the Ph.D. program, for helping me to create my current skills and personality. Finally, I acknowledge the support of the Graduate School of The Ohio State University, for the University Fellowship and the Presidential Fellowship Awards. This research was also supported in part by the National Science Foundation, Texas Instruments, and Los Alamos National Laboratory.
vi
VITA
September 1983 . . . . . . . . . . . . . . . . . . . . . . . . . . . . Born in Ankara, Turkey May 2005 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .B.S., Electrical and Electronics Engineering, Bilkent University, Ankara, Turkey June 2007 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . M.S., Electrical and Computer Engineering, The Ohio State University, Columbus, OH, USA September 2005-August 2006 . . . . . . . . . . . . . . . University Fellow, The Ohio State University, Columbus, OH, USA September 2006-December 2009 . . . . . . . . . . . . .Grad. Research and Teaching Assoc., The Ohio State University, Columbus, OH, USA January 2010-Present . . . . . . . . . . . . . . . . . . . . . . . Presidential Fellow, The Ohio State University, Columbus, OH, USA October 2010-Present . . . . . . . . . . . . . . . . . . . . . . . Research Intern, Alcatel-Lucent Bell Labs, Holmdel, NJ, USA
PUBLICATIONS
Research Publications 1. O. O. Koyluoglu and H. El Gamal, ”On power control and frequency reuse in the two user cognitive channel,” IEEE Transactions on Wireless Communications, vol. 8, no. 7, pp. 3546-3553, July 2009. vii
2. O. O. Koyluoglu and H. El Gamal, ”Polar coding for secure transmission and key agreement,” in Proc. 2010 IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2010), Special Session on Physical Layer Security, Istanbul, Turkey, Sept. 2010. (invited) 3. L. Toher, O. O. Koyluoglu, and H. El Gamal, ”Secrecy games over the cognitive channel,” in Proc. 2010 IEEE International Symposium on Information Theory (ISIT 2010), Austin, TX, June 2010. 4. O. O. Koyluoglu, C. E. Koksal, and H. El Gamal, ”On the effect of colluding eavesdroppers on secrecy capacity scaling,” in Proc. European Wireless 2010 (EW 2010), Invited Session on Physical Layer Security, Lucca, Italy, Apr. 2010. (invited) 5. O. O. Koyluoglu, C. E. Koksal, and H. El Gamal, ”On the secrecy capacity scaling in wireless networks,” in Proc. 2010 Information Theory and Applications Workshop (ITA 2010), UCSD, La Jolla, CA, Feb. 2010. (invited) 6. A. El Gamal, O. O. Koyluoglu, M. Youssef, and H. El Gamal, ”New achievable secrecy rate regions for the two way wiretap channel,” in Proc. 2010 IEEE Information Theory Workshop (ITW 2010), Cairo, Egypt, Jan. 2010. 7. K. Khalil, M. Youssef, O. O. Koyluoglu, and H. El Gamal, ”On the delay limited secrecy capacity of fading channels,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, June 2009. 8. O. O. Koyluoglu, M. Shahmohammadi, and H. El Gamal, ”A new achievable rate region for the X channel,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, June 2009. 9. O. O. Koyluoglu and H. El Gamal, ”On the secrecy rate region for the interference channel,” in Proc. 2008 IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2008), Special Session on Physical Layer Security, Cannes, France, Sept. 2008. (invited) 10. O. O. Koyluoglu, H. El Gamal, L. Lai, and H. V. Poor, ”On the secure degrees of freedom in the K-user Gaussian interference channel,” in Proc. 2008 IEEE International Symposium on Information Theory (ISIT 2008), Toronto, ON, July 2008. 11. O. O. Koyluoglu and H. El Gamal, ”On the utilization of frequency reuse in cognitive radio channels,” in Proc. IEEE International Symposium on Information Theory (ISIT 2007), Nice, France, June 2007.
viii
FIELDS OF STUDY
Major Field: Electrical and Computer Engineering Studies in: Information Theory, Wireless Communications Stochastic Processes Optimization Theory Control Theory Prof. Prof. Prof. Prof. Hesham El Gamal Randolph Moses Atilla Eryılmaz Vadim Utkin
Figure 1.1 Shannon’s secrecy system. The encoder has the message W and transmits X. The received sequences at the decoder and at the eavesdropper are Y and Ye , respectively; and, it is assumed that Y = Ye = X. The secret key, K, is shared between encoder and decoder. The enemy node, eavesdropper, does not have the knowledge of the key. . . . . . Wyner’s wiretap channel model. The transmitted sequence, X, enters to the noisy channel given by p(y, ye|x), which generates the channel outputs Y and Ye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The discrete memoryless interference channel with an eavesdropper (IC-E). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Random codebook of Shannon. To transmit a message, the codeword indexed by the message is transmitted. . . . . . . . . . . . . . . . . . Randomized codebook of Wyner. For a given message index, a column is randomly chosen, and the corresponding channel input is transmitted. Designing the number of columns properly is the key to prove that the security constraint is met. We refer to this codebook as randomized (two-dimensional) codebook. . . . . . . . . . . . . . . . . . . . . . . . Proposed encoder structure for the IC-E. . . . . . . . . . . . . . . . . Numerical results for GIC-E with h12 = h21 = 1.9, h1e = h2e = 0.5, P1 = P2 = 10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numerical results for GIC-E with h12 = h21 = 0.6, h1e = h2e = 1.1, P1 = P2 = 10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Page
5
1.2
6
2.1
17
2.2
21
2.3
21 23
2.4 2.5
33
2.6
34
xiii
2.7
Numerical results for GIC-E with h12 = 1.9, h21 = 1, h1e = 0.5, h2e = 1.6, P1 = P2 = 10. . . . . . . . . . . . . . . . . . . . . . . . . . K-user interference channel with confidential messages. . . . . . . . . K-user interference channel with an external eavesdropper. . . . . . . Proposed encoder and decoder architecture for user k in the K-user interference channel with confidential messages. . . . . . . . . . . . . Proposed codebook structure for user k. The secret message of user k results in the bin index wk and the randomization index for the x corresponding user is wk . Considering these two indices, each entry of x ˆ the codebook is denoted as Xk (wk , wk ). . . . . . . . . . . . . . . . . . A typical multi-hop route consists of four transmission phases: 1) From source node to an entry point on the horizontal highway, 2) Across horizontal highway (message is carried until the desired vertical highway member), 3) Across vertical highway (message is carried until the exit node), and 4) From the exit node to the destination node. . . . . . . The transmitter located at the center of the figure wishes to communicate with a receiver that is d squares away. The second square surrounding the transmitter is the secrecy zone, which is the region of points that are at most fe d squares away from the transmitter. Side length of each square is denoted by c. The time division approach is represented by the shaded squares that are allowed for transmission. It is evident from the dashed square that the time division requires (ft d)2 time slots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Horizontal and vertical edges in the discrete bond percolation model are denoted by dotted lines. A dotted edge is open (used for the highway construction) if the corresponding square is open. There are Θ(n) number of edges in the random graph. . . . . . . . . . . . . . . . . . There are ⌈δ log n⌉ number of disjoint highways within each rectangle √ of size (κ log n − ǫ) × n. The legitimate users in the slab, denoted by dotted lines, of the rectangle is served by the highway denoted with red bold line. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35 43 46
3.1 3.2 3.3
48
3.4
50
4.1
71
4.2
72
4.3
81
4.4
82
xiv
C.1 The second square surrounding the transmitter is the secrecy zone (zone of level 1), which is the region of points that are at most fl1 d squares away from the transmitter. The zone of level k is denoted with distance flk dc and has an area of Alk . . . . . . . . . . . . . . . . . . . 153
xv
CHAPTER 1
Introduction
We are in the midst of wireless revolution, and increasing demand continues for wireless consumer, military, public, and scientific applications. Technologies like Wireless LANs, Bluetooth, and Cellular Networks have increased the consumer potential; and users keep requesting for higher data transfer rates. Wireless networks can be deployed rapidly and failure of some nodes does not imply the failure of the whole network; making the military potential also evident (e.g., surveillance applications). Defense and public safety applications are of definite interest for governmental entities. Finally, scientific applications include data collection and event detection based on wireless sensor nodes. In fact, the wireless revolution is just beginning, especially due to the advance of new technologies like WiMAX, Mesh Networks, and Smart (Cognitive) Radio Networks. This explosive growth, of wireless communications and wireless based services, has lead to an increased focus on the security aspect of these systems. For example, how can we ensure that a wireless transaction is secure? Indeed, due to the broadcast nature of the wireless communications, the transmissions are susceptible to eavesdropping. In other words, an adversary, eavesdropper, can listen the transmissions and try to obtain some meaningful information. Therefore, it is imperative to design secure wireless systems, to ensure their continued growth and 1
well being. At this point, security arises as a new quality of service (QoS) constraint that must be accounted for in the network design. The state of the art technique in combating eavesdropping attacks is to utilize cryptographic approaches, which can be broadly classified into public-key and privatekey protocols. Public-key cryptography assumes that the eavesdropper(s) has limited computational power, whereas the decryption requires a significant complexity without the knowledge of the key [1, 2]. Private-key approaches , on the other hand, assume that a random key is shared in private between the legitimate transmitter and receiver. This key is used to secure the transmitted information from potential eavesdropper(s). One of the earliest examples of private-key cryptography is the Vernam’s one time pad scheme [3], where the transmitter sends the XOR of the message bits and key bits. The legitimate receiver can then decode the messages by XORing the shared key with the received sequence. In such cryptographic approaches, the security is guaranteed by designing a protocol such that it is computationally prohibitive for the eavesdropper to decode the message. These protocols are heavily based on unproven assumptions such as hardness of factoring large primes [2]. Thus, it remains unknown whether the protocols will be vulnerable to attacks with novel algorithms and/or increased computational power at the eavesdropper. In fact, most of the cryptographic protocols require upgrades and patches in order to increase the security level. For instance, cryptographic hash functions, such as SHA-1, are extensively used in cryptography. Yet, as there is no rigorous mathematical proofs for the security of such functions, there is always the chance of a surprise attack [2]. Indeed, some attacks (see, e.g., [4]) cast doubts on the security of SHA-1, which was an improvement over SHA-0 ([5]), and federal agencies 2
like National Institute of Standards and Technology (NIST) enforces entities not to use SHA-1 and switch to protocols using SHA-2 by 2010 [6]. In addition to these drawbacks, some cryptographic protocols require deploying secret keys at users, which might be highly costly for some applications, such as energy-limited sensor networks. Information theoretic security, first proposed by Shannon in [7], avoids the aforementioned limitations of the computational based approach and is even called as provable security. Shannon [7] considered noiseless links and an eavesdropper with unlimited computational power (Fig. 1.1); and, introduced a notion of secrecy. According to his secrecy notion, the eavesdropper must get zero information regarding the transmitted message, i.e., I(W ; Ye ) = 0 must be satisfied. Shannon showed that this can be guaranteed for the Vernam’s one time pad scheme only if the transmitterreceiver pair shares a secret key, which has higher entropy than that of the message, i.e., H(K) ≥ H(W ). This result is pessimistic in the sense that one needs to send/share a key that has a length at least that of the message. If such a secret key can be shared, then the message will be sent securely instead of the key. The result of Shannon was mainly based on the assumption of the noiseless channel between the nodes. Actually, wireless channels are noisy and the quality of the channel varies across time. In fact, this property can be exploited to enhance the security of the network. Accordingly, Wyner [8] considered the wiretap channel model, in which the eavesdropper has degraded (more noisy) observations from the channel compared to that of the legitimate receiver, i.e., the eavesdropper is said to be degraded (Fig. 1.2). Under this assumption, Wyner showed that the advantage of the main channel over that of the eavesdropper, in terms of the lower noise level, can be
3
exploited to transmit secret bits using random codes.
1
In other words, it is possible
to achieve a non-zero secret rate without sharing a key, where the eavesdropper is limited to learn almost nothing from the transmissions. In particular, Wyner characterized the tradeoff between the message rate and the level of ignorance of the message at the wiretapper, i.e., equivocation rate. In such a setting, perfect secrecy is said to be achieved if the message rate, H(W )/N, can be made arbitrarily close to the equivocation rate, H(W |Ye )/N, which measures the remaining uncertainty in W after observing Ye , in the limit of large number of channel uses, N. (That is, as I(W ; Ye ) = H(W ) −H(W |Ye ), I(W ; Ye )/N is made small.) This notion, if satisfied, assures that the wiretapper gains only a negligible amount of information regarding the message per channel use. This keyless secrecy result was then extended to a more general (broadcast) model in [9] and to the Gaussian setting in [10]. A more stronger notion of secrecy compared to Wyner’s is proposed in [11], where, instead of the mutual information per channel use, the authors required cumulative information leakage, i.e., I(W ; Ye ), to be arbitrarily small to say that the system is secure. Recently, there has been a growing interest in the analysis and design of secure wireless communication networks based on information theoretic principles (see, e.g., Special Issue on Information Theoretic Security, IEEE Trans. Inf. Theory, June 2008 and references therein). For example, the secrecy capacity of relay networks was studied in [12–20], while the role of feedback in secure communications were analyzed by [21–26]. In addition, the two-way, multiple access, and broadcast channels
1 Wyner’s coding scheme will be introduced in the next chapter in the context of two user interference channels. We note that, we will refer to Wyner’s encoding technique as randomized (two-dimensional) encoding in the rest of the sequel. See also Remark 2.3.
4
K Y W Encoder X Ye Decoder
ˆ W
Eavesdropper
H(W |Ye )
Figure 1.1: Shannon’s secrecy system. The encoder has the message W and transmits X. The received sequences at the decoder and at the eavesdropper are Y and Ye , respectively; and, it is assumed that Y = Ye = X. The secret key, K, is shared between encoder and decoder. The enemy node, eavesdropper, does not have the knowledge of the key.
with secrecy constraints were investigated in [26–29], [22, 23, 30–37], [9, 14, 38– 54]. Finally, the role of multiple antennas in enhancing the secrecy capacity was established in [40, 47, 48, 51, 53, 55–64], and the impact of fading on secrecy capacity was revealed in [33, 41, 42, 57, 65–70]. Yet, the field of physical layer security is still not that mature and the followings are, arguably, the essential open problems in this context. First, there is little known regarding the information theoretic security of large networks with multiple users. Multi-user networks are interference limited, i.e., the throughput of users can be severely affected by the interfering transmissions; and, the problem of interference management becomes more daunting under the security constraints. And secondly, practical algorithms, such as efficient code designs, are needed in order to put the physical layer security into practice. This thesis focuses on these aspects of physical layer security, and, in particular, analyzes elemental (small) interference networks, performance scaling for large interference networks (in the asymptotic limits of high power and large number of users), and code design for 5
Y W Encoder X Channel p(y, ye|x) Ye
Decoder
ˆ W
Eavesdropper
H(W |Ye)
Figure 1.2: Wyner’s wiretap channel model. The transmitted sequence, X, enters to the noisy channel given by p(y, ye|x), which generates the channel outputs Y and Ye .
physical layer security. The results are encouraging in the sense that a) interference can be exploited to enhance security, b) not only small sized networks, but also large networks can achieve provable secrecy, c) there exists practical coding schemes achieving the secrecy capacity of a fairly large set of channels, d) physical layer security can be implemented together with higher layer cryptographic protocols, and hence, allows for cross layer security solutions. In the rest of this chapter, we summarize the contributions of this thesis, provide an outline of the sequel, and introduce the notation used in the text.
1.1
Contributions
This thesis, based on information theoretic principles, proposes innovative approaches and provides novel results in physical layer security. In particular, the focus is on information theoretic security for interference networks and the code design for physical layer security. We divide the analysis into the following four parts, each focuses on the different aspects of the physical layer security and reveals interesting insights based on information theoretic principles. 6
1.1.1
Elemental Networks
We focus on networks with small number of users, in particular, the two-user channels with an adversary (an eavesdropper external to the network). The problem is to characterize the secrecy capacity of such small networks. Towards this end, we devise coding schemes, forming inner bounds to the capacity region, and compare the achievable rates with outer bounds to the capacity region. This analysis is useful to explore microscopic gains that can be leveraged by the different coding schemes. Our contributions can be summarized as follows. • We first focus on the discrete memoryless two-user interference channel in the presence of an external eavesdropper. In this setting, we construct an inner bound, to the secrecy capacity region, based on the idea of cooperative encoding and channel prefixing, in which the two users cooperatively design their randomized codebooks and jointly optimize their channel prefixing distributions. Our achievability scheme also utilizes message-splitting in order to allow for partial decoding of the interference at the non-intended receiver. • We derive outer bounds to the secrecy capacity region and use them to establish the optimality of the proposed scheme in certain cases. • We analyze the proposed coding scheme in the context of multiple-access and relay channels, where we characterize the secrecy sum capacity for the former and the secrecy capacity for the latter in some special cases. • In the Gaussian case, the previously proposed cooperative jamming and noiseforwarding techniques are shown to be special cases of our proposed approach. 7
Overall, our results provide structural insights on how the interference can be exploited to increase the secrecy capacity of wireless networks.
1.1.2
Degrees of Freedom
We focus on networks with arbitrary but finite number of interfering users. As the users interfere, the problem is to identify the optimal ways of distributing the network resources among the users under the secrecy constraints. In order to derive insights on the interference management problem in the presence of secrecy constraints, we focus on the high signal to noise ratio (SNR) regime, where the noise impairing each receiver is deemphasized compared to the strengths of the intended signals and interference. In this asymptotic scenario, the relevant metric to consider is the degrees of freedom (DoF) per user. DoF (also called as multiplexing gain or the pre-log term [71],[72]) per user can be defined as follows: A user is said to have d DoFs if its rate scales as d log(SNR) + o(log(SNR)). Thus, DoF approximates the achievable rate in the high SNR regime by eliminating the terms of order o(log(SNR)). In our approach, we analyze the high SNR regime and reduce the problem to the characterization of the achievable secure degrees of freedom (DoF) per user. Our contributions can be summarized as follows. • We focus on the frequency/time selective K-user Gaussian interference channel with two different secrecy constraints, namely, a) the confidential message case, and b)the external eavesdropper scenario. • Using interference alignment along with secrecy pre-coding, we show that each user can achieve non-zero secure Degrees of Freedom (DoF) for both cases. More precisely, the proposed coding scheme achieves 8
K−2 2K−2
secure DoF with probability
one per user in the confidential messages model. For the external eavesdropper scenario, on the other hand, we show that each user can achieve DoF in the ergodic setting. • We characterize the impact of channel state information (CSI) on the secure transmission problem. In particular, the key difference between the two models is the lack of channel state information (CSI) about the external eavesdropper. • Noting that the secure DoF for the point-to-point Gaussian channel is vanishing (i.e., the secrecy capacity scales as o(log SNR) as SNR → ∞ [10],[66]), our results interestingly establish the positive impact of interference on the secrecy capacity region of wireless networks.
K−2 2K
secure
1.1.3
Capacity Scaling in Large Networks
There is an inherent limitation of the above DoF approach: The DoF characterization assumes finite number of users, and hence the analysis does not shed light on the rate scaling as the number of users get large for a given finite SNR. Here, we focus on large networks and the problem we face is the characterization of the achievable rate per user as the number of users approaches to infinity. We list our contributions as follows. • First, we consider a path loss model (α > 2) with stochastic node distribution: The legitimate and eavesdropper nodes are assumed to be placed according to Poisson point processes with intensities λ and λe , respectively. This model is used to analyze extended and dense networks, which have a network area of n with λ = 1 and a unit-area network with λ = n, respectively. We show that, as 9
long as λe /λ = o ((log n)−2 ), almost all of the nodes achieve a perfectly secure rate of Ω
1 √ n
for the two models. Therefore, under these assumptions, securing
the transmissions of nodes does not entail a loss in the per-node throughput in terms of scaling. The achievability argument is based on a novel multihop forwarding scheme where randomization is added in every hop to ensure maximal ambiguity at the eavesdropper(s). • Secondly, we consider an ergodic fading model, where the network consists of n source-destination pairs and ne eavesdroppers. Employing the ergodic interference alignment scheme with an appropriate secrecy pre-coding, each user is shown to achieve secrecy. In particular, the proposed scheme allows
1 each user to achieve a secure degrees of freedom (DoF) of η = [ 1 − n ]+ in 2
the high SNR regime even with the absence of eavesdropper CSI. Remarkably, secure throughput of each node increases as we add more legitimate users to the network in this setting. • Finally, we investigate the effect of eavesdropper collusion on secrecy capacity scaling. In particular, when all the eavesdroppers collude, the proposed multi-hop scheme allows for achieving the same rate scaling under a similar eavesdropper intensity requirement for the path loss model; and, for the fading model, each user can achieve a secure DoF of η = [ 1 − 2 regime with the proposed interference alignment scheme. ne + ] n
in the high SNR
1.1.4
Code Design
Wyner’s work on wiretap channels and the recent works on information theoretic security are based on random codes. Achieving information theoretical security with 10
practical coding schemes is of definite interest. In our last focus, the attempt is to overcome this elusive task by employing the polar coding technique of Arıkan. We summarize our contributions as follows. • We show that polar codes achieve non-trivial perfect secrecy rates for binaryinput degraded wiretap channels while enjoying their low encoding-decoding complexity. In the special case of symmetric main and eavesdropper channels, this coding technique achieves the secrecy capacity. • We discuss the extension of the coding technique to the multiple-access channels with a degraded eavesdropper. • Finally, we consider the fading erasure wiretap channel and propose a secret key agreement scheme, which requires only the statistical knowledge of the eavesdropper channel state information (CSI). The enabling factor is the creation of advantage over Eve, by blindly using the proposed scheme over each fading block, which is then exploited with privacy amplification techniques to generate secret keys. We also provide extensions of the proposed scheme to other channel models.
1.2
Outline
Next four chapters of this thesis cover the contributions stated in the previous section. In Chapter 2, we focus on the elemental network consisting of two users, and detail the degrees of freedom analysis for the K-user network in Chapter 3. Chapter 4 is devoted to the large network scenario, where we focus on the secrecy capacity scaling of networks. In Chapter 5, we consider the problem of code design 11
for physical layer security, where we introduce a polar coding scheme for confidential message transmission in discrete memoryless point-to-point channels and multipleaccess channels, and propose a key agreement scheme for fading channels. In the last part of this thesis, Chapter 6, we offer some concluding remarks along with possible future directions. To enhance the flow of the thesis, some proofs and lemmas are relegated to the Appendix and the notation we use in this thesis is introduced in the next section.
1.3
Notations
In this section, we introduce the notation used in the rest of the sequel (unless otherwise stated). Random variables are denoted with capital letters X, which are defined over sets denoted by the calligraphic letters X . A realization of a random variable (say X) is denoted with small case letters (x). For simplicity, we use the following shorthand for probability distributions: p(x) p(X = x), p(x|y) p(X = x|Y =
y). The same notation will be used for joint distributions. Vectors are denoted as xi = {x(1), · · · , x(i)}. Here, we will omit the superscript i if i = N, i.e.,
x = {x(1), · · · , x(N)}. We will also use the notation x if we omit the indices. ¯ (This notation will be clear from the text.) Random vectors are represented with bold-capital letters Xi = {X(1), · · · , X(i)}. Again, we drop the superscript i for X = {X(1), · · · , X(N)}. For a given set S, the sum of the communication rates Rk for k ∈ S is represented with RS Rk . For a number (x), a vector (x), and a random vector (X), the k∈S 12
subscript S is used in order to denote the collection of variables, i.e., xS xS {xk |k ∈ S}, and XS We define [x]+ {Xk |k ∈ S}.
{xk |k ∈ S},
max{0, x} for any given x ∈ ℜ and α ¯
1 − α for any given
α ∈ ℜ. We denote the logarithm function with respect to base 2 as log(.) and the natural logarithm function as ln(.). The delta function δ(x) is defined as δ(x) = 1, if x = 0; δ(x) = 0, if x = 0. A zero-mean Gaussian random variable with variance σ 2 is denoted by N (0, σ 2). In addition, a zero-mean circularly symmetric complex Gaussian random variable with variance σ 2 is denoted by CN (0, σ 2). (Note that this random variable has real and imaginary parts distributed according to N (0, σ 2/2).) Finally, we introduce the Landau’s notation used in the sequel: We say f (n) = O(g(n)), if there exists a constant k and n0 such that f (n) ≤ kg(n), for all n ≥ n0 . We also say that f (n) = Ω(g(n)), if g(n) = O(f (n)). We denote f (n) = Θ(g(n)), if f (n) = O(g(n)) and f (n) = Ω(g(n)). Lastly, we say f (n) = o(g(n)), if lim f (n) n→∞ g(n)
= 0.
13
CHAPTER 2
Security in Two-User Interference Channels
In this chapter, we focus on two-user interference channels with security constraints. The two-user interference channel refers to a communication network consisting of two source-destination pairs. In this network, the output of the channel seen at each destination is affected by the channel input of both sources, and therefore, users are said to interfere each other. This channel model (without the security constraints) has been widely investigated in the literature. The best known achievable rate region is given by Han and Kobayashi [73]; and is simplified in [74]. However, except for some special cases (e.g., [75–79]), characterizing the capacity region of the two-user Gaussian interference channel remains as an open problem. On the other hand, recent attempts have shed light on the fundamental limits of the interference channels with confidential messages [43, 80], where each source would like to transmit its message to its respective destination while securing it from the non-intended destination. In our model, we focus on the external eavesdropper scenario, which has not been addressed adequately in the literature. Our work develops a general approach for cooperative encoding and channel prefixing for the (discrete) two-user memoryless interference channels operated in the
14
presence of a passive eavesdropper. The proposed scheme allows for cooperation in two distinct ways: 1. The two users jointly optimize their random codebooks [8], and 2. They jointly introduce randomness in the transmitted signals, to confuse the eavesdropper, via a cooperative channel prefixing approach [9]. Our scheme also utilizes message splitting and partial decoding to enlarge the achievable secrecy rate region [73]. We then derive outer bounds to the secrecy capacity region and use them to establish the optimality of the proposed scheme for some classes of channels. We also argue that some coding techniques for the secure discrete multiple access channel and relay-eavesdropper channel can be obtained as special cases of our cooperative encoding and channel prefixing approach. Recently, noise forwarding (or jamming) has been shown to enhance the achievable secrecy rate region of several Gaussian multi-user channels (e.g., [56] , [27]). The basic idea is to allow each transmitter to allocate only a fraction of the available power for its encoding codebook and use the rest for the generation of independent noise samples. The superposition of the two signals is then transmitted. With the appropriate power allocation policy, one can ensure that the jamming signal results in maximal ambiguity at the eavesdropper while incurring only a minimal loss in the achievable rate at the legitimate receiver(s). Our work reveals the fact that this noise injection technique can be obtained as a manifestation of the cooperative channel prefixing approach. Based on this observation, we obtain a larger achievable region for the secrecy rate in the Gaussian multiple access channel.
15
The rest of this chapter is organized as follows. Section 2.1 is devoted to the discrete memoryless scenario where the main results are derived and few special cases are analyzed. The analysis for the Gaussian channels, along with numerical results in selected scenarios, are given in Section 2.2. The proofs of the theorems and corollaries are relegated to the Appendix A.
2.1 2.1.1
The Discrete Memoryless Channel System Model
The discrete memoryless two-user interference channel with an (external) eavesdropper (IC-E) is denoted by (X1 × X2 , p(y1, y2 , ye |x1 , x2 ), Y1 × Y2 × Ye ), for some finite sets X1 , X2 , Y1 , Y2, Ye (see Fig. 2.1), where the symbols (x1 , x2 ) ∈ X1 × X2 are the channel inputs and the symbols (y1 , y2, ye ) ∈ Y1 × Y2 × Ye are the channel outputs observed at the decoder 1, decoder 2, and at the eavesdropper, respectively. The channel is memoryless and time-invariant: i−1 i−1 i−1 p(y1(i), y2 (i), ye (i)|xi , xi , y1 , y2 , ye ) 1 2
= p(y1 (i), y2 (i), ye (i)|x1 (i), x2 (i)). In this two-user network, each source k ∈ {1, 2} has a secret message Wk , to be transmitted to the respective destination in N channel uses and to be secured from the eavesdropper. In this setting, an (N, M1 , M2 , Pe,1, Pe,2) secret codebook has the following components: 1. The secret message set Wk = {1, ..., Mk }; k = 1, 2. 16
W1
Encoder 1
X1
Y1
Decoder 1
ˆ W1
Channel p(y1 , y2 , ye |x1 , x2 ) W2 X2 Y2 ˆ W2
Encoder 2
Decoder 2
Ye
Eavesdropper
H(W1 , W2 |Ye )
Figure 2.1: The discrete memoryless interference channel with an eavesdropper (ICE).
2. A stochastic encoding function fk (.) at transmitter k which maps the secret messages to the transmitted symbols: fk : wk → Xk for each wk ∈ Wk ; k = 1, 2. 3. Decoding function φk (.) at receiver k which maps the received symbols to an estimate of the message: φk (Yk ) = wk ; k = 1, 2. ˆ The reliability of transmission is measured by the following probabilities of error Pe,k 1 M1 M2 Pr {φk (Yk ) = wk |(w1 , w2 ) is sent} ; k = 1, 2.
(w1 ,w2 )∈W1 ×W2
The secrecy is measured by the equivocation rate 1 H (W1 , W2 |Ye ) . N The rate tuple (R1 , R2 ) is said to be achievable for the IC-E, if, for any given ǫ > 0, there exists an (N, M1 , M2 , Pe,1 , Pe,2) secret codebook such that the following 17
equations hold for sufficiently large N. 1 log(M1 ) = R1 , N 1 log(M2 ) = R2 , N max{Pe,1 , Pe,2} ≤ ǫ, R1 + R2 − 1 H (W1 , W2 |Ye ) ≤ ǫ. N (2.1)
The secrecy capacity region is the closure of the set of all achievable rate pairs (R1 , R2 ) and is denoted as CIC-E . We note the following. Remark 2.1. The secrecy requirement imposed on the full message set implies the secrecy of individual messages. In other words,
1 I(Wk ; Ye ) N 1 I(W1 , W2 ; Ye ) N
≤ ǫ implies that
≤ ǫ for k = 1, 2.
We finally introduce the following notation that we use in this chapter. For any two dimensional codebook that we use for secrecy, we will have 2nR rows (bins) and 2nR columns (codewords per bin), where we refer to R as the secrecy rate and Rx as the randomization rate. x 2.1.2
Inner Bound
In this section, we introduce the cooperative encoding and channel prefixing scheme, which establishes an inner bound to CIC-E . The proposed strategy allows for cooperation in both the design of the secrecy codebooks and channel prefixing [9]. This way, each user will add only a sufficient amount of randomness as the other user will help to increase the randomness seen by the eavesdropper. The achievable secrecy rate region using this scheme is given by the following result.
18
Theorem 2.2. RIC-E the closure of p∈P R(p)
⊆ CIC-E ,
(2.2)
where P denotes the set of all joint distributions of the random variables Q, C1 , S1 , O1 , C2 , S2 , O2 , X1 , X2 that factors as
2
p(q, c1 , s1 , o1 , c2 , s2 , o2 , x1 , x2 ) = p(q)p(c1 |q)p(s1|q)p(o1 |q)p(c2 |q)p(s2|q)p(o2 |q) p(x1 |c1 , s1 , o1 )p(x2 |c2 , s2 , o2 ), and R(p) is the closure of all (R1 , R2 ) satisfying R1 = RC1 + RS1 , R2 = RC2 + RS2 , x x x x (RC1 , RC1 , RS1 , RS1 , RC2 , RC2 , RO2 ) ∈ R1 (p), x x x x (RC2 , RC2 , RS2 , RS2 , RC1 , RC1 , RO1 ) ∈ R2 (p), x x x x x x (RC1 , RS1 , RO1 , RC2 , RS2 , RO2 ) ∈ Re (p),
(2.3)
and x x x RC1 ≥ 0, RC1 ≥ 0, RS1 ≥ 0, RS1 ≥ 0, RO1 ≥ 0, x x x RC2 ≥ 0, RC2 ≥ 0, RS2 ≥ 0, RS2 ≥ 0, RO2 ≥ 0,
(2.4)
x x for a given joint distribution p. Here, R1 (p) is the set of all tuples (RC1 , RC1 , RS1 , RS1 , x x RC2 , RC2 , RO2 ) satisfying
2 Here Q, C1 , S1 , O1 , C2 , S2 , and O2 are defined on arbitrary finite sets Q, C1 , S1 , O1 , C2 , S2 , and O2 , respectively.
19
R2 (p) is the rate region defined by reversing the indices 1 and 2 everywhere in the x x x x x x expression for R1 (p). Re (p) is the set of all tuples (RC1 , RS1 , RO1 , RC2 , RS2 , RO2 )
satisfying x RS ≤ I(S; Ye |S c , Q), ∀S
{C1 , S1 , O1, C2 , S2 , O2 }, (2.6)
x RS = I(S; Ye |Q), S = {C1 , S1 , O1, C2 , S2 , O2 }.
Proof. Please refer to Appendix A.1. Remark 2.3. We note that, in Wyner’s encoding scheme [8], each codeword in the codebook is indexed by the message index and an additional, here referred to as randomization, index. Hence, the coding scheme essentially generates a two dimensional codebook, which we refer to as randomized (or, binning) codebook. (Please refer to Fig. 2.2 and Fig. 2.3.) Note that our use of the binning technique here is different than that of the source coding problems (see, e.g., [81] and [82]), as the latter is a compression technique whereas the former is a codebook expansion technique to confuse the eavesdropper. In the rest of the sequel, we will either generate the codewords and distribute them into the bins (where the number of bins is the same as the number of secret messages), or for each secret message we will generate sufficient number of codewords indexed by both the message and randomization indices. These two techniques are equivalent and they produce the same results. The following comments are now in order. 1. The auxiliary random variable Q serves as a time-sharing parameter (see, e.g.,[82, 83]).
20
N
1
1
X(w) w
2N R
Figure 2.2: Random codebook of Shannon. To transmit a message, the codeword indexed by the message is transmitted.
N
1
1
X(w, w x ) w
2N R 1 wx 2N R x Figure 2.3: Randomized codebook of Wyner. For a given message index, a column is randomly chosen, and the corresponding channel input is transmitted. Designing the number of columns properly is the key to prove that the security constraint is met. We refer to this codebook as randomized (two-dimensional) codebook.
2. The auxiliary variable C1 (C2 ) is used to construct the common secure signal of transmitter 1 (2, respectively). This signal has to be decoded at both receivers; and we use the random coding technique of [8] for this codeword. 3. The auxiliary variable S1 is used to construct the self secure signal of transmitter 1. This signal has to be decoded at receiver 1 but not at receiver 2; and we use the random coding technique of [8] for this codeword. Similarly, S2 is used for the self secure signal of user 2.
21
4. The auxiliary variable O1 is used to construct the other signal of transmitter 1. This codeword has to be decoded at receiver 2 but not at receiver 1 (conventional random coding [82] is used to construct this signal). Similarly, O2 is used for x x the other signal of user 2. Note that we use RO1 and RO2 for the associated
rates of these codewords; and, set RO1 = RO2 = 0. 5. Compared to the Han-Kobayashi scheme [73], the common and self random variables are constructed with randomized codebooks. This way, they are used not only for transmitting information, but also for adding randomness. Moreover, we have two additional random variables in this scheme. These extra random variables, namely O1 and O2 , are used to facilitate cooperation among the network users by adding extra randomness to the channel which has to be decoded by the non-intended receiver. We note that, compared to random variables Ck and Sk , the randomization added via Ok is considered as interference at the receiver k. 6. The gain that can be leveraged from cooperative encoding can be attributed to the freedom in the allocation of randomization rates at the two users (e.g., see (2.6)). This allows the users to cooperatively add randomness to impair the eavesdropper with a minimal impact on the achievable rate at the legitimate receivers. Cooperative channel prefixing, on the other hand, can be achieved by the joint optimization of the probabilistic channel prefixes p(x1 |c1 , s1 , o1 ) and p(x2 |c2 , s2 , o2 ). Please refer to Fig. 2.4.
22
Encoder k wk wCk Randomized codebook c (w , wx ) k Ck Ck p(ck |q)
Randomized codebook
q
wSk
p(sk |q)
Random codebook
x sk (wSk , wSk ) Channel prefixing p(xk |ck , sk , ok ) x ok (wOk )
xk
p(ok |q)
Figure 2.4: Proposed encoder structure for the IC-E.
2.1.3
Outer Bounds
Theorem 2.4. For any (R1 , R2 ) ∈ CIC-E , R1 ≤ max I(V1 ; Y1 |V2 , U) − I(V1 ; Ye |U) p∈PO (2.7) (2.8)
R2 ≤ max I(V2 ; Y2 |V1 , U) − I(V2 ; Ye |U), p∈PO where PO is the set of joint distributions that factors as p(u, v1 , v2 , x1 , x2 ) = p(u)p(v1 |u)p(v2 |u)p(x1 |v1 )p(x2 |v2 ). Proof. Please refer to Appendix A.2. Theorem 2.5. For channels satisfying I(V2 ; Y2 |V1 ) ≤ I(V2 ; Y1 |V1 ) (2.9)
for any distribution that factors as p(v1 , v2 , x1 , x2 ) = p(v1 )p(v2 )p(x1 |v1 )p(x2 |v2 ), the following is an upper bound on the sum-rate of the IC-E. R1 + R2 ≤ max I(V1 , V2 ; Y1 |U) − I(V1 , V2 ; Ye |U), p∈PO (2.10)
23
where PO is the set of joint distributions that factors as p(u, v1 , v2 , x1 , x2 ) = p(u)p(v1 |u)p(v2 |u)p(x1 |v1 )p(x2 |v2 ). Proof. Please refer to Appendix A.3. We note that the above sum-rate upper bound also holds for the set of channels satisfying I(V2 ; Y2 ) ≤ I(V2 ; Y1 ) (2.11)
for any distribution that factors as p(v1 , v2 , x1 , x2 ) = p(v1 )p(v2 )p(x1 |v1 )p(x2 |v2 ). Finally, it is evident that one can obtain another upper bound by reversing the indices 1 and 2 in above expressions.
2.1.4
Special Cases
We now focus on few special cases, where we derive sharp results on the secrecy capacity region. In all these scenarios, the achievability is based on the proposed cooperative encoding and channel prefixing scheme. To simplify the presentation, we first define the following set of probability distributions. For any given random variable tuple (T1 , T2 ), P(T1 , T2 ) p(q, t1 , t2 , x1 , x2 ) | p(q, t1 , t2 , x1 , x2 ) = p(q)p(t1 |q)p(t2 |q)p(x1 |t1 )p(x2 |t2 ) .
Corollary 2.6. If the IC-E satisfies I(V2 ; Y2 |V1 , Q) ≤ I(V2 ; Ye |Q) I(V2 ; Ye |V1 , Q) ≤ I(V2 ; Y1 |Q) (2.12)
24
for all input distributions that factors as p(q)p(v1 |q)p(v2 |q)p(x1 |v1 )p(x2 |v2 ), then its secrecy capacity region is given by CIC-E = the closure of RS1 (p) ,
p∈P(S1 ,O2 )
where RS1 (p) is the set of rate-tuples (R1 , R2 ) satisfying
R1 ≤ [I(S1 ; Y1|O2 , Q) − I(S1 ; Ye |Q)]+ R2 = 0, for any p ∈ P(S1 , O2 ). Proof. Please refer to Appendix A.4. Corollary 2.7. If the IC-E satisfies I(V2 ; Ye |Q) ≤ I(V2 ; Y1 |Q) ≤ I(V2 ; Y2 |Q) I(V1 ; Ye |V2 , Q) ≤ I(V1 ; Y1 |V2 , Q) I(V2 ; Y2 |V1 , Q) ≤ I(V2 ; Y1 |V1 , Q) (2.14) (2.13)
for all input distributions that factors as p(q)p(v1 |q)p(v2 |q)p(x1 |v1 )p(x2 |v2 ), then its secrecy sum capacity is given as follows. max R1 + R2 = max I(S1 , C2 ; Y1 |Q) − I(S1 , C2 ; Ye |Q).
(R1 ,R2 )∈C IC-E
p∈P(S1 ,C2 )
Proof. Please refer to Appendix A.5. Corollary 2.8. If the IC-E satisfies I(V2 ; Ye |Q) ≤ I(V2 ; Y1 |V1 , Q) ≤ I(V2 ; Ye |V1 , Q) I(V2 ; Y2|V1 , Q) ≤ I(V2 ; Y1 |V1 , Q) 25 (2.15)
for all input distributions that factors as p(q)p(v1 |q)p(v2 |q)p(x1 |v1 )p(x2 |v2 ), then its secrecy sum capacity is given as follows. max R1 + R2 = max I(S1 , O2 ; Y1|Q) − I(S1 , O2 ; Ye |Q).
(R1 ,R2 )∈C IC-E
p∈P(S1 ,O2 )
We also note that, in this case, O2 will not increase the sum-rate, and hence, we can set |O2 | = 1 Proof. Please refer to Appendix A.6. Another case for which the cooperative encoding and channel prefixing approach can attain the sum-capacity is the following. Corollary 2.9. If the IC-E satisfies I(V2 ; Y1 |Q) ≤ I(V2 ; Ye |V1 , Q) ≤ I(V2 ; Y1 |V1 , Q) I(V2 ; Y2 |V1 , Q) ≤ I(V2 ; Y1 |V1 , Q) for all input distributions that factors as p(q)p(v1 |q)p(v2 |q)p(x1 |v1 )p(x2 |v2 ), then its secrecy sum capacity is given as follows. max R1 + R2 = max I(S1 , O2 ; Y1|Q) − I(S1 , O2 ; Ye |Q). (2.16)
(R1 ,R2 )∈C IC-E
p∈P(S1 ,O2 )
Proof. Please refer to Appendix A.7. Now, we use our results for the two-user interference channel to shed more light on the secrecy capacity region of the discrete memoryless multiple access channel. In this model, two users communicate with a single receiver in the presence of an eavesdropper. At this point, we observe that the multiple access channel with an eavesdropper (MAC-E) defined by p(y1, ye |x1 , x2 ) is equivalent to the IC-E defined by 26
p(y1 , y2 , ye |x1 , x2 ) = p(y1 , ye |x1 , x2 )δ(y2 − y1 ). This allows for specializing the results obtained earlier to the MAC-E. Corollary 2.10. RMAC-E the closure of R(p) ,
p∈P(C1 ,C2 )
where the channel is given by p(y1 , ye |x1 , x2 )δ(y2 − y1 ).
Note that, as there is only one intended receiver in this network model, the usage of codewords corresponding to random variables Sk and Ok for k = 1, 2 (see Theorem 2.2) becomes obsolete. We now characterize the secrecy sum rate of the weak MAC-E. Corollary 2.11 (MAC-E with a weak eavesdropper). If the eavesdropper is weak for the MAC-E, i.e., I(V1 ; Ye |V2 ) ≤ I(V1 ; Y1 |V2) I(V2 ; Ye |V1 ) ≤ I(V2 ; Y1|V1 ), (2.17)
for all input distributions that factor as p(v1 )p(v2 )p(x1 |v1 )p(x2 |v2 ), then the secure sum-rate capacity is given by max R1 + R2 = max {I(C1 , C2 ; Y1 |Q) − I(C1 , C2 ; Ye |Q)}.
(R1 ,R2 )∈C MAC-E
p∈P(C1 ,C2 )
Proof. Please refer to Appendix A.8. Another special case of the IC-E model is the relay-eavesdropper channel with a deaf helper. In this scenario, transmitter 1 has a secret message for receiver 1 and transmitter 2, referred to as relay, is only interested in helping transmitter 1 in 27
increasing its secure transmission rates. (Note that, the relay node here does not have a receiver and hence it is referred to as deaf.) In this model, we use the random variable O2 at transmitter 2 to add randomness to the network. Again, the regions given earlier can be specialized to this scenario. For example, the following region is achievable for this relay-eavesdropper model.
RRE
the closure of the convex hull of
p∈P(S1 ,O2 ,|Q|=1)
R(p)
,
where P(S1 , O2, |Q| = 1) denotes the probability distributions in P(S1 , O2 ) with a deterministic Q. For this relay-eavesdropper scenario, the noise forwarding (NF) scheme proposed in [13] achieves the following rate. R[NF] = where R1 (p) max R1 (p), (2.18)
p∈P(S1 ,O2 ,|Q|=1)
[I(S1 ; Y1 |O2 )+min{I(O2 ; Y1 ), I(O2; Ye |S1 )}−min{I(O2 ; Y1 ), I(O2; Ye )}
−I(S1 ; Ye |O2 )]+ . The following result shows that NF is a special case of the cooperative encoding and channel prefixing scheme and provides a simplification for the achievable rate expression. Corollary 2.12. (R[NF] , 0) ∈ RRE , where R[NF] can be simplified as follows. R[NF] = p∈P(S1 ,O2 ,|Q|=1) s.t. I(O2 ;Ye )≤I(O2 ;Y1 )
max
I(S1 ; Y1|O2 ) − I(S1 , O2 ; Ye ) + min{I(O2; Y1 ), I(O2; Ye |S1 )}
(2.19)
Proof. Please refer to Appendix A.9. Finally, the next result establishes the optimality of the noise forwarding in certain relay-eavesdropper channels.
28
Corollary 2.13. Noise Forwarding scheme is optimal for the relay-eavesdropper channels which satisfy I(V2 ; Y1) ≤ I(V2 ; Ye |V1 ), (2.20)
for all input distributions that factor as p(v1 )p(v2 )p(x1 |v1 )p(x2 |v2 ), and the corresponding secrecy capacity is given by C RE = max I(S1 , O2 ; Y1 ) − I(S1 , O2; Ye ).
p∈P(S1 ,O2 ,|Q|=1) s.t. I(O2 ;Ye )≤I(O2 ;Y1 )
Proof. Please refer to Appendix A.10.
2.2 2.2.1
The Gaussian Channel System Model
In its standard form [84], the two user Gaussian Interference Channel with an Eavesdropper (GIC-E) is given by Y 1 = X1 + Y2 = Ye = h21 X2 + Z1 (2.21)
h12 X1 + X2 + Z2 h1e X1 + h2e X2 + Ze ,
where Zr ∼ N (0, 1) is the additive Gaussian noise impairing receiver r ∈ {1, 2, e}. Here, the channel inputs have the following average power constraints. 1 N
N
t=1
(Xk (t))2 ≤ Pk ; k = 1, 2.
(2.22)
The secrecy capacity region of the GIC-E is denoted as CGIC-E .
29
2.2.2
Inner Bound and Numerical Results
In this section, our goal is to specialize the results obtained in the previous section to the Gaussian scenario and illustrate the gains that can be leveraged from cooperative encoding and channel prefixing, and time sharing. Towards this end, we first introduce the following definitions. Consider a probability mass function on the time sharing parameter denoted by p(q). Let A(p(q)) denote the set of all possible power allocations, i.e., A(p(q)) j j c s o c s o P1 (q), P1 (q), P1 (q), P2 (q), P2 (q), P2 (q), P1 (q), P2 (q) j c s o (Pk (q) + Pk (q) + Pk (q) + Pk (q))p(q) ≤ Pk ; k = 1, 2.
(2.23)
q∈Q
Now, we define a set of joint distributions PG for the Gaussian case as follows. PG j j c s o c s o p | p ∈ P, (P1 (q), P1 (q), P1 (q), P2 (q), P2 (q), P2 (q), P1 (q), P2 (q)) ∈ A(p(q)), c s o C1 (q) ∼ N (0, P1 (q)), S1 (q) ∼ N (0, P1 (q)), O1(q) ∼ N (0, P1 (q)), c s o C2 (q) ∼ N (0, P2 (q)), S2 (q) ∼ N (0, P2 (q)), O2(q) ∼ N (0, P2 (q)), j j J1 (q) ∼ N (0, P1 (q)), J2 (q) ∼ N (0, P2 (q)),
X1 (q) = C1 (q) + S1 (q) + O1 (q) + J1 (q), X2 (q) = C2 (q) + S2 (q) + O2 (q) + J2 (q) , and the Gaussian model given in (2.21) gives the channel p(y1 , y2, ye |x1 , x2 ). Note that, in addition to the previously defined codewords, here, each transmitter has a jamming sequence (denoted by Jk ) that is drawn from a Gaussian distribution j (with power Pk , respectively). Using this set of distributions, we obtain the following
achievable secrecy rate region for the GIC-E. 30
Corollary 2.14. RGIC-E
the closure of p∈PG R(p)
⊆ CGIC-E .
It is interesting to see that our particular choice of the channel prefixing distribution p(xk |ck , sk , ok ) in the above corollary corresponds to a superposition coding approach where Xk = Ck + Sk + Ok + Jk . This observation establishes the fact that noise injection scheme of [56] and jamming scheme of [27] are special cases of the channel prefixing technique of [9]. The following computationally simple subregion will be used to generate some of our numerical results.
GIC-E Corollary 2.15. R2
convex closure of p∈PG2 R(p)
⊆ RGIC-E ⊆ CGIC-E ,
where PG2 s o s o {p | p ∈ PG , |Q| = 1, P1 (q) = P1 (q) = P2 (q) = P2 (q) = 0 for any Q = q}.
Another simplification can be obtained from the following TDMA-like approach. Here we divide the N channel uses into two parts of lengths represented by αN and (1 − α)N, where 0 ≤ α ≤ 1 and αN is assumed to be an integer. During the s first period, transmitter 1 generates randomized codewords using power P1 (1) and j transmitter 2 jams the channel using power P2 (1). For the second period, the roles j s of the users are reversed, where the users use powers P2 (2) and P1 (2). We refer to
this scheme cooperative TDMA (C-TDMA) which achieves the following region. Corollary 2.16. RC-TDMA ⊆ RGIC-E ⊆ CGIC-E , where RC-TDMA the closure of (R1 , R2 ) , α∈[0,1] αP s (1)+(1−α)P j (2)≤P 1 1 j 1 αP (1)+(1−α)P s (2)≤P2 2 2
31
where
+
R1 = and
s P1 (1) α log 1 + j 2 1 + h21 P2 (1)
− log 1 +
s h1e P1 (1) j 1 + h2e P2 (1)
,
s P2 (2) (1 − α) R2 = log 1 + j 2 1 + h12 P1 (2)
s h2e P2 (2) − log 1 + j 1 + h1e P1 (2)
+
.
Proof. This is a subregion of the CGIC-E , where we use a time sharing random variable satisfying p(q = 1) = α and p(q = 2) = 1 − α, and utilize the random variables S1 and S2 . The proof also follows by respective single-user Gaussian wiretap channel result [10] with the modified noise variances due to the jamming signals. In the C-TDMA scheme above, we only add randomness by noise injection at the helper node. We note that, our cooperative encoding and channel prefixing scheme (Corollary 2.14) allows for the implementation of more general cooperation strategies. For example, in a more general TDMA approach, each user can help the other via both randomized encoding and channel prefixing (i.e., the noise forwarding scheme described in Section 2.2.3). In addition, one can develop enhanced transmission strategies with a time-sharing random variable of cardinality greater than 2. We now provide numerical results for the following subregions of the achievable region given in Corollary 2.14. • RGIC-E : For this region, we utilize both cooperative encoding and channel pre2 fixing.
GIC-E • R2 (b or cp): Here we utilize either cooperative encoding (b) or channel
prefixing (cp) scheme at a transmitter, but not both. 32
• RGIC-E (ncp): Here we only utilize cooperative encoding, no channel prefixing 2 (ncp) is implemented. • RC-TDMA : This region is an example of utilizing both time-sharing and cooperative channel prefixing. • RC-TDMA (ncp): This region is a subregion of RC-TDMA , for which we set the jamming powers to zero.
The first scenario depicted in Fig. 2.5 shows the gain offered by the cooperative encoding technique, as compared with the various cooperative TDMA approaches. Also, it is shown that cooperative channel prefixing does not increase the secrecy rate region in this particular scenario. This is due to the fact that the noise injection hurts legitimate receivers more than the eavesdropper in this scenario. In Fig. 2.6, we consider a channel with a rather capable eavesdropper. In this case, it is straightforward to verify that the corresponding single user channels have zero secrecy capacities. 34
Despite this fact, with the appropriate cooperation strategies between the two interfering users, one can achieve non-zero rates for both users (as reported in the figure). In Fig. 2.7, we consider an asymmetric scenario, in which the first user has a weak channel to the eavesdropper, but the second user has a strong channel to the eavesdropper. In this case, the proposed cooperative encoding technique allows the second user to achieve a positive secure transmission rate, which is not possible by exploiting only the channel prefixing and time-sharing techniques. In addition, by prefixing the 35
channel, the second user can help the first one to increase its secure transmission rate. Remarkably, these observations establish that the interference can be beneficial for security applications as it allows for cooperation against the eavesdropper. Finally, we note that for some channel coefficients RC-TDMA outperforms RGIC-E and for some 2 others RGIC-E outperforms RC-TDMA . Therefore, in general, the proposed techniques 2 (cooperative encoding, cooperative channel prefixing, and time-sharing) should be exploited simultaneously as considered in Corollary 2.14.
2.2.3
Special Cases
The Multiple Access Channel First, we define the following set of probability distributions. PG3 s o s o p | p ∈ PG , P1 (q) = P1 (q) = P2 (q) = P2 (q) = 0 for any Q = q (2.24)
Using this notation, we see that the region RGIC-E in Corollary 2.14 reduces to the following achievable secrecy rate region for the special case of Gaussian Multiple Access Channel with an Eavesdropper (GMAC-E) given by the channel p(y1, ye |x1 , x2 ). RGMAC-E the closure of p∈PG3 R(p) ,
where the expressions in the region R(p) are calculated for the channel given by p(y1 , ye |x1 , x2 )δ(y2 − y1 ). The region RGMAC-E generalizes the one obtained in [27] for the two user case 3 . The underlying reason is that, in the achievable scheme of [27], the users are either transmitting their codewords or jamming the channel whereas, in our approach, the
We note that we have used the randomized codebook construction here to achieve the stated region, whereas in [27] the authors claimed that their region is achievable with the superposition coding approach.
3
36
users can transmit their codewords and jam the channel simultaneously. In addition, our cooperative TDMA approach generalizes the one proposed in [27], as we allow the two users to cooperate in the design of randomized codebooks and channel prefixing during the time slots dedicated to either one. The Relay-Eavesdropper Channel In the previous section, we argued that the noise forwarding (NF) scheme of [13] can be obtained as a special case of our generalized cooperation scheme. Here, we demonstrate the positive impact of channel prefixing on increasing the achievable secrecy rate of the Gaussian relay-eavesdropper channel. In particular, the proposed region for the Gaussian IC-E, when specialized to the Gaussian relay-eavesdropper setting, results in RGRE where PG4 c o c s p | p ∈ PG , |Q| = 1, P1 (q) = P1 (q) = P2 (q) = P2 (q) = 0 . (2.25)
closure of the convex hull of p∈PG4 R(p) ,
One the other hand, noise forwarding with no channel prefixing (GNF-ncp) results in the following achievable rate. R[GNF-ncp] = 1 1 log (1 + P1 ) − log (1 + h1e P1 ) 2 2 1 h21 P2 1 + min log 1 + , log (1 + h2e P2 ) 2 1 + P1 2 − min 1 h21 P2 log 1 + 2 1 + P1 , 1 h2e P2 log 1 + 2 1 + h1e P1
+
,(2.26)
where we choose X1 = S1 ∼ N (0, P1 ) and X2 = O2 ∼ N (0, P2) in the expression of R[NF] (see also [13]). 37
Numerically, the positive impact of channel prefixing is illustrated in the following example. First, it is easy to see that the following secrecy rate is achievable with channel prefixing P1 1 R1 = log 1 + 2 1 + h21 P2 1 h1e P1 − log 1 + 2 1 + h2e P2
+
,
(2.27)
j s since (R1 , 0) ∈ RGRE (i.e., we set P1 = P1 and P2 = P2 ). Now, we consider a network
model given by h1e = h2e = 1 and P1 = P2 = 1, resulting in R[GNF-ncp] = 0 and R1 > 0 if h21 < 1. This clearly establishes the positive impact of channel prefixing (in the form of jamming) in relay-eavesdropper channels.
38
CHAPTER 3
Secure Degrees of Freedom in K-User Interference Channels
In this chapter, we focus on the K-user network, consisting of K source-destination pairs, under security constraints. We consider two distinct network models, namely 1. The K-user interference channel with confidential messages, and 2. The K-user interference channel with an external eavesdropper. In the first scenario, one needs to ensure the confidentiality of each message from all non-intended receivers in the network. Whereas, in the second scenario, the messages have to be kept secret only from the external eavesdropper. We note that, as all users are assumed to belong to the same network, the availability of channel state information (CSI) is a more appropriate assumption for the former scenario compared to the latter one, where the CSI of the external eavesdropper may not be available at the network users. In the sequel, we will take into account this factor and propose coding schemes, for the second scenario, without the assumption of instantaneous CSI of the channel seen by the adversary. In this K-user network, our focus will be on asymptotically high signal strengths with respect to the noise levels impairing the receivers. This approach allows us to characterize the achievable performance, secrecy rate per user, within a factor of 39
o(log(SNR)), where SNR stands for the signal to noise ratio. In other words, we explore the pre-log gain, also known as the degrees of freedom (DoF), per user (definition of this term will be made precise in the next section) in this interfering network under the secrecy constraints given above. This approach allows us to identify how these interfering users can share the signal dimensions under the secrecy constraints. Note that, without the secrecy constraints, it is well known that the point-to-point channel has a DoF of 1, i.e., the capacity, C, of the single user Gaussian channel scales as C(SNR) = log(SNR) + o(log(SNR)) as SNR gets large. (See, e.g., [72], [71].) However, under the secrecy constraint (against an eavesdropper), the situation drastically changes. Denoting the capacities of the main and eavesdropper channels by Cm and Ce , respectively, it is shown in [10] that the secrecy capacity of the single user Gaussian channel is Cs = [Cm − Ce ]+ . Thus, in the high SNR regime, secrecy capacity scales as Cs (SNR) = o(log(SNR)). These results show that the secrecy capacity saturates in the high SNR regime implying a vanishing value for the secure DoF . In this chapter, we show that the interfering users can cooperate to achieve secrecy and, in particular, to overcome this phenomenon. The frequency/time selective K-user Gaussian interference channel, without the secrecy constraints, is studied in [85] and it is shown that a
1 2
DoF per orthogonal
dimension is achievable for each source-destination pair in this network. The enabling scheme was based on the interference alignment technique (see also [86]), by which the interfering signals are aligned to occupy a subspace orthogonal to the one spanned by the intended signal at each receiver. However, the impact of secrecy constraints on the degrees of freedom in this model has not been fully characterized. In fact, to the best of our knowledge, the only relevant prior works are the studies on the 40
two-user discrete memoryless interference channels. (The external eavesdropper case is studied in the previous chapter and the confidential message scenario is studied in [39, 43, 87].) The frequency selective interference channel adopted in this chapter is fundamentally different from these memoryless models. The proposed scheme for this network employs an interference alignment scheme along with secrecy pre-coding at each transmitter. Intuitively, the interference alignment scheme has two effects on each receiver i: 1. It aligns the signals from transmitters k = i to a small dimensionality subspace, and 2. It enforces the signal from transmitter i to span the orthogonal subspace. Hence, while the signal from its own transmitter is received cleanly, the signals from other transmitters are mixed together. Our secrecy pre-coding takes advantage of the phenomenon to ensure that the resulting multiple access channel (from the K − 1 interfering users) does not reveal any useful information about each non-intended message. This way, we show that
1 4
secure DoF per orthogonal dimension is achiev-
able for each user in the three-user Gaussian interference channel with confidential messages. We then generalize our results to the K-user Gaussian interference channel showing that each user can achieve
K−2 2K−2
secure DoF. In the second scenario, we
study the external eavesdropper model where the fundamental challenge is the lack of channel state information (CSI) about the links connected to it. Despite this fact, it is shown that 1/2 − 1/K DoF per user is achievable in the ergodic setting. This result provides further evidence on the diminishing gain resulting from knowing the
41
instantaneous CSI of the eavesdropper a-priori. Interestingly, by comparing our results with those obtained for the point-to-point case [65, 66], one can see the positive impact of interference on the secrecy capacity region of wireless network. The underlying idea is that the coordination between several source-destination pairs allows for hiding the secret messages in the background interference. The remainder of this chapter is organized as follows. In Section II, the system model of the two network models are introduced. Section III is devoted to the interference channel with confidential messages. The analysis for the external eavesdropper scenario is detailed in Section IV. The lemmas used in the text are collected in the Appendix B.
3.1 3.1.1
System Model The Confidential Messages Scenario
We consider a frequency selective wireless network comprised of K transmitterreceiver pairs and F frequency bands. The user set is denoted by K {1, · · · , K}.
Also, for this chapter, matrices are represented with bold capital letters (X) and ¯ vectors are denoted as bold capital letters with bars or tildes (for example, X and ˜ X). We denote the transmitted symbol of user k at frequency slot f during time t as Xk (f, t). Then, the output of the ith receiver at time t ∈ {1, · · · , N} and frequency slot f ∈ {1, · · · , F } is given by
K
Yi (f, t) = k=1 hik (f )Xk (f, t) + Zi (f, t),
(3.1)
42
W1
Encoder 1
X1
Y1
Decoder 1
ˆ W1 ∆S,1 , ∀S ⊆ K − 1
Channel
WK
Encoder K
XK
YK
Decoder K
ˆ WK ∆S,K , ∀S ⊆ K − K
Figure 3.1: K-user interference channel with confidential messages.
where Zi (f, t) ∼ CN (0, 1) is the additive white Gaussian noise at receiver i. We assume that the channel coefficients are independently and randomly generated according to a continuous distribution and are fixed during the communication period 4 . We also assume that the channel coefficients are known at every node in the network. The network model is provided in Fig. 3.1. To ease the presentation, we now represent the received symbols using only the time index by representing the different frequency dimensions with appropriate matrices and vectors (called as extended channel notation in [85]). Accordingly, the ith received vector during time slot t can be written as
K
¯ Yi(t) = k=1 ¯ ¯ Hi,k Xk (t) + Zi (t).
(3.2)
Here, Hi,k is the F × F diagonal matrix of channel coefficients from transmitter k ¯ ¯ to receiver i, whereas Yi(t) = [Yi (1, t), · · · , Yi (F, t)]T , Zi (t) = [Zi (1, t), · · · , Zi (F, t)]T , ¯ and Xk (t) = [Xk (1, t), · · · , Xk (F, t)]T are F × 1 column vectors.
We note that the continuous distribution assumption on the channel coefficients guarantee the existence of the interference alignment matrix. See also [85].
4
43
We assume that each source k ∈ K has a message Wk which is transmitted to its respective receiver and kept secret from the remaining K − 1 receivers. We assume that transmitters have the same average long-term power constraint denoted by P . Note that, for i.i.d. CN (0, P ) input distribution, SNR
P 1
is the signal-to-noise ratio
per complex dimension. Therefore, our (N, F, M1 , · · · , MK ) secret codebook has the following components: 1. The secret message set Wk = {1, · · · , Mk }. 2. Encoding functions fk (.) which map the secret messages to the transmitted ¯ ¯ symbols, i.e., fk : wk → (Xk (1), · · · , Xk (N)) for each wk ∈ Wk . At encoder k, each codeword is designed according to the transmitter’s average long-term power constraint P , i.e., 1 nF
F N
f =1 t=1
(Xk (t, f ))2 ≤ P.
3. Decoding functions φk (.) at receivers k ∈ K which map the received symbols to ˆ ¯ ¯ estimates of the messages: φk (Yk ) = Wk where Yk = {Yk (1), · · · , Yk (N)}. In this network, we have the following notions of reliability and secrecy. The reliability of the transmission of user k is measured by the probability of error Pe,k = 1
K
Mi i=1 (w1 ,··· ,wK ) ∈ W1 ×···×WK
Pr {φk (Yk ) = wk |(w1 , · · · , wK ) is sent} .
The secrecy level is measured by the normalized equivocation defined as follows [8, 88]: For receiver i, the equivocation for each subset of messages WS , S ⊆ K − i, is ∆S,i H (WS |Yi ) . H (WS ) 44 (3.3)
Note that this is a multi-user extension of the equivocation considered in [8] and [88]. We say that the rate-equivocation tuple (R1 , · · · , RK , d) is achievable for the Gaussian interference channel with confidential messages, if, for any given ǫ > 0, there exists an (N, F, M1 , · · · , MK ) secret codebook satisfying the followings 1 log2 Mk = Rk , ∀k ∈ K, NF max{Pe,1 , · · · , Pe,K } ≤ ǫ, ∆S,i ≥ d − ǫ, ∀i ∈ K, ∀S ⊆ K − i. Note that, we use a symmetric secrecy notion for each user in the network. We also say that the symmetric degrees of freedom (per orthogonal frequency-time slot) of η is achievable with perfect secrecy, if the rate-equivocation tuple (R1 = R, · · · , RK = R, d = 1) is achievable and η= R . SNR→∞ log(SNR) lim (3.5) (3.4)
3.1.2
The External Eavesdropper Scenario
In this model, we assume the existence of an external eavesdropper who observes the signals of the K sources. The network model is depicted in Fig. 3.2. We consider an ergodic setting where the channel gains are fixed during a block of N1 symbol times and then randomly change to another value for the next block. Hence, transmission time of N time slots is divided into B fading blocks with N = N1 B. We denote the received signals at receiver i ∈ {1, · · · , K, e} using the extended channel notation as follows
K
Figure 3.2: K-user interference channel with an external eavesdropper.
where b ∈ {1, · · · , B} denotes the fading block b, j ∈ {1, · · · , N1 } denotes the j th time instant of the corresponding fading block, Hi,k (b) is the F × F diagonal matrix of channel coefficients between transmitter k and receiver i during fading block b, ¯ and Xk (j + (b − 1)N1 ) is the transmitted vector of user k at j th symbol of the bth fading block. We also represent the channel coefficients as H K, b ∈ {1, · · · , B}} and He {Hi,k (b) : i, k ∈
{He,k (b) : k ∈ K, b ∈ {1, · · · , B}}. We assume
that H is known at all the nodes in the network, whereas He is known only at the eavesdropper. (Only the statistical knowledge about the eavesdropper CSI is available to the network users.) The channel coefficients are i.i.d. samples of a zero-mean unit variance complex Gaussian distribution. The components of the secrecy codebook remain as detailed above. However, for this network, each transmitter must secure its own message only from the external eavesdropper. Accordingly, we modify the secrecy requirement by considering the 46
normalized equivocation seen by the eavesdropper. We denote the observation at ¯ ¯ ¯ the eavesdropper as Ye = {Ye (1), · · · , Ye (N)}, in which Ye (t) is defined similarly ¯ as Yi (t) for t = 1, · · · , N. Therefore, the normalized equivocation for a subset of messages S ⊆ K is given by ∆S H (WS |Ye , H, He) . H (WS ) (3.7)
We say that the rate-equivocation tuple (R1 , · · · , RK , d) is achievable for the Gaussian interference channel with an external eavesdropper, if, for any given ǫ > 0, there exits an (N, F, M1 , · · · , MK ) secret codebook satisfying the followings 1 log2 Mk = Rk , ∀k ∈ K, NF max{Pe,1, · · · , Pe,K } ≤ ǫ, ∆S ≥ d − ǫ, ∀S ⊆ K. Finally, the symmetric DoF with perfect secrecy is defined along the same lines as in the previous section. (3.8)
3.2
The K-User Gaussian Interference Channel with Confidential Messages
We first start with an intuitive argument for the three-user Gaussian interference channel to illustrate the main idea. Let F = 2m + 1 for some m ∈ N. This is the (2m + 1) symbol extension of the three-user channel considered in [85]. We now ¯ employ interference alignment precoding using the matrices Vk of [85], so that the ¯ ¯ ˜ ˜ transmitted signals are of the form Xk (t) = Vk Xk (t), where Xk (t) represents the vector of mk streams transmitted from user k. (Please refer to Fig. 3.3.) According ¯ to the interference alignment principle, the beamforming matrices Vk are constructed to satisfy the following two properties: 47
Encoder k
Wk
Secrecy Precoding
˜ Xk (t)
Interference Alignmenet Coding
¯ Xk (t)
Decoder k
ˆ Wk
¯ Yk (t)
Decoding
Eavesdropping
∆S,k , ∀S ⊆ K − k
Figure 3.3: Proposed encoder and decoder architecture for user k in the K-user interference channel with confidential messages.
1. The non-intended signals seen by each receiver are aligned within some low dimensionality subspace. More precisely, the column space of the matrices ¯ Hi,k Vk for k ∈ K − i lie in a subspace of dimension F − mi at receiver i. ¯ 2. The intended streams span the orthogonal subspace, i.e., the columns of Hi,iVi ¯ are independent and are orthogonal to that of Hi,k Vk for each user k ∈ K − i. Notice that, by employing the interference alignment technique, the F dimensional received signal space at each receiver is used to create mi interference free dimensions, spanned by the desired streams. Now, let us consider receiver 1 as the eavesdropper for the messages of users 2 and 3. This particular eavesdropper now sees the m 48
˜ ˜ streams X2 (t) and m streams X3 (t) mixed together in a multiple access channel with only m dimensions. Here, taking advantage of this key observation with appropriate ˜ ˜ secrecy precoding for X2 (t) and X3 (t) allows for completely securing m/2 streams in each transmitted vector. It is easy to see that a similar argument follows for securing each vector against the second potential eavesdropper. In the limit of a large F = 2m + 1, the m/2 secure streams results in 1/4 secure DoF. This intuitive discussion is formalized for the general case of a K-user Gaussian interference channel in the below result. Theorem 3.1. For the K-user Gaussian interference channel with confidential messages, a secure DoF of η = for each user. Proof. We shall show that almost all codebooks in an appropriately constructed ensemble satisfy the achievability conditions for symmetric secure DoF of η =
K−2 2K−2 K−2 2K−2
per frequency-time slot is almost surely achievable
with
probability that approaches to 1, for all channel coefficients, as N, m, SNR → ∞. Fix an m ∈ N. Let m1 = (m + 1)M , mk = mM ∀k = 1, M = (K − 1)(K − 2) − 1, and F = (m + 1)M + mM frequency slots. We now generate, for each user k, 2
N mk
F mk
(Rk +Rx ) k
codewords each of length Nmk with entries that are independent
and identically distributed (i.i.d.) ∼ CN 0, Pc−ǫ . We choose ck to satisfy the power k constraint for each user: ck =
¯ ¯H tr(Vk Vk ) . F
These codewords are then randomly partix
x tioned into Mk = 2N F Rk message bins, each consisting of Mk = 2N F Rk codewords. x ˆ Hence, an entry of the k th user codebook will be represented by Xk (wk , wk ) where x x the bin index wk ∈ Wk is the secrecy message and the index wk ∈ {1, · · · , Mk } is
the randomization message. It is easy to see that the secure transmission rate per orthogonal time and frequency slot is Rk . 49
1 1 2 x ˆ Xk (wk , wk )
x wk
2nF Rk
x
wk
2nF Rk
Figure 3.4: Proposed codebook structure for user k. The secret message of user k results in the bin index wk and the randomization index for the corresponding x user is wk . Considering these two indices, each entry of the codebook is denoted as x ˆ Xk (wk , wk ).
To send a message wk , the k th transmitter looks into the bin wk ∈ Wk and x randomly selects a codeword in this bin, denoted by the index wk , according to x ˆ uniform distribution. It thus obtains Xk (wk , wk ) of length Nmk . (See Fig. 3.4.) We x ˆ ˜ ˜ further partition the elements of this vector as Xk (wk , wk ) = [Xk (1), · · · , Xk (N)],
where each element is an mk × 1 vector. Then, for each symbol time t ∈ {1, · · · , N}, ˜ ¯ the transmitter employs the interference alignment scheme, and maps Xk (t) to Xk (t) ¯ ¯ ˜ ¯ via Xk (t) = Vk Xk (t), where we choose the interference alignment matrices Vk as in [85].
50
We choose the secrecy and randomization rates as follows 5 . Rk = x Rk
1 1 ˜ ¯ ˜ ¯ min I(Xi ; Yi) − max I(XK−i; Yi ) F i∈K (K − 1)F i∈K 1 1 ˜ ¯ ˜ = min I(XS ; Yi |XK−S−i) F i∈K,S⊆K−i |S|
and (3.9)
x The above rates are inside the decodability region for each user, i.e., Rk + Rk ≤ 1 ˜ ¯ I(Xk ; Yk ), F
∀k ∈ K, implying that each user can reliably decode its own streams
as the block length N → ∞. (This argument is similar to the Channel Coding Theorem, see, e.g., [82, Theorem 8.7.1].) Hence, using the union bound argument, we can show that for a given ǫ there exists N0 (ǫ) such that for any N > N0 (ǫ) max{Pe,1, · · · , Pe,K } ≤ ǫ for almost all codebooks in the ensemble. Our second step is to show that ∆S,i can be made arbitrarily close to 1 for any i ∈ K and S ⊆ K − i for almost all codebooks in the ensemble. Towards this end, it is sufficient to focus on the equivocation at an arbitrary receiver i ∈ K. Furthermore, it is sufficient to establish perfect secrecy for the full message set since Lemma B.1 shows that perfect secrecy of the full message set implies secrecy for all subsets. (Here, the full message set at the receiver i refers to WK−i .). Denoting the observation of the eavesdropper as Yi, we write H(WK−i|Yi ) = H(WK−i, Yi ) − H(Yi) x x = H(WK−i, WK−i , Yi ) − H(WK−i|WK−i , Yi ) − H(Yi ) x x = H(WK−i) + H(WK−i|WK−i ) + H(Yi |WK−i, WK−i ) x − H(WK−i |WK−i , Yi ) − H(Yi) x x x = H(WK−i) + H(WK−i) − I(WK−i , WK−i ; Yi) − H(WK−i |WK−i , Yi),
(3.10)
Since the channel coefficients are fixed and known everywhere, we omit the conditioning on them here.
5
51
x x where the last equality follows from the fact that H(WK−i|WK−i ) = H(WK−i ) as
the randomization (i.e., codeword) indices are independent of the message (i.e., bin) indices. We now bound each term of (3.10). First x ˜ ˜ I(WK−i , WK−i ; Yi) ≤ I(XK−i(1), · · · , XK−i (N); Yi )
(3.11)
due to the Markov chain relationship x ˜ ˜ {WK−i , WK−i } → {XK−i (1), · · · , XK−i(N)} → Yi .
(3.12)
Combining this with the fact that ˜ ˜ ˜ ¯ I(XK−i (1), · · · , XK−i (N); Yi ) ≤ N max I(XK−i ; Yi),
˜ p(XK−i )
we obtain x ˜ ¯ I(WK−i , WK−i ; Yi) ≤ N max I(XK−i ; Yi). ˜ p(XK−i )
(3.13)
Second x H(WK−i ) = log x Mk k=i
= NF k∈K−i x Rk .
(3.14)
To upper bound the last term, we use the following argument. Assume that wK−i ∈ WK−i is transmitted. Given these bin indices, the remaining randomness x in WK−i at the eavesdropper can be resolved for almost all codebooks as the above x choice of Rk satisfies the multiple access channel achievability conditions k∈S 1 ˜ ¯ ˜ I(XS ; Yi|XK−S−i), F x Rk ≤
∀S ⊆ K − i [82, Chapter 14]. This argument follows due
to the randomized (two-dimensional) codebook construction (see, e.g., [8]). Then, x by Fano’s inequality, we have H(WK−i|WK−i = wK−i , Yi ) ≤ Nδ(N, wK−i ), where
δ(N, wK−i ) → 0 as N → ∞. Then, defining δ(N) x H(WK−i|WK−i , Yi ) = wK−i ∈WK−i
wK−i ∈WK−i
max
δ(N, wK−i ), we have
x H(WK−i |WK−i = wK−i , Yi) p(WK−i = wK−i )
≤ Nδ(N),
(3.15) 52
where δ(N) → 0 as n → ∞. Using equations (3.13), (3.14), and (3.15) in (3.10) and dividing both sides of by H(WK−i), we obtain ˆ ∆K−i,i ≥ 1 − δ, and ˆ δ ˜ ¯ δ(N) + max I(XK−i ; Yi) − F
˜ p(XK−i ) x Rk k∈K−i
˜ ¯ ˜ ¯ (K − 1) min I(Xi ; Yi) − max I(XK−i; Yi ) i∈K k∈K−i
,
where we used the fact that H(WK−i ) = NF by (3.9).
Rk and the rate assignment given
It is already observed that δ(N) → 0 as N → ∞ for almost all codebooks in the ensemble. The orthogonality of the intended message and interference at each respective receiver along with the full rank property of the gain matrices (see Lemma B.2) imply the followings. ˜ ¯ max I(XK−i ; Yi) log(SNR) lim
SNR→∞
lim
˜ p(XK−i )
= F − mi , ∀i ∈ K,
(3.18) (3.19)
˜ ¯ ˜ I(XS ; Yi|XK−S−i) = r, SNR→∞ log(SNR) where r = mM or r = (m + 1)M depending on i, ˜ ¯ I(Xi ; Yi ) = mi , ∀i ∈ K, SNR→∞ log(SNR) lim and ˜ ¯ I(XK−i; Yi ) = F − mi , ∀i ∈ K. SNR→∞ log(SNR) lim 53
(3.20)
(3.21)
Using the observations (3.18), (3.19), (3.20), and (3.21) in (3.17) we see that lim ˆ δ=0 (3.22)
N,m,SNR→∞
for almost all codebooks in the ensemble. Hence, for any given ǫ > 0, we can make ∆K−i,i ≥ 1 − ǫ by letting N, m, SNR grow. Finally, due to (3.9), (3.20), and (3.21), we obtain η = lim Rk (K − 1)mM − (m + 1)M K−2 = lim = . M + (m + 1)M ) m→∞ SNR→∞ log(SNR) m→∞ (K − 1) (m 2K − 2 lim (3.23)
which proves our result.
3.3
The K-User Gaussian Interference Channel with an External Eavesdropper
We focus on the external eavesdropper model in this section. First, we note that if the CSI of the external eavesdropper is available a-priori at the network users, then our results given in the previous section extend naturally. Intuitively, one can imagine the existence of a virtual transmitter associated with the external eavesdropper transforming our K-user network into another one with K + 1-users. This way, one can achieve a secure DoF of η =
(K+1)−2 2(K+1)−2
=
K−1 2K
per frequency-time slot for each user
using the scheme of the previous section. For example, for a two-user network with an external eavesdropper, it is possible to achieve
1 4
secure DoFs if the eavesdropper
CSI is available at the transmitters. More formally, we have the following result. Corollary 3.2. For the K-user Gaussian interference channel with an external eavesdropper, a secure DoF of η =
K−1 2K
per frequency-time slot is almost surely achievable
for each user (assuming the availability of the eavesdropper CSI).
54
More interestingly, it is still possible to achieve positive secure DoF per user in the absence of the eavesdropper CSI by exploiting the channel ergodicity. In the ergodic model, the channel gains are assumed to be fixed during a block of N1 symbol times and then randomly change to another value in the next block for a total of B blocks, where N1 → ∞ and B → ∞. For illustration purposes, let us first consider the K = 3 case. In such a scenario, due to the interference alignment scheme, the users of the network have
3m+1 2m+1
total
DoF. However, the multiple access channel (MAC) seen by the eavesdropper can only have one DoF from its observations. Thus, via an appropriate choice of secrecy precoding, the additional m 2m+1
DoF can be evenly distributed among the network
1 6
users on the average, allowing for a
secure DoF per user without any requirement
on the eavesdropper CSI. We formalize this discussion in the following. Theorem 3.3. For the K-user Gaussian interference channel with an external eavesdropper, a secure DoF of η =
1 2
−
1 K
per frequency-time slot is achievable for each
user in the ergodic setting (in the absence of the eavesdropper CSI). Proof. Let m ∈ N and F = (m + 1)M + mM , where M = (K − 1)(K − 2) − 1. We set m1 = (m + 1)M and mk = mM for k = 1. We generate all the permutations of length K and denote this set by Π, where |Π| = K!. Then, for each fading block b ∈ {1, · · · , B}, we randomly pick, according to uniform distribution, a permutation from Π and denote it by πb . In order to ensure statistical symmetry, the interference alignment matrices in each fading block will be obtained according to a different user ordering induced by πb . More specifically, let k(b) = πb (k) and Hi(b),k(b) = Hi,k (b). Using the newly ordered channel matrices Hi(b),k(b) , the interference alignment matrix ¯ for the user k(b), i.e., Vk(b) , is generated. 55
(b) (b)
For each secrecy codebook in the ensemble, we generate 2N F (Rk +Rk ) sequences
B
x
each of length N1 b=1 −ǫ mk(b) , where entries are chosen i.i.d.∼ CN 0, P c
for some
ǫ > 0 and c that satisfies the long term average power constraint (the existence of ǫ and c follows from the argument of Theorem 3.1). We independently assign each x codeword to one of Mk = 2N F Rk bins each having Mk = 2N F Rk codewords. Given wk , x transmitter k chooses the corresponding bin and independently (according to uniform x x ˆ distribution) chooses a codeword in that bin denoted by Xk (wk , wk ), where wk is the
randomization index. This codeword is then divided into B blocks, each with a length N1 mk(b) symbols. Each block is then arranged in the following mk(b) × N1 matrix ˜ ˜ ˜ [Xk (1 + (b − 1)N1 ), · · · , Xk (N1 + (b − 1)N1 )], where Xk (j + (b − 1)N1 ), for 1 ≤ j ≤ N1 , ˜ is an mk(b) × 1 vector. At time slot t = j + (b − 1)N1 , the k th transmitter maps Xk (t) ¯ ¯ ¯ ˜ to Xk (t) via Xk (t) = Vk(b) Xk (t). Finally, we would like to emphasize the fact that in the sequel expectations will be taken with respect to the random distribution of the channel matrices and the uniform distribution underlying the permutation operators used in different fading blocks. As shown below, this will allow us to average out the fluctuations of the eavesdropper CSI. ¯ Our first key observation is that the equivalent channel matrices Hi,k (b)Vk(b) con˜ ¯ necting Xk (t) and Yi (t) are identically distributed ∀i, k ∈ K and b ∈ {1, · · · , B}. ˜ ¯ This property will allow us to drop the subscript i and write E[I(Xi ; Yi |H)] = ˜ ¯ E[I(X; Y|H)], ∀i ∈ K in the following. To satisfy the achievability conditions and x the secrecy requirements of the network, we choose Rk and Rk as follows
Rk = x Rk
1 ˜ ¯ ¯ ¯ KE[I(X; Y|H)] − max E[I(XK ; Ye |H, He )] ¯ KF p(XK ) 1 ˜ ¯ = E[I(XK ; Ye |H, He)], KF 56
and (3.24)
where the maximization in the first equation is among all possible input distributions. With this choice of rates, we have the following x Rk + Rk =
1 1 ˜ ¯ ¯ ¯ E[I(X; Y|H)] − max E[I(XK ; Ye |H, He )] ¯ F KF p(XK ) 1 ˜ ¯ + E[I(XK ; Ye |H, He)] KF 1 ˜ ¯ ≤ E[I(X; Y|H)], F
(3.25)
where the inequality is due to the maximization among all possible input distributions x in the second term of the equation. Hence, we have Rk + Rk ≤ 1 ˜ ¯ E[I(X; Y|H)], F
from
which we conclude that each user in the interference network can decode its own secrecy and randomization indices as N1 → ∞ and as B → ∞ using almost all codebooks in the ensemble. (This argument is the fading version of the channel coding theorem.) The next step is to study the equivocation at the eavesdropper. We write
1 1 H(WK |Ye , H, He ) = H(WK , Ye , H, He) − H(Ye , H, He) N N 1 x x = H(WK , WK , Ye , H, He) − H(WK |WK , Ye , H, He) N − H(Ye , H, He ) = 1 x x H(WK ) + H(WK |WK ) + H(Ye , H, He |WK , WK ) N x − H(WK |WK , Ye , H, He ) − H(Ye , H, He )
=
1 x x H(WK ) + H(WK ) − I(WK , WK ; Ye , H, He ) N x − H(WK |WK , Ye , H, He ) ,
(3.26)
57
x x where the last equality follows from the fact that H(WK |WK ) = H(WK ) as the code-
word indices are independent of the bin indices. Here,
K x H(WK ) = log x Mk k=1 K
= k=1 x ˜ ¯ NF Rk = NE[I(XK ; Ye |H, He)]
(3.27)
and 1 x I(WK , WK ; Ye , H, He ) ≤ N →∞ N lim 1 ˜ ˜ I(XK (1), · · · , XK (N); Ye , H, He ) N →∞ N 1 ˜ ˜ = lim I(XK (1), · · · , XK (N); H, He ) N →∞ N ˜ ˜ +I(XK (1), · · · , XK (N); Ye |H, He ) lim = 1 ˜ ˜ I(XK (1), · · · , XK (N); Ye |H, He ) N →∞ N ˜ ¯ = E[I(XK ; Ye |H, He)], (3.28) lim
where the first inequality is due to the Markov chain relationship x ˜ ˜ {WK , WK } → {XK (1), · · · , XK (N)} → {Ye , H, He },
and the last one is due to ergodicity. For the last term of (3.26), we observe that the channel seen by the eavesdropper reduces to a fading MAC channel for the randomization messages, once the bin indices are given, due to the randomized (twodimensional) code construction. For this fading MAC, each user is able to set its randomization message rate as a fraction
1 K
of the total DoF seen by the eavesdrop-
per as chosen in (3.24), and assure the decodability of the randomization messages at the eavesdropper given the secrecy message indices (the technical details are reported in Lemma B.3, Lemma B.4, and Lemma B.5). Then, by Fano’s inequality, we have x H(WK |WK , Ye , H, He) = 0, N1 ,B→∞ N1 B
lim
58
for almost all codebooks in the ensemble. Therefore, by dividing both sides of (3.26) by
1 H(WK ), N
we can ensure ∆K = H(WK |Ye , H, He) ≥ 1 − ǫ, H(WK ) (3.29)
for any ǫ > 0 as N1 , B → ∞, which is sufficient for our purposes (please refer to Lemma B.1). Finally, considering (3.24), we have ˜ ¯ E[I(X; Y|H)] = SNR→∞ log(SNR) lim and hence Rk 1 1 K−1 = K m1 + m2 SNR→∞ log(SNR) KF K K (K − 2)mM = KF lim implying that η = mM F
M
1 K −1 m1 + m2 , K K
−F (3.30)
− 2m DoF is achievable for each user for any m. Consequently, KF
1 2
we conclude that lim η = m→∞ −
1 K
symmetric DoF is achievable with perfect secrecy
in the ergodic setting.
Note that, the DoF achievable in the absence of the eavesdropper CSI (i.e., η =
1 2
−
1 , K
Theorem 3.3) is lower than that of the full CSI case (i.e., η =
1 2
−
1 , 2K
Theorem 3.2). In addition, it is important to observe that the achievability of a positive DoF for the no eavesdropper CSI scenario hinges largely on the ergodicity assumption, whereas when the eavesdropper CSI is assumed to be available our results hold almost surely for all channel realizations. This is the second price entailed by the lack of eavesdropper CSI. Finally, the positive impact of interference on the secrecy capacity region is best illustrated by comparing our results to the point-to-point 59
scenario. In [66], a point-to-point channel with an external eavesdropper was shown to have zero DoF. On the other hand, our results show that as more source-destination pairs are added to the network, not only each pair is able to achieve non-zero DoF for K ≥ 2, but also the achievable DoF increases with K. This seemingly surprising result is due to the interference alignment technique which not only allows for a clean separation between the intended message and interference at each receiver, but also packs the interfering signals into a low dimensionality subspace. This helps to impair the ability of each eavesdropper to distinguish any of the secure messages efficiently.
60
CHAPTER 4
Secrecy Capacity Scaling in Wireless Networks
In this chapter, we focus on large networks and characterize the asymptotic achievable secrecy rate as the number of nodes, n, gets large. Without the security constraints, Gupta and Kumar have shown in [89] that the randomly located nodes can achieve at most a rate that scales like
1 √ , n
as the number of nodes n → ∞, under an
interference-limited channel model in which the interference is considered as noise at the receivers. Gupta and Kumar also proposed a multi-hop based achievable scheme achieving a rate scaling of
√ 1 n log n
per user. This gap, between the upper limits and
the achievable performance, was closed (in terms of scaling) by Franceschetti et al. in [90], where the authors proposed a multi-hop forwarding protocol based on highways achieving a rate scaling of
1 √ n
per source-destination pair in random networks.
Franceschetti et al. constructed a set of connected nodes, highways, that span the network area both horizontally and vertically (a grid like structure). Then, it is shown that each source-destination pair can access to these highways in a time-division manner to transmit the messages. Specifically, first source transmits to a closes horizontal highway. Then, the message is carried until the appropriate vertical highway, which carries the message until the exit node (closest vertical highway member to the destination). Finally, the message is delivered to the destination node from the exit node. 61
The existence of sufficient number of highways and the scaling of the distance between the source-destination nodes and the highway members are established by borrowing tools from percolation theory.
6
Contrary to this multi-hop approach, a single-hop
scheme called as ergodic interference alignment [96] (see also [85], [86]) is recently employed in [97] and, with arbitrary node placement and arbitrary traffic pattern, the unicast and multicast capacity regions of dense networks are characterized (up to a factor of log n) under the Gaussian fading channel model. These line of works assumed an interference-limited channel model, where the interference is considered as noise. Contrary to this model, [98] considered Gaussian fading channel model and proposed hierarchical cooperation schemes that can increase the per-node rate. This approach is further improved in the follow-up works (see, e.g., [99], [100], and references therein). The scaling laws for the secrecy rate under the assumption of pre-distributed private keys was studied in [101]. However, it is important to note that, the key agreement step of the cryptographic protocols is arguably the most challenging part and this step becomes even more daunting as the network size grows. Our approach avoids the aforementioned limitations by adopting an information theoretic framework for secrecy in wireless networks. In particular, we assume the presence of eavesdropper(s) with infinite computational power and characterize the scaling laws of the network secrecy capacity while relaxing the idealistic assumption of pre-distributed keys. The
Percolation theory was founded by Broadbent and Hammersley [91] to model the fluid flow in a medium with randomly blocked channels. Roughly speaking, the basic bond (site) percolation problem is the analysis of the component structure of random graphs (e.g., a lattice grid), where each edge (respectively, vertex) is open (i.e., selected to the component) independently with the same probability p. After percolation problems are introduced to mathematicians [92], there have been many problem formulations with elegant techniques and results [93, 94]. The theory is also very relevant to many engineering applications. (See, e.g., [95].)
6
62
secrecy in stochastic networks is studied in [102], where it is shown that even a small density of eavesdroppers has a drastic impact on the connectivity of the secrecy graph. Connectivity in stochastic networks with secrecy constraints is also studied in [103, 104], where the node degree distribution is analyzed. However, according to the best of our knowledge, information theoretical analysis of secrecy capacity scaling in large wireless networks has not been studied in the literature before. We consider two different network models: 1. The static path loss model: The random network is over a square region; and, the legitimate and eavesdropper nodes are distributed according to Poisson point processes with intensities λ and λe , respectively. (For extended networks, the area of the region is n and λ = 1; and, for dense networks, area of the region is 1 and λ = n.) The path loss is modeled with a power loss exponent of α > 2. This model suits for the scenarios where the channel gains are mostly determined by path losses. 2. The ergodic fading model: There are n source-destination pairs and ne eavesdroppers, where the gain of each link is assumed to follow some fading process. (The assumptions on the fading processes will be clear in the next section. Here, we note that our model includes a large set of fading distributions.) Arguably, this model suits for (dense) networks in which the inter node distances have a negligible effect on the channel gains compared to that of the underlying fading processes. The results for these two scenarios given in this chapter can be summarized as follows.
63
1. For the path loss model, we construct a ”highway backbone” similar to [90]. However, in addition to the interference constraint considered in [90], our backbone construction and multi-hop forwarding strategy are designed to ensure secrecy. More specifically, an edge can be considered on the highway if and only if there is a legitimate node within the corresponding square of the edge and if there is no eavesdropper within a certain secrecy zone around the node. We show that the network still percolates in this dependent edge model. That is, many highway paths with desired properties can be constructed. Here, in addition to the careful choice of the secrecy zone, our novel multi-hop strategy, which enforces the usage of an independent randomization at each hop, allows the legitimate nodes to create an advantage over the eavesdroppers, which is, then, exploited to transmit secure bits using the nodes on the highways as relays. This way, we show that, as long as λe /λ = o ((log n)−2 ), almost all source-destination pairs achieve a secure rate of Ω
1 √ n
with high probability.
This implies that the secrecy constraint does not entail a loss in the per-node throughput (in terms of the scaling). (Note that λ = 1 for extended networks and λ = n for dense networks.) In these scenarios, the proposed scheme, which uses independent randomization at the transmitter of each hop, is the crucial step to obtain the results. 2. For the ergodic fading model, employing the ergodic interference alignment scheme ([96], [85], [86]) with an appropriate secrecy pre-coding at each source, we show that each user can achieve secrecy. Here, the secrecy rate per user is shown to be positive for most of the relevant fading distributions. In particular, in the high SNR regime, the proposed scheme allows each user to achieve a 64
1 secure degrees of freedom of η = [ 1 − n ]+ even with the absence of eavesdropper 2
CSI. Interestingly, we observe that, per node performance of users increase as we add more legitimate users in the network for this scenario, contrary to the result obtained for the path loss model. 3. Finally, we focus on the effect of eavesdropper collusion on secrecy capacity scaling. Here, the eavesdroppers are assumed to share their observations freely. That is, each eavesdropper not only knows its received symbols, but also it is assumed to be given the signals received by all (or a subset) of the remaining eavesdroppers. For the extended networks with the path loss model, the same secrecy rate scaling result is shown to hold for the colluding eavesdropper scenario when λe = O (log n)−2(1+p) for any p > 0. For the ergodic fading model, extensions to many eavesdropper collusion scenarios are discussed. In the extreme case, where all the eavesdroppers collude, it is shown that the proposed scheme allows each user to achieve a secure degrees of freedom of η = [ 1 − ne ]+ . 2 n We note that, for the path loss model under the stated assumptions, the eavesdropper collusion does not affect the performance of our multi-hop scheme (in terms of scaling). On the contrary, for the ergodic fading model, the eavesdropper collusion has a clear effect on the achievable performance of our ergodic interference alignment scheme. The rest of this chapter is organized as follows. Section 4.1 provides the two network models, namely the path loss and the ergodic fading models. In Section 4.2, we focus on the path loss model and develop our novel multi-hop secret encoding scheme. Section 4.3 investigates the ergodic fading scenario and proposes ergodic interference alignment scheme for security applications. In Section 4.4, we consider 65
the effect of eavesdropper collusion on the secrecy capacity scaling. To enhance the flow of the paper, some of technical lemmas and proofs are relegated to the Appendix C.
4.1
Network Models
The set of legitimate nodes is denoted by L, whereas the set of eavesdroppers is represented by E. During time slot t, the set of transmitting nodes are denoted by T (t) ⊂ L. User i ∈ T (t) transmits the signal Xi (t). The received signals at receiving node j ∈ L − T (t) and at eavesdropper e ∈ E are denoted by Yj (t) and Ye (t), respectively: Yj (t) = i∈T (t)
where receivers are impaired by additive noises that are distributed according to CN (0, N0 ). Assuming that each transmitter is active over N channel uses, the average power constraint on channel inputs at each transmitter is given by Note that, for i.i.d. CN (0, P ) input distribution, SNR per complex symbol.
P No 1 N N t=1
|Xi(t)|2 ≤ P .
is the signal-to-noise ratio
4.1.1
Static Path Loss Model with Stochastic Node Distribution
In the path loss model we consider, the signal power decays with the distance d as d−α for some α > 2; and the distance between node i and node j is denoted by dij . The path loss is modeled in (4.1) and (4.2) with hi,j (t) = d−α , i,j andhi,e (t) = 66 d−α . i,e (4.3)
The set of all observations at eavesdropper e is denoted by Ye
{Ye (t), ∀t}. To
analyze the worst case scenario from a security perspective, the legitimate receivers are assumed to consider interference as noise, whereas no such assumption is made on the eavesdroppers. The extended network model has a square area of side-length √ n (the area of
the region is n). The legitimate nodes and eavesdroppers are assumed to be placed randomly according to Poisson point processes of intensity λ = 1 and λe , respectively. The transmitters are assumed to have the a-priori knowledge of whether there is any eavesdropper within some neighborhood or not (the size of the neighborhood will be clear in later parts of the chapter). This assumption is a bit idealistic. Nevertheless, we believe that it allows for extracting valuable insights from the problem. Now, consider any random source-destination pair, where the source s wishes to transmit the message Ws,d securely to the intended destination d. In our multi-hop strategy, each transmission consists of N channel uses per hop. We say that the secret rate of R is achievable for almost all the source-destination pairs (s, d), if • The error probability of decoding the intended message at the intended receiver can be made arbitrarily small as N → ∞, and • The information leakage rate associated with the transmissions of the message over the entire path, i.e., N → ∞, for almost all (s, d) (i.e., the ratio of the source-destination pairs that do not satisfy the above requirements should scale as o(1)).
I(Ws,d ;Ye ) , N
can be made arbitrarily small ∀e ∈ E as
67
Let us denote the length-N channel output vector at eavesdropper e ∈ E during hop h as Ye (h). Then, if there are H hops carrying the message Ws,d, one only needs to consider the associated channel observations at the eavesdropper when evaluating our security constraint. Hence, our second condition is satisfied if I(Ws,d; Ye (1), · · · , Ye (H)) N can be made arbitrarily small for sufficiently large block lengths 7 . To derive our asymptotic scaling results, we use the following probabilistic version of Landau’s notation. We say f (n) = O(g(n)) w.h.p., if there exists a constant k such that n→∞ (4.4)
lim Pr {f (n) ≤ kg(n)} = 1.
We also say that f (n) = Ω(g(n)) w.h.p., if w.h.p. g(n) = O(f (n)). We also analyze dense networks with the path loss model and stochastic node distribution similar to above, where we assume that the network is deployed on a square region of unit area. In this case, we assume that the legitimate nodes have an intensity of λ = n.
4.1.2
Ergodic Fading Model
We assume that each transmitter in the network has an arbitrary and distinct receiver, and the set of legitimate nodes, i.e., L, consists of n source-destination pairs. For notational convenience, we enumerate each transmitter-receiver pair using an element of K = {1, · · · , n}, and denote the channel gain process associated with
We note that the length of the observation vector Ye regarding message Ws,d is N H for H hops and N channel uses per hop. Therefore, to analyze the mutual information leakage rate per I(Ws,d ;Ye (1),··· ,Ye (H)) channel use one might be tempted to use in the secrecy constraint. However, NH as H hops carry the same message Ws,d , the overall information accumulation at the eavesdropper I(Ws,d ;Ye (1),··· ,Ye (H)) might be large even if is made arbitrarily small. NH
7
68
transmitter-receiver pair i with hi,i (t). Fading process for the link from i ∈ K to k ∈ K ∪ E, denoted by hi,k (t) in (4.1) and (4.2), is assumed to be drawn i.i.d. across time according to some ergodic fading process satisfying the following two assumptions: 1. The channel gains of the legitimate users, hi,j , are assumed to be drawn from independent distributions (for each i, j ∈ K) that are symmetric around zero (that is Pr{hi,j = h} = Pr{hi,j = −h}); and 2. The fading process for eavesdropper e ∈ E, i.e., hi,e , is assumed to be drawn independently from the same distribution ∀i ∈ K. We remark that, as we assume a certain distribution for any given transmitter-receiver pair, the location of the nodes are not relevant in this model. In addition, the second assumption on the fading processes ensures that each eavesdropper has statistically the same channel to each transmitter. We denote Ye H(N)}, He (t) {Ye (1), · · · , Ye (N)}, H(t) {hi,j (t), ∀i, j ∈ K}, H {H(1), · · · ,
{hi,e (t), ∀i ∈ K, ∀e ∈ E}, and He
{He (1), · · · , He (N)}. Here, H
is assumed to be known at legitimate users, whereas eavesdroppers are assumed to know both H and He . In this model, transmitter-receiver pair i ∈ K tries to communicate a secret message Wi ∈ Wi . Denoting the decoding error at the receiver by Pe,i, we say that the secret rate Ri is achievable, if for any ǫ > 0, |Wi | ≥ 2N Ri Pe,i ≤ ǫ 1 I(Wi ; Ye , H, He ) ≤ ǫ, N 69 (4.5) (4.6) (4.7)
∀e ∈ E, for sufficiently large N. We finally say that the symmetric secure degrees of freedom (DoF) (per orthogonal dimension) of η is achievable, if the rate Ri is achievable for pair i ∈ K and η≤ Ri , ∀i ∈ K. SNR→∞ log(SNR) lim (4.8)
4.2
The Path Loss Model
In this section, we first focus on extended networks with a path loss model (α > 2) and stochastic node distribution (Poisson point processes) as detailed in Section 4.1.1. Our achievability argument is divided into the following four key steps: 1. Lemma 4.1 uses the idea of secrecy zone to guarantee the secrecy of the communication over a single hop. 2. In Lemma 4.2, we introduce our novel multi-hop forwarding strategy which uses independent randomization signal in each hop. This strategy is shown to allow for hiding the information from an eavesdropper which listens to the transmissions over all hops. 3. Using tools from percolation theory, we show the existence of a sufficient number of horizontal and vertical highways in Lemma 4.3. 4. We characterize the rate assigned to each node on the highway in Lemma 4.4. 5. The accessibility of highways for almost all the nodes in the networks with the appropriate rates is established in Lemma 4.5.
70
e3 s e1 e2 e|E|
d
Figure 4.1: A typical multi-hop route consists of four transmission phases: 1) From source node to an entry point on the horizontal highway, 2) Across horizontal highway (message is carried until the desired vertical highway member), 3) Across vertical highway (message is carried until the exit node), and 4) From the exit node to the destination node.
Our main result, i.e., Theorem 4.6, is then proved by combining the aforementioned steps with a multi-hop routing scheme. This multi-hop scheme is based on fourphase time division procedure, in which a) sources access to horizontal highways, b) horizontal highways carry the messages to an appropriate vertical highway, c) vertical highway carries the message to an appropriate exit node, and d) the exit node delivers the message to the destination. Please refer to Fig. 4.1. We partition the network area into squares of constant side length c. We further divide the area into larger squares of side ft dc, each of which contains (ft d)2 small squares. These small squares take turn over a Time-Division-Multiple-Access
71
ft dc fe dc dc
e
c e e
Figure 4.2: The transmitter located at the center of the figure wishes to communicate with a receiver that is d squares away. The second square surrounding the transmitter is the secrecy zone, which is the region of points that are at most fe d squares away from the transmitter. Side length of each square is denoted by c. The time division approach is represented by the shaded squares that are allowed for transmission. It is evident from the dashed square that the time division requires (ft d)2 time slots.
(TDMA) frame of size (ft d)2 slots. In each slot, a transmitter within each active small square can transmit to a receiver that is located at most d squares away as illustrated in Fig. 4.2. On the same figure, we also show the secrecy zone, around a transmitting square, consisting of squares that are at most fe d squares away. Our first result establishes an achievable secure rate per a single hop, active over N channel uses, under the assumption of a single eavesdropper on the boundary of the secrecy zone.
72
Lemma 4.1 (Secure Rate per Hop). In a communication scenario given by Fig. 4.2, the secure rate, simultaneously achievable between any active transmitter-receiver pair is: RT R = where SNRT R S(α) SNRe∗ ft and √ P (d + 1)−α c−α ( 2)−α , No + P 8(ft )−α d−α c−α S(α)
∞ i=1
1 log(1 + SNRT R ) − log(1 + SNRe∗ ) , (ft d)2
(4.9)
(4.10) (4.11) (4.12) (4.13)
i(i − 0.5)−α ,
P (fe )−α d−α c−α , No 2(d + 1) ≥ , d
√ (d + 1)α ( 2)α P 1+ 8(ft )−α d−α c−α S(α) < (fe )α . α (d) No
(4.14)
Here, secrecy is guaranteed assuming the presence of an eavesdropper on the boundary of the secrecy zone. Proof. In Fig. 4.2, consider that one node per filled square is transmitting. Assuming that there is a transmission from every such square, we denote the interference set seen by our designated legitimate receiver as I. Since the legitimate receivers simply consider other transmissions as noise in our model, we obtain the following SNR at the legitimate receiver. SNRT R = P d−α TR , No + P d−α iR i∈I (4.15)
where the distance between the transmitter and receiver is denoted as dT R and that between interferer i ∈ I and our receiver is denoted by diR . 73
We now consider an eavesdropper e ∈ E listening to the transmission and upper bound its received SNR by the following. SNRe ≤ P d−α Te , No (4.16)
where the distance between the transmitter and the eavesdropper e is denoted by dT e . Here, the upper bound follows by eliminating the interference at the eavesdropper. The construction in Fig. 4.2 allows for showing that √ dT R ≤ (d + 1)c 2, dT e ≥ fe dc, and d−α = iR i∈I (a) ∞ i=1
(4.17) (4.18)
8i(ift d − (d + 1))−α c−α
∞ i=1
≤ 8(ft dc)−α
i(i − 0.5)−α (4.19)
= 8(ft dc)−α S(α), where (a) follows by choosing ft d ≥ 2(d + 1), and the last equality follows by defining S(α)
∞ i=1
(4.20)
i(i − 0.5)−α ,
(4.21)
which converges to some finite value as α > 2. Using (4.17), (4.18), (4.19) in (4.15) and (4.16), we obtain the followings. SNRT R ≥ SNRT R √ P (d + 1)−α c−α ( 2)−α , No + P 8(ft )−α d−α c−α S(α) 74 (4.22)
and SNRe ≤ SNRe∗ P (fe )−α d−α c−α . No (4.23)
Hence, SNRT R > SNRe for every eavesdropper e, once we choose fe such that √ P (d + 1)α ( 2)α 1+ 8(ft )−α d−α c−α S(α) < (fe )α . α (d) No (4.24)
We then construct the secrecy codebook at the transmitter by considering an eavesdropper that observes the signals of the transmission of this hop only with an SNR of SNRe∗ . Based on the Gaussian wiretap channel capacity [10], one can easily show that the following perfectly secure rate is achievable RT R = 1 log(1 + SNRT R ) − log(1 + SNRe∗ ) , (ft d)2 (4.25)
where the (ft d)2 term is due to time-division described above. Next we introduce our novel multi-hop randomization strategy which ensures secrecy over the entire path, from a source to a destination node, at every eavesdropper observing all transmissions. Lemma 4.2 (Securing a Multi-Hop Path). Securing each hop from an eavesdropper that is located on the boundary of the secrecy zone is sufficient to ensure secrecy from any eavesdropper which listens the transmissions from all the hops and lie outside the secrecy zones of transmitters of hops. Proof. We consider a source s, a destination d, and an eavesdropper e in the network. Without loss of generality, we assume that the multi-hop scheme uses H hops to route the message. We design the secrecy codebook at each transmitter according to highest possible eavesdropper SNR assumption for each hop. In our multi-hop routing 75
scenario, each code of the ensemble at the transmitter of hop i generates 2N (Ri +Ri − H ) codewords each entry with i.i.d. CN (0, P ), for some ǫ1 > 0, and distributes them into x 2N Ri bins. Each codeword is, therefore, represented with the tuple (ws,d, wi ), where x ws,d is the bin index (secret message) and wi is the codeword index (randomization
x
ǫ1
message). To transmit the message ws,d , the encoder of transmitter i will randomly choose a codeword within the bin ws,d according to a uniform distribution. This x codeword, i.e., Xi (ws,d, wi ), is sent from transmitter i. It is clear now that each x transmitter on the path adds independent randomness, i.e., the codeword index wi x is independent of wj for i = j.
We consider an eavesdropper at the boundary of the secrecy zone around the transmitter of the hop i, and denote it by e∗ . We subtract all the interference seen by i this virtual node and denote its observations for hop i as Ye∗ . Omitting the indices i x (ws,d, wi ), for simplicity, we denote the symbols transmitted from the transmitter i x as Xi ; and set Ri = I(Xi ; Ye∗ ) = log 1 + SNRe∗ . (Note that this is the rate loss i i
in (4.9).) We continue as below.
76
I(Ws,d; Ye ) = I(Ws,d; Ye (1), · · · , Ye (H))
(a)
≤ I(Ws,d; Ye∗ , · · · , Ye∗ ) 1 H x x = I(Ws,d, W1 , · · · , WH ; Ye∗ , · · · , Ye∗ ) 1 H x x − I(W1 , · · · , WH ; Ye∗ , · · · , Ye∗ |Ws,d ) 1 H
(b)
x x ≤ I(X1 , · · · , XH ; Ye∗ , · · · , Ye∗ ) − H(W1 , · · · , WH |Ws,d ) 1 H x x + H(W1 , · · · , WH |Ye∗ , · · · , Ye∗ , Ws,d ) 1 H
(c)
H
=
i=1
x x I(X1 , · · · , XH ; Ye∗ |Ye∗ , · · · , Ye∗ ) − H(W1 , · · · , WH ) 1 i i−1 H x x H(Wix |Ws,d, Ye∗ , · · · , Ye∗ , W1 , · · · , Wi−1 ) 1 H
+ i=1 H
= i=1 I(Xi; Ye∗ |Ye∗ , · · · , Ye∗ ) 1 i i−1 ǫ1 + H(Wix |Ye∗ , Ws,d ) i H
+ I(X1 , · · · , Xi−1, Xi+1 , · · · , XH ; Ye∗ |Ye∗ , · · · , Ye∗ , Xi ) 1 i i−1 x − NRi + N (d) H
∗ H(Ye∗ |Ye∗ , · · · , Ye∗ ) − H(Yei |Ye∗ , · · · , Ye∗ , Xi ) 1 1 i i−1 i−1
≤
i=1
x − NRi + N (e) H
ǫ1 + ǫ2 H ǫ1 + ǫ2 H
≤ =
i=1 H
x H(Ye∗ ) − H(Ye∗ |Xi ) − NRi + N i i x I(Xi; Ye∗ ) − NRi + N i
(f )
i=1 H
ǫ1 + ǫ2 H ǫ1 + ǫ2 H (4.26)
≤
i=1
x ∗ NI(Xi ; Yei ) − NRi + N
= N(ǫ1 + ǫ2 ),
77
where (a) is due to the fact that Ye∗ is an enhanced set of observations compared i to that of Ye (i), (b) is due to the data processing inequality and the Markov chain x x {Ws,d , W1 , · · · , WH } → {X1 , · · · , XH } → {Ye∗ , · · · , Ye∗ }, (c) follows since Ws,d and 1 H
Wix are independent, (d) is due to fact that the second term in the sum is zero x and due to Fano’s inequality (as we choose Ri ≤ I(Xi ; Ye∗ ), the randomized (twoi
dimensional) codebook construction allows for decoding randomization message at the eavesdropper given the bin index for almost all codebooks in the ensemble): We define the decoding error probability as Pe,e∗ i ˆ ˆ Pr{Wix = Wix }, where Wix is the
estimate of the randomization message Wix given (Ye∗ , Ws,d), and bound i
∗ H(Wix |Yei , Ws,d ) ≤ N
H(Pe,e∗ ) x i + Pe,e∗ Ri i N
≤N
ǫ2 H
(4.27)
with some ǫ2 → 0 as N → ∞, (e) follows by the fact that conditioning does not increase the entropy and the observation that H(Ye∗ |Ye∗ , · · · , Ye∗ , Xi) = H(Ye∗ |Xi ), 1 i i−1 i
N
and (f) is due to the fact that I(Xi ; Ye∗ ) = i
N t=1
t=1
I(Xi ; Ye∗ (t)|Ye∗ (1), · · · , Ye∗ (t − 1)) ≤ i i i
After setting, ǫ = ǫ1 + ǫ2 , we obtain our result: For any given ǫ > 0, as N → ∞.
I(Ws,d ;Ye ) N
0, if c ≥ c0 for some finite constant c0 > 0 and λe → 0. Proof. We first describe the notion of secure highway and the percolation model we use in the proof. We note that most of this percolation based construction is developed in [90, 95] and here we generalize it for secrecy. We say that each square is ”open” if the square has at least one legitimate node and there are no eavesdroppers in the secrecy zone around the square. We denote the probability of having at least one legitimate node in a square by p. It is evident that p = 1 − e−c , and hence, p can be made arbitrarily close to 1 by increasing c. For any given transmitting square, we denote the probability of having an eavesdropper-free secrecy zone by q. The number of eavesdroppers within a secrecy zone is a Poisson random variable with parameter λe (2fe d + 1)2 c2 , and hence, q = e−λe (2fe d+1)
2 c2 2
.
Thus, q gets arbitrarily close to 1, as n → ∞, since λe → 0 with n (fe , d, and c are some finite numbers for the highway construction). 79
We then map this model to a discrete edge-percolation model (a.k.a. bond percolation on the random square grid [93]) by drawing horizontal and vertical edges over the open squares, where an edge is called open if the corresponding square is open (see Fig. 4.3). We are interested in characterizing (horizontal and vertical) open paths that span the network area. Such open paths are our horizontal and vertical highways. We only focus on horizontal highways for the rest of the section as the results hold, due to symmetry, for the vertical highways. We remark that, in our model, the status of edges are not statistically independent due to the presence of associated secrecy zones that intersect for successive squares. Notice that the status of two edges would be independent if their secrecy zones did not intersect, which happens if there were at least 2fe d squares between two edges. Therefore, this dependent scenario is referred to as finite-dependent model, as fe and d are some finite numbers. Due to Lemma C.1, given in Appendix C.1, this dependent model stochastically dominates an independent model, in which edges are independently open with probability p′ , where p′ can be made arbitrarily high if pq can be made arbitrarily high. This independent scenario can be constructed by following the steps provided in [105]. Therefore, after proving the percolation of the network with some desirable properties under the independence assumption, the network will also percolate with the same properties under the finite dependence model as both p and q can be made sufficiently large. Using the independent edge model, applying Lemma C.2, given in Appendix C.1, with edge openness probability of p′ , and noting the fact that m = c√n (Fig. 4.3), we 2 √ obtain the following: There are w.h.p. Ω( n) horizontal paths, which, for any given κ > 0, can be grouped into disjoint sets of ⌈δ log n⌉ highways that span a rectangle 80
√
√
n (m =
√ n √ c 2
edges)
c √ c 2
Figure 4.3: Horizontal and vertical edges in the discrete bond percolation model are denoted by dotted lines. A dotted edge is open (used for the highway construction) if the corresponding square is open. There are Θ(n) number of edges in the random graph.
√ area of size (κ log n − ǫ) × n, for some δ > 0, and some ǫ → 0 as n → ∞ if p′ is high enough. Then, the network area is sliced into slabs of side length w, chosen so that the number of slabs match with the number of highways in each rectangle. Then, each source (destination) in the ith horizontal (vertical) slab will access the corresponding √ highway (Fig. 4.4). This way, each highway is required to serve at most 2w n nodes and an entry (exit) point has w.h.p. a distance of at most κ′ log n away from each source (respectively, destination) for some finite constant κ′ > 0. The former claim follows by an application of Chernoff bound, given in Lemma C.3, and union bound 81
√
n
w κ log n − ǫ
Figure 4.4: There are ⌈δ log n⌉ number of disjoint highways within each rectangle of √ size (κ log n − ǫ) × n. The legitimate users in the slab, denoted by dotted lines, of the rectangle is served by the highway denoted with red bold line.
(see [90, Lemma 2] or [95, Lemma 5.3.5] for details) and the latter incorporates √ the negligible horizontal distance (at most c 2) in addition to the vertical distance, which scales as κ log n. Finally, due to the statistical domination argument given above, these percolation results will also hold for our finite-dependent model, as pq can be made arbitrarily large as n → ∞. Formally, ∃c0 ∈ (0, ∞) such that, for any c ≥ c0 , pq can be made sufficiently high if λe → 0 as n → ∞. This translates to high enough p′ by Lemma C.1, which shows that the dependent model has the property given in Lemma C.2 as well. With the following lemma we conclude the discussion of highways.
82
Lemma 4.4 (Rate per Node on the Highways). Each node on the constructed highways can transmit to their next hop at a constant secure rate. Furthermore, the num√ ber of nodes each highway serves is O( n), and therefore each highway can w.h.p. carry a per-node secure throughput of Ω
1 √ n
.
Proof. The highways are constructed such that there is at least one legitimate node per square and there are no eavesdroppers within the secrecy zone around the squares of the highway. We choose one legitimate node per square as a member of the highway, and compute the rate that can be achieved with the multi-hop strategy. From Lemma 4.1 (with d = 1) and Lemma 4.2, one can see that highways can carry data √ securely with a constant positive rate. As each highway carries the data for O( n) nodes due to Lemma 4.3, the achievable rate per node on highways is Ω
1 √ n
.
Our final step is to show that almost all the nodes can access the highways simultaneously with high probability with a rate scaling higher than Ω
1 √ n
.
Lemma 4.5 (Access Rate to Highways). Almost all source (destination) nodes can w.h.p. simultaneously transmit (receive) their messages to (from) highways with a secure rate of Ω ((log n)−3−α ), if λe = o ((log n)−2 ). Proof. To calculate the rate of each node transmitting to the closest horizontal highway, we follow the same procedure given in the proof of Lemma 4.4. However, this time we choose d = κ′′ log n in Lemma 4.1 for some finite κ′′ > 0, as the nodes within each transmitting squares need to transmit to a receiver at a distance of at most κ′′ log n squares away (due to Lemma 4.3). (Here, we can choose smallest number κ′′ ≥ κ′ c
making κ′′ log n integer.) In addition, compared to Lemma 4.4, where only
83
one node per square is transmitting, here all legitimate nodes within small squares should access the highways w.h.p., which is accomplished with a TDMA scheme. As d = κ′′ log n → ∞, we see from (4.10), (4.12), (4.9) that a per-node rate of Ω ((log n)−2−α ) is achievable. Note that, to satisfy (4.14) and thus (4.9), any choice √ of fe > 2 suffices as n → ∞. However, for this case, due to time division between nodes within squares this rate needs to be further modified. Again applying the Chernoff bound (Lemma C.3) and the union bound one can show that there are w.h.p. O(log n) legitimate nodes in each square (see [90, Lemma 1] or [95, Lemma 5.3.4] for details). Therefore, w.h.p. the secure rate Ω ((log n)−3−α ) is achievable to the associated highway from a source node, if there is no eavesdropper in the associated secrecy zone. Next, we show that this will happen with a very high probability if λe = o ((log n)−2 ) asymptotically (as n → ∞). From Fig. 4.2, it is clear that the presence of an eavesdropper eliminates the possibility of secure access to a highway from a region of area A = (2fe d + 1)2 c2 . We denote the total number of eavesdroppers in the network as |E| (Poisson r.v. with parameter λe n), and the total number of legitimate users in the network as |L| (Poisson r.v. with parameter λn = n). Let the total area in which the eavesdroppers make it impossible to reach a highway be AE . Clearly, AE ≤ A|E|. Let us further denote the number of legitimate users in an area of A|E| as |LA|E| |. Then, using the Chebyshev inequality (please refer to Lemma C.4 in Appendix C.1), we obtain |E| ≤ (1 + ǫ)λe n, |L| ≥ (1 − ǫ)n, |LA|E| | ≤ (1 + ǫ)A|E|, 84 (4.28)
for any ǫ ∈ (0, 1) with high probability (as n → ∞). We denote the fraction of users that can not transmit to highways due to eavesdroppers as F which can be upper bounded by F ≤ |LA|E| | (1 + ǫ)2 (2fe d + 1)2 c2 λe n ≤ →0 |L| (1 − ǫ)n (4.29)
with high probability (as n → ∞). The first inequality follows since the eavesdroppers can have intersecting secrecy regions, the second inequality follows from (4.28), and the limit holds as d = κ′′ log(n) and λe = o ((log n)−2 ). This argument shows that almost all of the nodes are connected to the highways as n → ∞. Similar conclusion can be made for the final destination nodes: Any given destination node can w.h.p. receive data from the highways securely with a rate of Ω ((log n)−3−α ). We now state the main result of this section. Theorem 4.6. If the legitimate nodes have unit intensity (λ = 1) and the eavesdroppers have an intensity of λe = o ((log n)−2 ) in an extended network, almost all of the nodes can achieve a secure rate of Ω
1 √ n
with high probability.
Proof. In our multi-hop routing scheme, each user has a dedicated route (due to the time division scheme described below) with each hop sending the message to the next hop over N channel uses. The secrecy encoding at each transmitter is designed assuming an eavesdropper on the boundary of the secrecy zone and listening to this hop (observations of length N) only. This way, a transmitter can achieve the rate reported in Lemma 4.1. Then, we can argue that this secrecy encoding scheme will ensure secrecy from an eavesdropper that listens to the transmissions of every hop due to Lemma 4.2. 85
Now, the main result follows by Lemma 4.4 and Lemma 4.5 by utilizing a time division approach. That is the total transmission time of the network is divided into four phases, as shown in Fig. 4.1. During the first phase, the sources that are not affected by eavesdroppers (i.e., almost all of them due to Lemma 4.5) will w.h.p. transmit their messages to the closest highway entry point. Then, the secret messages of all nodes are carried through the horizontal highways and then the vertical highways (Lemma 4.4). During the final phase, the messages are delivered from the highways to almost all of the destinations (Lemma 4.5). Hence, by Lemma 4.4 and Lemma 4.5, as the secrecy rate scaling per node is limited by the transmissions on the highway, we can see that almost all of the nodes achieve a secure rate of Ω probability. This concludes the proof. Few remarks are now in order. 1. In this extended network, the expected number of legitimate nodes is n and the expected number of eavesdroppers is ne = o(n(log n)−2 ). Note that ne satisfies ne = O(n1−ǫ ) for any ǫ > 0, and hence network can endure eavesdroppers as long as the total number of eavesdroppers scale slightly lower than that of legitimate nodes. 2. Utilizing the upper bound of [89] for the capacity of wireless networks, we can see that Theorem 4.6 establishes the achievability of the same optimal scaling law with security constraints. It is worth noting that, in our model, the interference is considered as noise at the legitimate receivers. As shown in [98], more sophisticated cooperation strategies achieve the same throughput for the case of extended networks with α ≥ 3. This leads to the conclusion that cooperation 86
1 √ n
with high
in the sense of [98] does not increase the secrecy capacity when α ≥ 3 and λe = o ((log n)−2 ). 3. λe = o(1) is tolerable if each node shares key only with the closest highway member. If each node can share a secret key with only the closest highway member, then the proposed scheme can be combined with a one-time pad scheme (see, e.g., [3] and [7]) for accessing the highways, which results in the same scaling performance for any λe → 0 as n → ∞. 4. Can network endure λe = o(1) without key sharing? Note that in our percolation theory result, we have chosen squares of side length c (edge length in √ the square lattice was c 2, see Fig. 4.3) satisfying c ≥ c0 to make pq sufficiently large in order to have p′ >
5 6
for Lemma C.2. We remark that for independent
percolation with edge probability p′ in a random grid, for any γ ∈ (0, 1), ∃p∗ (γ) such that for p′ > p∗ (γ), the random grid contains a connected component of at least γn2 vertices (see, e.g., [95, Theorem 3.2.2]). Thus, as long as λe = o(1), for some ǫ′ , ǫ∗ > 0, we can choose a very large, but constant, c (to make sure that pq is very close to 1) to have p′ = 1 − ǫ′ > p∗ (1 − ǫ∗ ), which implies that there are w.h.p. (1 − ǫ∗ )n2 connected vertices. Therefore, we conjecture that, √ for any given ǫ > 0 and for λe = o(1), per-node secure throughput of Ω(1/ n) is achievable for (1 −ǫ) fraction of nodes (we conjecture that these are the nodes that have constant distances to highways). We now focus on the dense network scenario, where the network has a square region of unit area. The stochastic node distribution for this scenario can be modeled
87
by assuming that the distribution of legitimate and eavesdropper nodes follows Poisson point processes of intensities λ = n and λe , respectively. The proposed scheme in the previous section can be utilized for this topology and the same scaling result can be obtained for dense networks as formalized in the following corollary. Corollary 4.7. Under the stochastic modeling of node distribution (Poisson point processes) in a dense network (on a unit area region) with the path loss model (with α > 2), if the legitimate nodes have an intensity of λ = n and the eavesdropper intensity satisfies λe λ
= o ((log n)−2 ), then almost all of the nodes can simultaneously
1 √ n
achieve a secure rate of Ω
.
Proof. The claim can be proved by following the same steps of the proof of Theorem 4.6 with scaling the transmit power from P to (√P α at each transmitter, and n) √ scaling each distance parameter by dividing with n. Note that, with these scalings, signal to interference and noise ratio (SINR) calculations and percolation results remain unchanged.
4.3
The Ergodic Fading Model
We now focus on the ergodic fading model described in Section 4.1.2 and propose the ergodic interference alignment for secrecy scheme. Frequency selective slow fading channels are studied in the previous chapter, where each symbol time t = 1, · · · , N corresponds to F frequency uses and the channel states of each sub-channel remain constant for a block of N1 channel uses and i.i.d. among B blocks (N = N1 B). For such a model, we showed in Chapter 3 that the following high SNR performance is achievable using the interference alignment scheme [85]: For n source-destination pairs with ne number of external eavesdroppers, a secure DoF of η = 88
1 2
−
1 + n
per
frequency-time slot is achievable at each user in the ergodic setting, in the absence of the eavesdropper CSI, for sufficiently high SNR, N, and F . Remarkably, with this scheme, the network is secured against eavesdroppers by requiring only the statistical knowledge of the eavesdropper CSI at the network users. However, the proposed scheme only establishes a high SNR result in terms of secure DoF per user. In addition, the stated DoF gain is achieved in the limit of large number of sub-channels, which is unrealistic in practice for large number of users, n. (The result is achieved when the design parameter m gets large, where the number of frequency slots is given by F = Ω(mn ).) Providing secure transmission guarantees for users at any SNR with finite number of dimensions is of definite interest. In this section, we utilize the ergodic interference alignment scheme [96] to satisfy this quality of service (QoS) requirement at the expense of large coding delays. Ergodic interference alignment can be summarized as follows. Suppose that we can find some time indices in {1, · · · , N}, represented by ˜ ˜ ˜ t1 , t2 , · · · and their complements t1 , t2 , · · · , such that hi,i (tm ) = hi,i (tm ), ∀i ∈ K, and ˜ hi,j (tm ) = −hi,j (tm ), ∀i, j ∈ K with i = j, for m = 1, 2, · · · , N1 . Now, consider that we ˜ sent the same codeword over the resulting channels, i.e., we set Xi (tm ) = Xi (tm ), ∀m. Then, by adding the observations seen by destination i for these two time instance sequences, the effective channel can be represented as ˜ ˜ Yi (tm ) = 2hi,i (tm )Xi (tm ) + Zi (tm ) + Zi (tm ), whereas the eavesdropper e observes n 2
(4.30)
˜ Ye (tm ) = i=1 hi,e (tm ) ˜ hi,e (tm )
Xi (tm ) +
Ze (tm ) ˜ Ze (tm )
,
(4.31)
89
for m = 1, 2, · · · , N1 . Remarkably, while the interference is canceled for the legitimate users, it still exists for the eavesdropper, whose effective channel becomes multiple access channel with single input multiple output antennas (SIMO-MAC). By taking advantage of this phenomenon together with exploiting the ergodicity of the channel, secure transmission against each eavesdropper is made possible at each user for any SNR (depending on the underlying fading processes) as reported in the following theorem, which is the main result of this section. Theorem 4.8. For t = 1, 2, · · · , let ˜ Yi (t) ˜ 2hi,i(t)Xi (t) + Zi (t) + Zi (t), n (4.32)
˜ Ye (t) i=1 ˜ ˜ Hi,e (t)Xi (t) + Ze (t),
(4.33)
˜ Hi,e (t)
˜ ˜ [hi,e (t) hi,e (t)]T , and Ze (t)
˜ ˜ [Ze (t) Ze (t)]T , where, ∀i ∈ K and ∀e ∈ E, Zi
˜ ˜ and Ze are i.i.d. as Zi and Ze , respectively; and hi,e is i.i.d. as hi,e . Then, source destination pair i ∈ K can achieve the secret rate Ri = 1 1 ˜ ˜ E[I(Xi ; Yi|H)] − E[I(X1 , · · · , Xn ; Ye |H, He)] 2 2n
+
,
(4.34)
on the average, where the expectations are over underlying fading processes. Proof. We first need to quantize the channel gains to have a finite set of possible matrices. (These steps are given in [96] and provided here for completeness.) Let ǫ′ > 0. Choose τ > 0 such that Pr{∪i,j {|hi,j | > τ }} ≤ ǫ′ . This will ensure a finite quantization set. For γ > 0, the γ-quantization of hi,j is the point among γ(Z + j Z) that is closest to hi,j in Euclidean distance. The γ-quantization of channel gain matrix H(t) is denoted by Hγ (t), where each entry is γ-quantized. Thus, γ-quantized channel 90
alphabet Hγ has size satisfying (
˜
√
2τ 2n2 ) γ
≤ |Hγ | ≤ ( 2τ )2n . We denote each channel γ
2
type with Hb , for b = 1, · · · , B = |Hγ |. The complement of the channel Hb is denoted γ γ by Hb , whose diagonal elements are the same as Hb and the remaining elements are γ γ negatives of that of Hb . γ We next utilize strong typicality [82] to determine the number of channel uses for each type. Consider any i.i.d. sequence of quantized channel matrices Hγ (1), · · · , Hγ (N). Such a sequence is called δ-typical, if N(Pr{Hb } − δ) ≤ #{Hb |Hγ (1), · · · , Hγ (N)} ≤ N(Pr{Hb } + δ), γ γ γ (4.35)
where #{.|.} operator gives the number of blocks of each type. The set of such strong typical sequences is denoted by Aδ . By the strong law of large numbers, we choose sufficiently large N to have Pr{Aδ } ≥ 1 − ǫ′ . Assuming that the realized sequence of quantized channel gain matrices, i.e., Hγ (1), · · · , Hγ (N), is δ-typical, we use the first Nb N(Pr{Hb } − δ) channel uses γ
(N ) (N )
for each channel type b. This causes a loss of at most 2δNB channel uses out of N, which translates to a negligible rate loss. With again a negligible loss in the rate, we choose each Nb as even. Note that the complement block of b is ˜ which lasts for b, N˜ = Nb channel uses, as Pr{Hb } = Pr{Hb }. γ γ b We now describe the coding scheme, which can be viewed as an ergodic interference alignment coding scheme with a secrecy pre-coding. For each secrecy codebook in the ensemble of transmitter i, we generate 2N (Ri +Ri ) sequences each of length
B b=1 Nb , 2 x ˜
where entries are chosen such that they satisfy the long term average power x constraint of P . We assign each codeword to 2N Ri bins each with 2N Ri codewords. Given wi , transmitter randomly chooses a codeword in bin i according to the uniform x x distribution, which is denoted by Xi(wi , wi ), where wi is the randomization index to
91
confuse the eavesdroppers. The codeword is then divided into B blocks each with a length of
Nb 2
symbols. The codeword of block b is denoted by {Xib (t), t = 1, · · · , Nb } 2
Nb 2
and is repeated during the last
channel uses of the block ˜ i.e., Xib (t) = Xib ( Nb +t), b, 2
˜
for t = 1, · · · , Nb . The channel gains, additive noises, and the received symbols is 2 denoted with the same block, i.e., channel type, notation. Here, the effective channels during block b is given by
˜ ˜ Yib (t) = 2hb (t)Xib (t) + Zib (t) + Zib i,i
Nb +t , 2
(4.36)
and n ˜b Ye (t) = i=1 hb (t) i,e ˜ hb Nb + t i,e 2
Xib (t) +
b Ze (t) ˜ b Z e Nb + t 2
,
(4.37)
for t = 1, 2, · · · , Nb . 2 We essentially code over the above two fading channels seen by destinations and eavesdroppers. Here, to satisfy both the secrecy and the reliability constraints, we choose the rates as follows. Ri = x Ri
1 1 ˜ ˜ E[I(Xi ; Yi|H)] − E[I(X1 , · · · , Xn ; Ye |H, He )] − ǫ 2 2n 1 ˜ = E[I(X1 , · · · , Xn ; Ye |H, He )], 2n
(4.38) (4.39)
˜ where the expectation is over the ergodic channel fading, and the channel outputs Yi ˜ and Ye are given by the transformations (4.32) and (4.33), respectively. For any ǫ > 0, we choose sufficiently small δ. Then, in the limit of N → ∞, τ → ∞, γ → 0, each legitimate receiver i can decode Wi and Wix with high probability (covering a-typical behavior of the channel sequence as well) as 1 x ˜ Ri + Ri = E[I(Xi ; Yi|H)] − ǫ, 2 92 (4.40)
where ǫ covers for quantization errors and unused portion of the channel uses. For the secrecy constraint we first consider each expression on the right hand side of the following equality. 1 1 1 x x I(WK ; Ye , H, He ) = I(WK , WK ; Ye , H, He) + H(WK |WK , Ye , H, He) N N N 1 x − H(WK |WK , H, He), (4.41) N where we denote WK We have 1 1 x x I(WK , WK ; Ye , H, He) = I(WK , WK ; Ye |H, He ) N N
(a) x {Wi , ∀i ∈ K} and WK
{Wix , ∀i ∈ K}.
≤
1 ˜b I({Xib (t), ∀i, b, t}; {Ye (t), ∀b, t}|H, He) N
B
(b)
≤ =
(c)
≤
˜ E[I(X1 , · · · , Xn ; Ye |H, He )] − ǫ1 N (1 − ǫ2 ) ˜ E[I(X1 , · · · , Xn ; Ye |H, He )] − ǫ1 2 1 ˜ E[I(X1 , · · · , Xn ; Ye |H, He)] + ǫ1 ǫ2 , 2 b=1 Nb 2
(4.42)
where (a) is due to the coding scheme and the data processing inequality, (b) is due to ergodicity with some ǫ1 → 0 as N → ∞, (c) is due to unused portion of channel uses with some ǫ2 → 0 as N → ∞. Secondly, due to the ergodicity and the symmetry among tranmitters, the rate assignment implies the following: The rates satisfy 1 x ˜ Ri ≤ E[I(XS ; Ye |XK−S , H, He)], 2 (4.43)
i∈S
for any S ⊆ K. (Please refer to Lemma 8 of [106] for details.) Thus, the randomization x indices WK can be decoded at the eavesdropper e given the bin indices WK . Then,
93
utilizing Fano’s inequality and averaging over the ensemble of the codebooks, we have 1 x H(WK |WK , Ye , H, He ) ≤ ǫ3 , N with some ǫ3 → 0 as N → ∞. x Third, as WK is independent of {WK , H, He } and as each Wix is independent, we
(4.44)
have 1 1 1 x x H(WK |WK , H, He) = H(WK ) = N N N n H(Wix ) i=1 1 = N
n x NRi i=1
1 ˜ = E[I(X1 , · · · , Xn ; Ye |H, He )]. 2 Finally, using (4.42), (4.44), and (4.45) in (4.41), we obtain 1 I(WK ; Ye , H, He ) ≤ ǫ, N which implies that 1 I(Wi ; Ye , H, He) ≤ ǫ, ∀i ∈ K N with some ǫ → 0 as N → ∞, which establishes the claim.
(4.45)
(4.46)
(4.47)
Note that for i.i.d. complex Gaussian input distribution, i.e., when Xi (t) ∼ CN (0, P ), ∀i, t, the proposed scheme achieves 2P |hi,i|2 1 Ri = E log 1 + 2 N0 1 P − E log det I2 + 2n N0 n +
˜ ˜ Hi,e H∗ i,e i=1 (4.48)
for user i ∈ K. Here, for any non-degenerate fading distribution, e.g., Rayleigh fading where hi,k ∼ CN (0, 1), ∀i ∈ K, ∀k ∈ K ∪ E, the second term of (4.48) diminishes as n gets large. In particular, as n → ∞, Ri scales as Ri = 1 2P |hi,i|2 E log 1 + 2 N0 94 O(log(n)) − n
+
,
and hence we can say that each user can achieve at least a positive constant secure rate for any given SNR for sufficiently large n. (Please refer to Appendix C.2.) To quantify the behavior of the scheme in the high SNR regime, we now focus on the achievable secure DoF per user, which can be characterized by dimension counting arguments. The proposed scheme achieves η =
1 2
−
1 + n
secure DoF per
user for any given non-degenerate fading model. (This can be shown by dividing both sides of (4.48) with log SNR and taking the limit SNR → ∞ for any given n.) Note that the pre-log gain of the proposed scheme is the same as that of the scheme proposed in the previous chapter. But, remarkably, ergodic interference alignment allows us to attain secrecy at any SNR by only requiring a statistical knowledge of the eavesdropper CSI. We note that this gain is obtained at the expense of large coding delay (at least exponential in the number of users).
4.4
Eavesdropper Collusion
In a more powerful attack, eavesdroppers can collude, i.e., they can share their observations. Securing information in such a scenario will be an even more challenging task compared to non-colluding case [55, 104]. Interestingly, even with colluding eavesdroppers, we show that the scaling result for the path loss model remains the same with the proposed multi-hop scheme with almost the same eavesdropper intensity requirement. Theorem 4.9. If the legitimate nodes have unit intensity (λ = 1) and the colluding eavesdroppers have an intensity of λe = O ((log n)−2−ρ ) for any ρ > 0 in an extended network, almost all of the nodes can achieve a secure rate of Ω path loss channel model. 95
1 √ n
under the static
Proof. Please refer to Appendix C.3. We note the followings. 1. The scaling result for the colluding eavesdropper scenario requires only a slightly modified eavesdropper intensity condition compared to the non-colluding case. 2. For the highway construction of the non-colluding case, the secrecy zone with √ an area of (2dfe + 1)2 c2 with fe > 2 was sufficient. However, for the colluding eavesdropper scenario, legitimate nodes need to know whether there is an eavesdropper or not within the first layer zone, which has an area of (2dfl1 +1)2 c2 with fl1 = δ ′ log(n), where δ ′ can be chosen arbitrarily small (see (C.16)). Hence, securing the network against colluding eavesdroppers requires more information regarding the eavesdroppers compared to the non-colluding case. 3. Remarkably, the optimal scaling law (see [90]), under the stated assumptions, is achieved even when the eavesdroppers collude. For the ergodic fading model, the eavesdropper collusion decreases the achievable performance. Let us add independent observations to the received vector given in (4.33) of Theorem 4.8 according to eavesdropper collusion and denote colluding ˜ eavesdroppers’ observations by Ye∗ for e∗ ∈ E ∗ {e∗ , e∗ , · · · }. For example, if e1 1 2
˜ and e2 colludes, their cumulative observations is denoted by Ye∗ (SIMO-MAC with 1 4 receive antennas). In such a scenario, the proposed scheme achieves the following rate. Corollary 4.10. For a given eavesdropper collusion set E ∗ , source-destination pair i ∈ K achieves the following rate with the proposed ergodic interference alignment 96
scheme for the ergodic fading channel model: Ri = min∗ ∗ e ∈E
for non-degenerate fading distributions when all the eavesdroppers collude. (This can be shown from (4.49) by setting E ∗ = E, choosing the input distribution as i.i.d. CN (0, P ), dividing both sides by log SNR, and taking the limit SNR → ∞ for any given ne and n.) The effect of eavesdropper collusion is evident from this expression as compared to the result for the non-colluding case, where we showed that a secure DoF of η =
1 2
−
1 + n
per user is achievable.
97
CHAPTER 5
Polar Coding for Secure Transmission and Key Agreement over Fading Channels
Despite the renewed interest during the last decade (see, e.g., Special Issue on Information Theoretic Security, IEEE Trans. Inf. Theory, June 2008 and references therein), research on information theoretic security has been mostly focused on secrecy capacity analysis using random coding techniques. There are only a few works considering the problem of code design for security applications. For example, in [107], the authors constructed LDPC based wiretap codes for certain binary erasure channel (BEC) and binary symmetric channel (BSC) scenarios. In particular, when the main channel is noiseless and the eavesdropper channel is a BEC, [107] showed that their proposed coding scheme can approach the secrecy capacity. For other scenarios, secrecy capacity achieving code design is stated as an open problem. Similarly, [108] considers the design of secure nested codes for the noiseless main channel setting. However, designing practical codes that can achieve the secrecy capacity of a given main and eavesdropper channels remained open. In this chapter, we first consider secure communication over a binary-input degraded wiretap channel. Using the polar coding technique of Arıkan [109, 110], we
98
show that non-trivial secrecy rates are achievable. According to our best knowledge, this coding technique is the first provable and practical (having low encoding and decoding complexity) secrecy encoding technique for this set of channels. In the special case of the symmetric main and eavesdropper channels, this technique achieves the secrecy capacity of the channel 8 . Secondly, we extend the results to the multiple-access setting, where the proposed coding scheme is shown to achieve non-trivial secrecy rates for both users. Finally, we consider fading wiretap channels and propose a key agreement scheme where the main users only assumed to have the statistical knowledge of the eavesdropper CSI. The enabling observation is that by blindly using the scheme over many fading blocks, the users will eventually create an advantage over Eve, which can then be exploited to generate secret keys using privacy amplification techniques. The rest of this chapter is organized as follows. In Section 5.1, we provide a summary of Polar Codes, results stated in that section will be used in the later parts of the sequel. We focus on the point-to-point scenario in Section 5.2 and detail the analysis for the multiple-access setting in Section 5.3. Finally, we investigate the fading scenario and propose our key agreement scheme in Section 5.4. Additional results on polar codes and the proof of the result for the multiple-access scenario are provided in Appendix D to enhance the flow of the sequel.
We acknowledge that the parallel works [111, 112] independently established the result that polar codes can achieve the secrecy capacity of the degraded wiretap channels, when both main and eavesdropper channels are binary-input and symmetric (Corollary 5.7 of this note). An earlier version of our work can be found in [113].
8
99
5.1
Polar Codes
Consider a binary-input DMC (B-DMC) given by W (y|x), where x ∈ X = {0, 1}
N and y ∈ Y for some finite set Y. The N uses of W is denoted by W N (y1 |xN ). The 1
symmetric capacity of a B-DMC W is given by 1 I(W ) W (y|x) log2 2 x∈X y∈Y The Bhattacharyya parameter of W is given by Z(W ) y∈Y x′ ∈X
W (y|x) , 1 W (y|x′) 2
(5.1)
which is the mutual information I(X; Y ) when the input X is uniformly distributed.
W (y|0)W (y|1),
(5.2)
which measures the reliability of W as it is an upper bound on the probability of ML decision error on a single use of the channel. Polar codes are recently introduced by Arıkan [110]. These codes can be encoded and decoded with complexity O(N log N), while achieving an overall block-error probability that is bounded as O(2−N ) for any fixed β < β 1 2
([110], [114]). In [110], channel
polarization is used to construct codes (polar codes) that can achieve the symmetric capacity, I(W ), of any given B-DMC W . Channel polarization consists of two operations: Channel combining and channel splitting. (See also [115, 116].) Let uN be the 1 vector to be transmitted. The combined channel is represented by WN and is given by
N N WN (y1 |uN ) = W N (y1 |uN BN F ⊗n ), 1 1
(5.3) 1 0 1 1 . Note
where BN is a bit-reversal permutation matrix, N = 2n , and F
N that the actual channel input here is given by x1 = uN BN F ⊗n . The channel splitting 1
100
constructs N binary input channels from WN , where the transformation is given by
N WN (y1 , ui−1 |ui) 1 (i)
1 uN ∈X N−i i+1
2N −1
N WN (y1 |uN ). 1
(5.4)
The polarization phenomenon is shown by the following theorem. Theorem 5.1 (Theorem 1 of [110]). For any B-DMC W , N = 2n for some n, and δ ∈ (0, 1), we have |{i ∈ {1, · · · , N} : I(WN ) ∈ (1 − δ, 1]}| = I(W ), N →∞ N lim and |{i ∈ {1, · · · , N} : I(WN ) ∈ [0, δ)}| = 1 − I(W ). N →∞ N lim In order to derive the rate of the channel polarization, the random process Zn is defined in [110] and in [114]. Basically, Pr{Zn ∈ (a, b)} = |{i ∈ {1, · · · , N} : Z(W2n ) ∈ (a, b)}| N
(i) (i) (i)
(5.5)
The rate of the channel polarization is given by the following. Theorem 5.2 (Theorem 1 of [114]). For any B-DMC W and for any given β < 1 , 2 lim Pr{Zn < 2−2 } = I(W ). nβ n→∞
Now, the idea of polar coding is clear. The encoder-decoder pair, utilizing the polarization effect, will transmit data through the sub-channels for which Z(WN ) is near 0. In [110], the polar code (N, K, A, uAc ) for B-DMC W is defined by xN = 1 uN BN F ⊗n , where uAc is a given frozen vector, and the information set A is chosen 1 such that |A| = K and Z(WN ) < Z(WN ) for all i ∈ A, j ∈ Ac .
9
(i)
(i)
(j)
9
The frozen
In this chapter, for a given set A ⊆ {1, · · · , N }, we write xA to denote the sub-vector {xi : i ∈ A}. In addition, we use the following sub-vector notation: xj {xi , · · · , xj }. i
101
vector uAc is given to the decoder. Arıkan’s successive cancellation (SC) estimates the input as follows: For the frozen indices uAc = uAc . For the remaining indices s.t. ˆ
N N i ∈ A; ui = 0, if WN (y1 , ui−1|0) ≥ WN (y1 , ui−1|1) and ui = 1, otherwise. With ˆ ˆ1 ˆ1 ˆ (i) (i)
this decoder, it is shown in [110] that the average block error probability over the ensemble (consisting of all possible frozen vector choices) of polar codes is bounded by Pe (N) ≤ Z(WN ). i∈A (i)
We now state the result in [110] using the bound given in [114]. Theorem 5.3 (Theorem 2 of [114]). For any given B-DMC W with I(W ) > 0, let R < I(W ) and β ∈ (0, 1 ) be fixed. Block error probability of polar coding under SC 2 decoding (averaged over possible choices of frozen vectors) satisfies Pe (N) = O(2−N ). Note that, for any given β ∈ (0, 1 ) and ǫ > 0, we can define the sequence of polar 2 codes by choosing the information indices as AN = {i ∈ {1, · · · , N} : Z(WN ) ≤
(i)
β
1 −N β 2 }. N
Then, from the above theorems, for sufficiently large N, we can achieve the rate R= |AN | ≥ I(W ) − ǫ N
with average block error probability (averaged over the possible choices of uAc ) N Pe (N) ≤ under SC decoding. (See also [117].) 102 Z(WN ) ≤ 2−N
(i)
β
i∈AN
This result shows the existence of a polar code (N, K, A, uAc ) achieving the symmetric capacity of W . We remark that, any frozen vector choice of uAc will work for symmetric channels [110]. For our purposes, we will denote a polar code for B-DMC W with C(N, F , uF ), where the frozen set is given by F Ac . Note that, A denotes
the indices of information transmission for the polar code, whereas F is the set of frozen indices. We conclude this section by noting the following lemma (given in [117]) regarding polar coding over degraded channels. Lemma 5.4 (Lemma 4.7 of [117]). Let W : X → Y and W ′ : X → Y ′ be two BDMCs such that W is degraded w.r.t. W ′ , i.e., there exists a channel W ′′ : Y ′ → Y such that W (y|x) = y ′ ∈Y ′ (i) (i)
W ′ (y ′ |x)W ′′ (y|y ′).
(i) (i)
Then, WN is degraded w.r.t. W ′ N and Z(WN ) ≥ Z(W ′ N ).
5.2
Secure Transmission over Wiretap Channel
A discrete memoryless wiretap channel is denoted by (X , W (ym, ye |x), Ym × Ye ), for some finite sets X , Ym, Ye . Here the symbols x ∈ X are the channel inputs and the symbols (ym , ye ) ∈ Ym × Ye are the channel outputs observed at the main decoder and at the eavesdropper, respectively. The channel is memoryless and time-invariant: p(ym i , ye i |xi , ym i−1 , ye i−1 ) = W (ymi , ye i |xi ). 1 1 1
103
We assume that the transmitter has a secret message M which is to be transmitted to the receiver in N channel uses and to be secured from the eavesdropper. In this setting, a secret codebook has the following components: 1. The secret message set M. The transmitted messages are assumed to be uniformly distributed over these message sets. 2. A stochastic encoding function f (.) at the transmitter which maps the secret messages to the transmitted symbols: f : m → X for each m ∈ M. 3. Decoding function φ(.) at receiver which maps the received symbols to estimate of the message: φ(Ym ) = {m}. ˆ The reliability of transmission is measured by the following probability of error. Pe = 1 Pr {φ(Ym ) = m|(m) is sent} |M| m∈M
The secrecy is measured by the mutual information leakage rate to the eavesdropper 1 I (M; Ye ) . N We say that the rate R is an achievable secrecy rate, if, for any given ǫ > 0, there exists a secret codebook such that, 1 log(|M|) = R N Pe ≤ ǫ 1 I (M; Ye ) ≤ ǫ N for sufficiently large N. (5.6)
104
Consider a degraded binary-input wiretap channel, where, for the input set X = {0, 1}, the main channel is given by Wm (ym |x) and the eavesdropper channel is We (ye |x) = Wm (ym |x)Wd (ye |ym ). (5.8) (5.7)
ym ∈Ym
Here, the degradation is due to the distribution denoted by Wd (ye |ym ). Note that, due to degradation, polar codes designed for the eavesdropper channel
1 can be used for the main channel. For a given sufficiently large N and β ∈ (0, 2 ), let
Am = and Ae =
i ∈ {1, · · · , N} : Z(Wm N ) ≤
(i)
1 −N β 2 N 1 −N β 2 N
,
i ∈ {1, · · · , N} : Z(We N ) ≤
(i)
.
Now, consider a polar code Cm
C(N, Fm , uFm ) for the main channel with some uFm .
Due to Lemma 5.4, we have Ae ⊆ Am and hence Fm ⊆ Fe . Now, for any given length |Fe | − |Fm | vector vm and uFm , we define the frozen vector for the eavesdropper, ¯ denoted by uFe (¯m ), by choosing (uFe (¯m ))Fm = uFm and (uFe (¯m ))Fe \Fm = vm . Note v v v ¯ that, denoting Ce (¯m ) v v C(N, Fe , uFe (¯m )), the ensemble ∪vm ,uFm Ce (¯m ) is a symmetv ¯
ric capacity achieving polar code ensemble for the eavesdropper channel We (if the eavesdropper channel is symmetric, any frozen vector choice will work [110], and hence the code achieves the capacity of the eavesdropper channel for any vm , uFm ). This ¯ implies that the code for the main channel can be partitioned as Cm = ∪vm Ce (¯m ). v ¯ This observation, when considered over the ensemble of codes, enables us to construct secrecy achieving polar coding schemes, even if the eavesdropper channel is not symmetric, as characterized by the following theorem. 105
Theorem 5.5. For a binary-input degraded wiretap channel, the perfect secrecy rate of I(Wm ) − I(We ) is achieved by polar coding. Proof. We divide the proof into three parts; encoding scheme, decoding scheme, and the proof of security. Encoding: We map the secret message to be transmitted to vm and generate a ¯ random vector vr , according to uniform distribution over X , of length |Ae |. Then, the ¯
N N channel input is constructed with x1 = u1 BN F ⊗n , where uFm is the frozen vector
of the polar code Cm , uFe \Fm = vm , and uAe = vr . The polar code ensemble is ¯ ¯ constructed over all different choices of frozen vectors, i.e., uFm . Decoding: The vectors vm and vr can be decoded with the Sc decoder described ¯ ¯ above with error probability Pe = O(2−N ) (averaged over the ensemble) achieving a rate R =
|¯m | v N β = I(Wm ) − I(We ) for sufficiently large N.
Security: Lets assume that the vector vm is given to the eavesdropper (say by ¯ an oracle) along with uFm . Then, employing the SC decoding, the eavesdropper can decode the random vector vr with Pe = O(2−N ) averaged over the ensemble. ¯ Utilizing the Fano’s inequality and average it over the code ensemble seen by the ¯ Eve, i.e. over Vm and UFm , we obtain
N ¯ ¯ H(Vr |Vm , UFm , Ye 1 ) ≤ H(Pe ) + N log(|X |)Pe ≤ Nǫ(N), β (5.9)
where ǫ(N) → 0 as N → ∞.
106
Then, the mutual information leakage to the eavesdropper averaged over the ensemble can be bounded as follows. ¯ I(M; Ye N |UFm ) = I(Vm ; Ye N |UFm ) 1 1 ¯ ¯ ¯ ¯ = I(Vm , Vr ; Ye N |UFm ) − I(Vr ; Ye N |Vm , UFm ) 1 1
(a) (b) N ¯ ¯ ¯ = I(U1 ; Ye N ) − H(Vr ) + H(Vr |Vm , UFm , Ye N ) 1 1 N ¯ ¯ ¯ ≤ I(X1 ; Ye N ) − H(Vr ) + H(Vr |Vm , UFm , Ye N ) 1 1
(5.10) (5.11) (5.12) (5.13) (5.14) (5.15)
(c)
¯ ¯ ≤ NI(We ) − |Ae | + H(Vr |Vm , uFm , Ye N ) 1
(d)
≤ NI(We ) − |Ae | + Nǫ(N),
N where in (a) we have U1 each entry with i.i.d. uniformly distributed, (b) follows N from data processing inequality, (c) is due to I(X1 ; Ye N ) = 1 N i=1 N i=1 N I(X1 ; Yei |Ye i−1 ) ≤ 1
H(Yei ) −H(Yei |Xi ) = NI(Xi ; Yei ) with a uniformly distributed Xi , and (d) follows
|Ae | N
from (5.9) with ǫ(N) → 0 as N → ∞. As
→ I(We ) as N gets large, we obtain (5.16)
1 ¯ I(Vm ; Ye N |UFm ) ≤ ǫ 1 N
for a given ǫ > 0 for sufficiently large N. As the reliability and secrecy constraints are satisfied averaged over the ensemble, there exist a polar code with some fixed uFm achieving the secure rate I(Wm ) − I(We ). Note that in the above result, the code satisfying the reliability and the secrecy constraints can be found from the ensemble by an exhaustive search. However, as block length increases, almost all the codes in the ensemble will do equally well. If the eavesdropper channel is symmetric, then the secrecy constraint is satisfied for any given frozen vector uFm and the code search is only for the reliability constraint. If 107
the eavesdropper channel is not symmetric, a prefix channel can be utilized to have this property. Corollary 5.6. For non-symmetric eavesdropper channels, the channel can be prefixed with some p(x|x′ ) such that the resulting eavesdropper channel We′ (ye |x′ ) = p(x|x′ )Wm (ym |x)Wd (ye |ym)
ym ∈Ym
is symmetric. Then, using the scheme above, the secret rate
′ R = I(Wm ) − I(We′ ) ′ is achievable, where Wm (ym |x′ ) = p(x|x′ )Wm (ym |x).
Finally, we note that the scheme achieves the secrecy capacity and any code in the ensemble, i.e., any fixed uFm , will satisfy both the reliability and secrecy constraints, if the main and eavesdropper channels are symmetric. Corollary 5.7. For a binary-input degraded wiretap channel with symmetric main and eavesdropper channels, polar coding achieves the secrecy capacity of the channel, i.e., C(Wm ) − C(We ). We note that the stated results are achievable by encoders and decoders with complexity of O(N log N) for each. In addition, if the channels are binary erasure channels (BECs), then there exists algorithms with complexity O(N) for the code construction [110].
5.3
Secure Transmission over Multiple-Access Channel
A discrete memoryless two-user multiple access channel with an eavesdropper (MAC-E) is denoted by (X1 × X2 , W (ym , ye |x1 , x2 ), Ym × Ye ), 108
for some finite sets X1 , X2 , Ym , Ye . Here the symbols (x1 , x2 ) ∈ X1 ×X2 are the channel inputs and the symbols (ym , ye ) ∈ Ym × Ye are the channel outputs observed at the main decoder and at the eavesdropper, respectively. The channel is memoryless and time-invariant: p(ym i , ye i |x1 i , x2 i , ym i−1 , ye i−1 ) = W (ym i , ye i |x1i , x2i ). 1 1 1 1 We assume that each transmitter k ∈ {1, 2} has a secret message Mk which is to be transmitted to the receiver in N channel uses and to be secured from the eavesdropper. In this setting, secret codebooks have the following components: 1. The secret message set Mk ; k = 1, 2. The transmitted messages are assumed to be uniformly distributed over these message sets. 2. A stochastic encoding function fk (.) at transmitter k which maps the secret messages to the transmitted symbols: fk : mk → Xk for each mk ∈ Mk ; k = 1, 2. 3. Decoding function φ(.) at receiver which maps the received symbols to estimates of the messages: φ(Ym ) = {m1 , m2 }. ˆ ˆ The reliability of transmission is measured by the following probability of error. Pe = 1 |M1||M2 | Pr {φ(Ym ) = {m1 , m2 }|(m1 , m2 ) is sent}
(m1 ,m2 )∈M1 ×M2
The secrecy is measured by the mutual information leakage rate to the eavesdropper 1 I (M1 , M2 ; Ye ) . N
109
We say that the rate tuple (R1 , R2 ) is achievable for the channel, if, for any given ǫ > 0, there exists a secret codebook such that, 1 log(|M1 |) = R1 N 1 log(|M2 |) = R2 , N Pe ≤ ǫ, and 1 I (M1 , M2 ; Ye ) ≤ ǫ N for sufficiently large N. Finally, we note that the secrecy requirement imposed on the full message set implies the secrecy of individual messages. In other words,
1 implies n I(Mk ; Ye N ) ≤ ǫ for k = 1, 2. 1 1 I(M1 , M2 ; Ye N ) 1 n
(5.17)
≤ ǫ
We focus on a binary-input degraded MAC-E, where the main channel is given by Wm (ym |x1 , x2 ) and the eavesdropper channel is We (ye |x1 , x2 ) = Wm (ym |x1 , x2 )Wd (ye |ym ). (5.19) (5.18)
ym ∈Ym
Here, the degradation is due to the distribution denoted by Wd (ye |ym ). Utilizing the scheme given in the previous section together with a successive cancelation scheme for decoding the messages, we obtain the following result.
for uniform input distributions p(x1 ) and p(x2 ). Then, the secret rate pair R1 = I(W1m ) − I(W1e ) R2 = I(W2m ) − I(W2e ) is achieved by polar coding. Proof. Please refer to Appendix D.2. Note that another rate pair that is obtained by reversing the indices above is achievable. The overall region can be stated as the time sharing of the two rate pairs. Here, as noted in the previous section, the secrecy constraint is satisfied w.h.p. for any code pair in the ensembles of users as block length gets large (if an exhaustive search over the ensembles is not possible). But, if the channels W1e and W2e defined in the theorem are symmetric, and sum of the capacity of these channels is equal to the sum capacity of Eve, i.e., p(x1 )p(x2 )
(5.20) (5.21)
max I(X1 , X2 ; Ye )
= I(W1e ) + I(W2e ), then
(using this at step (a) of (D.5)) we can show that any code pair in the ensembles satisfy the reliability and secrecy constraints.
111
5.4
Secret Key Agreement over Fading Wiretap Channels
In this section, we focus on the following key agreement problem: Alice, over (slow) fading wiretap channel, would like to agree on a secret key with Bob in the presence of passive eavesdropper Eve. We focus on the special case of binary erasure main and eavesdropper channels, for which the code construction is shown to be simple [110]. We note that the results can be extended to arbitrary binary-input channels using the result of Section 5.2. Fading blocks are represented by i = 1, · · · , LM, each block has N channel uses, and there are L super blocks each with M fading blocks. Random variables over blocks ¯ (l;m) denotes the observations of are represented with the following bar notation. Ye Eve over the fading block m of the super block l, the observations of Eve over super ¯ (l) ¯ (l;1···M ) block l ∈ [1, · · · , L] is denoted by Ye = Ye ¯ {Y e
(l;1)
¯ (l;M ) }, and Eve’s , · · · , Ye
¯ (1···L) = {Ye(1) , · · · , Ye(L) }. ¯ ¯ total observation over all super blocks is denoted by Ye∗ = Ye Main and eavesdropper channels are binary erasure channels and are denoted by Wm and We , respectively. Here, the channels Wm and We are random, outcome of which result in the channels of each block. Instantaneous eavesdropper CSI is not known at the users, only the statistical knowledge of it is assumed. The channels are assumed to be physically degraded w.r.t. some order at each block.
10 (i) (i)
Note that, in
this setup, eavesdropper channel can be better than the main channel on the average. We utilize the proposed secrecy encoding scheme for the wiretap channel at each fading block. Omitting the block indices, frozen and information bits are denoted as uFM and uAM , respectively. Information bits are uniformly distributed binary
We remark that a random walk model with packet erasures can be covered with this model. Also, parallel channel model can be adapted into this framework.
10
112
random variables and are mapped to uAM . Secret and randomization bits among these ¯ ¯ information bits are denoted by Vm and Vr , respectively. Frozen bits are provided both to main receiver and eavesdropper at each block. (We omitted writing this side information below as all zero vector can be chosen as the frozen vector for the erasure ¯ (i) channel [110].) Note that Alice and Bob do not know the length of Vm at fading block i. In particular, there may not be any secured bits at a given fading block. At this point, if the eavesdropper is degraded, we have 1 (i) ¯ (i) H(Vm ) = C(Wm ) − C(We(i) ) N 1 ¯ H(Vr(i) ) = C(We(i) ) N 1 ¯ ¯ ¯ (i) H(Vr(i) |Ye(i) , Vm ) ≤ ǫ, N (5.22) (5.23) (5.24)
¯ (i) where the last inequality follows from Fano’s inequality if Vm is given to Eve by an oracle, for sufficiently large N. Otherwise, if the main receiver is degraded, we have ¯ (i) H(Vm ) = 0 1 (i) ¯ H(Vr(i) ) = C(Wm ) N 1 ¯ ¯ H(Vr(i) |Ye(i) ) ≤ ǫ, N for sufficiently large N. Considering the resulting information accumulation over a block, we obtain the followings. 1 (i) ¯ (i) H(Vm ) = [C(Wm ) − C(We(i) )]+ , N and 1 (i) ¯ H(Vr(i) ) = min{C(Wm ), C(We(i) )}, N (5.29) (5.28) (5.25) (5.26) (5.27)
113
where the former denotes the amount of secure information generated at block i (here the secrecy level is the bound on the mutual information leakage rate), and the latter denotes the remaining information. Note that these entropies are random variables as channels are random over the blocks. Remarkable, this scheme converts the fading phenomenon to the advantage of Alice and Bob (similar to the enabling observation utilized in [66]). Exploiting this observation and coding over LM fading blocks, the proposed scheme below creates advantage for the main users: As L, M, N get large, information bits, denoted by W ∗ , are w.h.p. reliably decoded at the Bob, H(W ∗ ) → LMN E [C(Wm )], and H(W ∗|Ye∗ ) → LMN E [[C(Wm ) − C(We )]+ ]. This accomplishes both advantage distillation and information reconciliation phases of a key agreement protocol [118, 119]. Now, a third phase (called as privacy amplification) is needed to distill a shorter string K from W ∗ , about which Eve has only a negligible amount of information. The privacy amplification step can be done with universal hashing as considered in [118]. We first state the following definitions and lemma regarding universal hashing, and then formalize the main result of this section in the following theorem. Definition 5.9. A class G of functions A → B is universal if, for any x1 = x2 in A, the probability that g(x1 ) = g(x2 ) is at most according to the uniform distribution. There are efficient universal classes, e.g., to map n bits to r bits, class of linear functions given by r × n matrices needs rn bits to describe [120]. Note that hash function should have complexity as a) it will be revealed to each user, and b) Alice and Bob will compute g(W ∗). There are more efficient classes with polynomial time evaluation complexity and O(n) description complexity [120]. 114
1 |B|
when g is chosen as random from G
Generalized privacy amplification, proposed in [118], is based on the following property of universal hashing. Lemma 5.10 (Theorem 3, [118]). Let X ∈ X be a random variable with distribution PX and R´nyi entropy (of second order) R(X) = − log2 E[PX (X)]. Let G be a random e choice (according to uniform distribution) of a member of universal class of hash functions X → {0, 1}r , and let Q = G(X). Then, we have H(Q|G) ≥ R(Q|G) ≥ r − log2 1 + 2r−R(X) ≥ r − 2r−R(X) . ln 2
Exploiting the proposed coding scheme, which creates advantage in favor of Bob over the fading channel, we use the hash functions described above and obtain the following result. Theorem 5.11. For any ǫ, ǫ∗ > 0, let n = L M N (E [C(Wm )] − ǫ∗ ) , and r = L M N E [C(Wm ) − C(We )]+ − ǫ∗ . Then, for sufficiently large L, M and N, Alice and Bob can w.h.p. agree on the random variable W ∗ ¯ W (1···L) of length n over LM fading blocks (i.e., Pr{W ∗ =
ˆ ˆ W ∗ } ≤ ǫ, where W ∗ denotes the estimate at Bob); and choose K = G(W ∗ ) as their secret key (here G is chosen uniformly random from universal class of hash functions {0, 1}n → {0, 1}r ) satisfying I(K; Ye∗ , G) ≤ ǫ, where Ye∗ ¯ (1···L) denotes the Eve’s total received symbols. Ye 115
Proof. We repeat the described scheme over LM fading blocks. Due to the construction above, we have 1 1 1 ¯ (i) ¯ (i) ¯ ¯ (i) H(Vm ) − ǫ1 ≤ H(Vm |Ye(i) ) ≤ H(Vm ), N N N where
1 ¯ (i) H(Vm ) N (i) (i)
(5.30)
= [C(Wm ) − C(We )]+ and ǫ1 → 0 as N gets large (follows from
¯ (i) the fact that conditioning does not increase entropy and the security of Vm ), and 1 ¯ ¯ ¯ (i) H(Vr(i) |Ye(i) , Vm ) ≤ ǫ2 , N where ǫ2 → 0 as N → ∞ (follows from Fano’s inequality). We now consider the total information accumulation and leakage. Let W ∗ = ¯ W (1···L) ¯ { Vm
(l;m)
(5.31)
¯ , Vr
(l;m)
, ∀l ∈ [1, L], ∀m ∈ [1, M]} and denote the estimate of it at
ˆ Bob as W ∗ . We obtain that, there exist N1 , M1 , s.t. for any N ≥ N1 and M ≥ M1 , we have H(W ∗) ≥ LMN (E [C(Wm )] − ǫ∗ ) β ˆ Pr{W ∗ = W ∗ } ≤ LM2−N ,
(5.32) (5.33)
for some β ∈ (0, 1 ) due to polar coding and the union bound. 2 Considering Ye∗ ¯ (1···L) at Eve, we write Ye
L
where ǫ4 and ǫ5 vanishes as M, N get large. In order to translate H(W ∗|Ye∗ ) to R´nyi entropy, to use Lemma 5.10 in our probe lem, we resort to typical sequences, as for a uniform random variable both measures ¯ ¯ ¯ (1) ¯ (L) are the same. Considering (W (1) , · · · , W (L) , Ye , · · · , Ye ) as L repetitions of the ex¯ ¯ periment of super block random variables (W, Ye ), we define the event T based on typ¯(1···L) ) ¯ ¯ ical sets as follows [11]: Let δ > 0. T = 1, if the sequences w (1···L) and (w (1···L) , ye ¯(1···L) is such that the probability that (w ′ (1···L) , ye ¯ ¯(1···L) ) is δ-typical are δ-typical; and ye ¯ (1···L) |ye ¯ ¯(1···L) ). Otherwise, is at least 1−δ, which is taken over w ′ (1···L) according to p(W ′ we set T = 0 and denote δ0 Pr{T = 0}. Then, by Lemma 6 of [11], as L → ∞ Lδ0 → 0, Lδ → 0, and ¯ ¯ ¯ ¯ ¯(1···L) , T = 1) ≥ L(H(W |Ye ) − 2δ) + log(1 − δ). R(W (1···L) |Ye(1···L) = ye We continue as follows. (5.36)
where δ ∗ → 0 as M, N → ∞. Thus, for the given ǫ∗ , there exists M2 , N2 s.t. for M ≥ M2 and N ≥ N2 , ǫ∗ 2
≥ δ ∗ . We let r = LMN (E [[C(Wm ) − C(We )]+ ] − ǫ∗ ) and
consider the following bound.
H(K|Ye∗ , G) ≥ H(K|Ye∗ , G, T )
(a)
≥ (1 − δ0 )
∗ H(K|Ye∗ = ye , G, T = 1)
∗ ∗ ye ∈Ye
∗ P (Ye∗ = ye |T = 1)
(b)
≥ (1 − δ0 ) r −
2−LM N (ǫ ln 2
∗ −δ ∗ )
,
(5.39)
where in (a) δ0 is s.t. Lδ0 → 0 as L → ∞, (b) is due to Lemma 5.10 given above and due to (5.38) and the choice of r. Here, for the given ǫ > 0, there exists M3 , N3 s.t. for M ≥ M3 and N ≥ N3 ,
2−LM N( ln 2 ǫ∗ ) 2
where (a) holds if M ≥ M2 and N ≥ N2 and (b) holds if M ≥ M3 and N ≥ N3 . Now, we choose some M ≥ max{M1 , M2 , M3 }. For this choice of M, we choose sufficiently large L and sufficiently large N such that N ≥ max{N1 , N2 , N3 } and δ0 LMN ≤ LM2−N β ǫ 2
(5.44) (5.45)
≤ ǫ,
118
which holds as δ0 L → 0 as L → ∞ in (5.36). (In fact, due to [11, Lemma 4 and Lemma 6], for any ǫ′ > 0, we can take δ0 L ≤ ǫ′ L
as L gets large.) Therefore, for
this choice of L, M, N, we obtain the desired result from (5.32), (5.33), (5.43), due to (5.44) and (5.45): H(W ∗) ≥ LMN (E [C(Wm )] − ǫ∗ ) ˆ Pr{W ∗ = W ∗ } ≤ ǫ I(K; Ye∗ , G) ≤ ǫ (5.46) (5.47) (5.48)
In addition, for this choice of L, M, N, we bound H(K) ≥ r − ǫ due to (5.39), which shows that the key is approximately uniform. Few remarks are now in order. 1) The results do not depend on random coding arguments. Coding is low complex: a) Any code in the ensemble will work (frozen bits can be set to all zero vector), b) Overall encoding and decoding complexity is O(LMN log(N)) for a total number of LMN channel uses, c) Code construction has O(N) complexity for each block, as the main channel is erasure channel [110]. 2) Existing code designs in the literature and the previous section of this work assume that Eve’s channel is known at Alice and Bob. In the above scheme, Alice and Bob only need the statistical knowledge of eavesdropper CSI. Also, the main channel is not necessarily stronger than the eavesdropper channel, which is not the case for degraded wiretap settings. 3) In the above scheme, instead of hash function and R´nyi entropy, extractor e functions and min-entropy can be used [11]. Similar to above, we can obtain
∗ H∞ (W ∗ |Ye∗ = ye , T = 1) ≥ LMN(E[[C(Wm ) − C(We )]+ ] − δ ∗ ),
119
as min-entropy and entropy are equal if the random variable is uniformly distributed. Now by Lemma 9 of [11], for any ∆ > 0 and sufficiently large L, there exist an extractor g : {0, 1}n ×{0, 1}d → {0, 1}r with d ≤ ∆n s.t., if V is uniformly distributed over {0, 1}d then
∗ H(K = E(W ∗ , V )|Ye∗ = ye , g, V, T = 1) ≥ r − 2−n
1/2−o(1)
.
Note that extractors can be efficient compared to universal hashing. For example, while the randomly chosen hash function may require n bits to describe, the extractor can be described with d ≤ ∆n bits with small ∆. If the chosen (hash or extractor) function has to be communicated through the same channel, this property can be exploited to increase the key renewal rate. 4) If the inverse of the hash (or extractor) functions can be computed easily, then this scheme can be used for secure message transmission. The enabling idea is to randomly select the transmitted input (here, information bits of the polar code) among the set g −1 (K), where K here denotes the message that we would like to transmit. Then, Bob can recover the message that is secured from the Eve with the above scheme. 5) The result can be extended to the multi-eavesdropper scenario. If the eavesdroppers do not collude, we can use the worst average leakage, i.e., r = min LMN(E[[C(Wm ) − C(We )]+ ] − ǫ∗ ),
We
(5.49)
for the key. If they collude, assuming that there exist a physical degradation order among them, we can use the best eavesdropper channel for each fading block in the expression, i.e., r = LMN(E[[C(Wm ) − C(We∗ )]+ ] − ǫ∗ ), 120 (5.50)
where the expectation is over the statistics of the best eavesdropper denoted by We∗ . 6) The above scheme can be used for the wiretap channel of Section 5.2 by setting M = 0 to achieve strong secrecy (assuring arbitrarily small information leakage) instead of the weak notion (making the leakage rate small). See also [11]. 7) The results can be extended to arbitrary binary-input channels along the same lines, using the result of Section 5.2. In such a setting, the above theorem would be reformulated with n = LMN(E[I(Wm )] − ǫ∗ ) and r = LMN(E[[I(Wm ) − I(We )]+ ] − ǫ∗ ). However, the code construction complexity of such channels may not scale as good as that of the erasure channels [110]. 8) Finally, the proposed scheme forms a cross layer security solution, as it accomplishes both advantage distillation and information reconciliation phases of the key agreement protocol at the physical layer using information theoretic insights and utilize cryptographic techniques like hashing for the privacy amplification in order to complete the key agreement protocol.
121
CHAPTER 6
Conclusions and Future Directions
6.1
Conclusions
In this thesis, we have studied physical layer security based on information theoretic principles. In particular, our focus was on multi-user interfering networks and the code design for physical layer security. First, we considered the two-user interference channel with an (external) eavesdropper. An inner bound on the achievable secrecy rate region was derived using a scheme that combines randomized encoding, channel prefixing, message splitting, and time-sharing techniques. More specifically, our achievable scheme allows the two users to cooperatively construct their randomized codebooks and channel prefixing distributions. We then derived outer bounds and showed the optimality of the proposed scheme in some special cases. For the Gaussian scenario, channel prefixing was used to allow the users to transmit independently generated noise samples using a fraction of the available power. Moreover, as a special case of time sharing, we have developed a novel cooperative TDMA scheme, where a user can add structured and unstructured noise to the channel during the allocated slot for the other user. It is shown that this scheme reduces to the noise forwarding scheme proposed earlier for 122
the relay-eavesdropper channel. In the Gaussian multiple-access setting, our cooperative encoding and channel prefixing scheme was shown to enlarge the achievable regions obtained in previous works. The most interesting aspect of our results is, perhaps, the illumination of the role of interference in cooperatively adding randomness to increase the achievable secrecy rates in multi-user networks. Secondly, we considered the K-user Gaussian interference channel with secrecy constraints. By using the interference alignment scheme along with secrecy precoding at each transmitter, we have shown that each user in the network can achieve a non-zero secure DoF. Our results differentiate between the confidential messages scenario and the case where an external eavesdropper, with unknown CSI, is present in the network. The most remarkable feature of our result is the discovery of the role of interference in increasing the secrecy capacity of multi-user wireless networks. In a third attempt, we studied the scaling behavior of the capacity of wireless networks under secrecy constraints. For extended networks with the path loss model (the exponent is assumed to satisfy α > 2), the legitimate nodes and eavesdroppers were assumed to be randomly placed in the network according to Poisson point processes of intensity λ = 1 and λe , respectively. We showed that when λe = o ((log n)−2 ), almost all of the nodes achieve a secure rate of Ω
1 √ n
. This shows that securing the
transmissions does not entail a loss in the per-node throughput for our model, where transmissions from other users are considered as noise at receivers. Our achievability argument was based on novel secure multi-hop forwarding strategy where forwarding nodes are chosen such that no eavesdroppers exist in appropriately constructed secrecy zones around them and independent randomization is employed in each hop. Tools from percolation theory were used to establish the existence of a sufficient 123
number of secure highways allowing for network connectivity. Finally, a time division approach was used to accomplish an end-to-end secure connection between almost all source-destination pairs. The same scaling result is also obtained for the dense network scenario when λe λ
= o ((log n)−2 ). We next focused on the ergodic fading model
and employed ergodic interference alignment scheme with an appropriate secrecy precoding at each user. This scheme is shown to be capable of securing each user at any SNR (depending on the underlying fading distributions), and hence provides performance guarantees even for the finite SNR regime. For the high SNR scenario, the
1 scheme achieves [ 1 − n ]+ secure DoFs per orthogonal dimension at each user. Re2
markably, the results for the ergodic fading scenarios do not require eavesdropper CSI at the legitimate users, only a statistical knowledge is sufficient. However, this gain is obtained at the expense of large coding delays. Lastly, the effect of the eavesdropper collusion is analyzed. It is shown that, for the path loss model, the same per-node throughput scaling, i.e., Ω
1 √ n
, is achievable under almost the same eavesdropper
intensity requirement. For the fading model, the proposed model is shown to endure various eavesdropper collusion scenarios. In particular, when all the eavesdroppers collude, a secure DoF of [ 1 − 2 ne + ] n
is shown to be achievable.
Finally, we focused on the problem of code design for physical layer security. We first considered polar coding for binary-input point-to-point and multiple-access DMCs with a degraded eavesdropper. We showed that polar coding can be utilized to achieve non-trivial secrecy rates for both channels. For the point-to-point case, if both receiver and eavesdropper have binary-input symmetric channels in addition to the degradedness assumption, this coding technique was shown to achieve the secrecy capacity. We then proposed a secret key agreement protocol over fading channels, 124
where we showed that Alice and Bob can create advantage over Eve by using the polar coding scheme at each fading block. This advantage offered by polar coding is then exploited with privacy amplification techniques to generate keys. This result is interesting in the sense that part of the key agreement protocol is established information theoretically over fading channels by only requiring the statistical knowledge of eavesdropper CSI at the users.
6.2
Future Directions
We now list some future directions. 1. The characterization of the secrecy capacity region of elemental networks (e.g., the two-user interference channel model considered in this thesis) is of definite interest. This study would give an idea about what kind of different coding techniques can be used for information theoretic security and what advantages these techniques can offer in terms of microscopic gains (e.g., an increase in the secrecy rate). 2. It is shown that the interference alignment technique is not only an enhanced interference management scheme but also helpful for security applications. However, this gain is achieved at the expense of long coding delays. In addition, the design of interference alignment at the users require the full knowledge of the channel state information. It would be interesting to study how a distributed algorithm (such as [121]) can perform under the secrecy constraints. 3. For the two-user network, we have assumed the knowledge of the CSI at the main users. Our interference alignment technique requires a statistical knowledge of 125
the eavesdropper CSI. Furthermore, the secrecy capacity scaling result based on multi-hop routing and percolation theory require the legitimate nodes to be aware of whether eavesdroppers exist in a certain zone (secrecy zone) or not. An analysis of a more practical scenario, in which legitimate nodes have no (or more limited) eavesdropper location information, would be interesting. 4. For the secrecy capacity scaling problem, characterizing the full trade-off between secure throughput vs. eavesdropper node intensity is of definite interest. Towards this end, we note that we have not exploited cooperation techniques to improve the achievable performance. Cooperation in the sense of [98] may be helpful. For example, in the extended network scenario, hierarchical cooperation might increase the per-node throughput for α < 3 or achieve the optimal throughput for α ≥ 3 even with higher eavesdropper intensities. In addition, cooperation for secrecy strategies (e.g., the techniques introduced in Chapter 2) may be beneficial in enhancing the scaling results. 5. We considered the notions of symmetric secure DoF and uniform secrecy rate per user for the multi-user networks. Arbitrary traffic pattern can be considered for users with distinct quality of service constraints. 6. Our polar coding for security result can be extended to arbitrary discrete memoryless channels using the techniques given in [122] (see also Appendix D.1). In addition, results for the multiple-access channels might be enhanced using the rate-splitting technique proposed in [123]. We note that, polar coding for multiple-access channels is recently considered in [124], where the authors show
126
that MAC can be polarized into five different extremal channels. This observation is used to achieve rate pairs on the dominant face of the rate region obtained by uniform inputs in [124]. This technique can be utilized in the secrecy setting by taking advantage of the extremal channels of the main channel over the eavesdropper channel. 7. Another QoS constraint is the delay encountered for the secure transmission. A recent attempt on this manner is the study of delay limited secrecy rate [67], [70]. We note that, the study of delay-secure throughput tradeoff in multiuser networks is an interesting research direction. For example, in the secrecy capacity scaling problem, this tradeoff appears as a relationship between delay, throughput, and eavesdropper density. 8. Eavesdroppers are assumed to be passive (they only listen the transmissions). An advanced attack might include active eavesdroppers [68], which can jam the wireless channel. Securing information in such scenarios is an interesting avenue for further research. Overall, information theoretic security can provide a key-less and provable secrecy design, which is critical for many applications and is of definite interest for the ongoing wireless evolution. Furthermore, the proposed techniques can be viewed as an integral part of the cross layer security approaches. For example, existing cryptographic techniques can be implemented together with the physical layer schemes based on information theoretic principles to increase the secrecy level and robustness.
127
APPENDIX A
Proofs of the Theorems and Corollaries in Chapter 2
A.1
Proof of Theorem 2.2
Fix some p(q), p(c1 |q), p(s1 |q), p(o1 |q), p(x1 |c1 , s1 , o1 ), p(c2 |q), p(s2 |q), p(o2 |q), and p(x2 |c2 , s2 , o2 ) for the channel given by p(y1 , y2 , ye |x1 , x2 ). Generate a random typical sequence qN , where p(qN ) =
N
p(q(i)) and each entry is chosen i.i.d. according to i=1 p(q). Every node knows the sequence qN . Codebook Generation: Consider transmitter k ∈ {1, 2} that has the secret message Wk ∈ Wk = {1, 2, · · · , Mk }, where Mk = 2N Rk . We construct each element in the codebook ensemble as follows. x • Generate MCk MCk = 2 N (RCk +Rx −ǫ1 ) C k sequences cN , each with probability given k
by p(cN |qN ) = k
N
i=1
p(ck (i)|q(i)), where p(ck (i)|q(i)) = p(ck |q) for each i. Dis-
tribute these into MCk = 2N RCk bins, where the bin index is wCk . Each bin x has MCk = 2 N (Rx −ǫ1 ) C k x codewords, where we denote the codeword index as wCk .
x Represent each codeword with these two indices, i.e., cN (wCk , wCk ). k x • Similarly, generate MSk MSk = 2 N (RSk +Rx −ǫ1 ) S k N sequences sk , each with prob-
ability p(sN |qN ) = k
N
i=1
p(sk (i)|q(i)), where p(sk (i)|q(i)) = p(sk |q) for each i. 128
Distribute these into MSk = 2N RSk bins, where the bin index is wSk . Each bin x has MSk = 2 N (Rx −ǫ1 ) S k x codewords, where we denote the codeword index as wSk .
x Represent each codeword with these two indices, i.e., sN (wSk , wSk ). k x • Finally, generate MOk = 2 N (Rx −ǫ1 ) O k sequences oN , each with probability given k
by p(oN |qN ) = k
N
i=1
p(ok (i)|q(i)), where p(ok (i)|q(i)) = p(ok |q) for each i. Denote
x each sequence by index wOk and represent each codeword with this index, i.e., x oN (wOk ). k
Choose Mk = MCk MSk , and assign each pair (wCk , wSk ) to a secret message wk . Note that, Rk = RCk + RSk for k = 1, 2. Every node in the network knows these codebooks. Encoding: Consider again user k ∈ {1, 2}. To send wk ∈ Wk , user k gets corresponding indices wCk and wSk . Then, user k obtains the following codewords: • From the codebook for Ck , user k randomly chooses a codeword in bin wCk according to the uniform distribution, where the codeword index is denoted by x x wCk and it gets the corresponding entry of the codebook, i.e. cN (wCk , wCk ). k
• Similarly, from the codebook for Sk , user k randomly chooses a codeword in bin wSk according to the uniform distribution, where the codeword index is denoted x N x by wSk and it gets the corresponding entry of the codebook, i.e. sk (wSk , wSk ).
• Finally, from the codebook for Ok , it randomly chooses a codeword, which is x denoted by oN (wOk ). k
129
Then, user k, generates the channel inputs xN , where each entry is chosen according k x x x to p(xk |ck , sk , ok ) using the codewords cN (wCk , wCk ), sN (wSk , wSk ), and oN (wOk ); and k k k
it transmits the constructed xN in N channel uses. See Fig. 2.4. k Decoding: Here, in addition to their intended messages, we also require the receivers to decode common and other signals of the other transmitter. Suppose receiver 1 has
N N received y1 . Let AN denote the set of typical (qN , cN , sN , cN , oN , y1 ) sequences. 1,ǫ 1 1 2 2 x x x x Decoder 1 chooses (wC1 , wC1 , wS1 , wS1 , wC2 , wC2 , wO2 ) s.t.
x x x x N (qN , cN (wC1 , wC1 ), sN (wS1 , wS1 ), cN (wC2 , wC2 ), oN (wO2 ), y1 ) ∈ AN , 1 1 2 2 1,ǫ
if such a tuple exists and is unique. Otherwise, the decoder declares an error. Decoding at receiver 2 is symmetric and a description of it can be obtained by reversing the indices 1 and 2 above. Probability of Error Analysis: Below we show that the decoding error probability of user k averaged over the ensemble can be arbitrarily made small for sufficiently large N. This demonstrates the existence of a codebook with the property that max(Pe,1 , Pe,2) ≤ ǫ, for any given ǫ > 0. The analysis follows from similar arguments given in [73]. See also [82] for joint typical decoding error computations. Here, for any given ǫ > 0, each receiver can decode corresponding messages given above with an error probability less than ǫ as N → ∞, if the rates satisfy the following equations. x RS + RS ≤ I(S; Y1 |S c , Q), ∀S ⊆ {C1 , S1 , C2 , O2 },
where inequalities are due to the fact that conditioning does not increase entropy. Here, x x x H(C1 , S1 , O1 , C2 , S2 , O2 |Q) = N(RC1 + RC1 + RS1 + RS1 + RO1 x x x + RC2 + RC2 + RS2 + RS2 + RO2 − 6ǫ1 ), (A.9)
as, for any given Q = q, the tuple (C1 , S1 , O1 , C2 , S2 , O2 ) has a value from a set with cardinality of 2N (RC1 +RC1 +RS1 +RS1 +RO1 +RC2 +RC2 +RS2 +RS2 +RO2 −6ǫ1 ) , where each value is assigned with equal probability. 131 x x x x x x
Secondly, I(C1 , S1 , O1 , C2 , S2 , O2 ; Ye |Q) ≤ NI(C1 , S1 , O1 , C2 , S2 , O2 ; Ye |Q) + Nǫ2 , where ǫ2 → 0 as N → ∞. See, for example, Lemma 8 of [8]. Lastly, for any WC1 = wC1 , WS1 = wS1 , WC2 = wC2 , WS2 = wS2 , and Q = q, we have H(C1 , S1 , O1 , C2 , S2 , O2 |WC1 = wC1 , WS1 = wS1 , WC2 = wC2 , WS2 = wS2 , Ye , Q = q) ≤ Nǫ3 , for some ǫ3 → 0 as N → ∞. This is due to the Fano’s inequality together with the randomized (two-dimensional) codebook construction: Given all the bin indices of two users, eavesdropper can decode the randomization indices among those bins (averaged over the codebook ensemble). Due to joint typicality, this latter argument holds as long as the rates satisfy the following equations. x RS ≤ I(S; Ye |S c , Q), ∀S ⊆ {C1 , S1 , O1 , C2 , S2 , O2 }.
(A.10)
(A.11)
This follows as given bin indices WC1 , WS1 , WC2 , and WS2 , this reduces to MAC probability of error computation among the codewords of those bins. See [82] for details of computing error probabilities in MAC. Then, averaging over WC1 , WS1 , WC2 , WS2 , and Q, we obtain H(C1 , S1 , O1 , C2 , S2 , O2 |WC1 , WS1 , WC2 , WS2 , Ye , Q) ≤ Nǫ3 . Hence, using (A.9), (A.10), and (A.12) in (A.8) we obtain (A.12)
R1 + R2 − as N → ∞, where we set
1 H(W1 , W2 |YeN ) ≤ 6ǫ1 + ǫ2 + ǫ3 N
ǫ → 0,
(A.13)
x RS = I(S; Ye |Q), S = {C1 , S1 , O1 , C2 , S2 , O2 }.
(A.14)
132
Combining (A.1), (A.2), (A.11), and (A.14) we obtain the result, i.e., R(p) is achievable for any p ∈ P.
A.2
Proof of Theorem 2.4
We bound R1 below. The bound on R2 can be obtained by following similar steps below and reversing the indices 1 and 2. We first state the following definitions. For ˜ any random variable Y , Y i+1 I1 i=1 N
[Y (i + 1) · · · Y (N)], and
N i−1 ˜ i+1 I(Ye ; Y1 (i)|Y1 )
(A.15) (A.16) (A.17) (A.18)
ˆ I1 i=1 N
i−1 ˜ i+1 I(Y1 ; Ye (i)|Ye )
I2 i=1 N
i−1 ˜ i+1 I(Ye ; Y1 (i)|Y1 , W1 )
ˆ I2 i=1 i−1 ˜ i+1 I(Y1 ; Ye (i)|Ye , W1 )
Then, we consider the following bound. R1 − ǫ ≤ 1 H(W1 |Ye ) n 1 = (H(W1 ) − I(W1 ; Ye )) N 1 (H(W1 |Y1 ) + I(W1 ; Y1 ) − I(W1 ; Ye )) = N N N 1 i−1 ˜ i+1 ≤ ǫ1 + I(W1 ; Y1 (i)|Y1 ) − I(W1 ; Ye (i)|Ye ) N i=1 i=1 1 = ǫ1 + N
N N i−1 ˜ i+1 I(W1 ; Y1 (i)|Y1 , Ye ) + I1 − I2
(A.19)
i=1
−
i=1
i−1 ˜ i+1 ˆ ˆ I(W1 ; Ye (i)|Y1 , Ye ) − I1 + I2 N i−1 ˜ i+1 I(W1 ; Y1 (i)|Y1 , Ye ) i=1 N i−1 ˜ i+1 I(W1 ; Ye (i)|Y1 , Ye ) , i=1
1 = ǫ1 + N
−
133
where the first inequality is due to Lemma A.1 given at the end of this section, the second inequality is due to the Fano’s inequality at the receiver 1 with some ǫ1 → 0 as ˆ ˆ N → ∞, the last equality is due to observations I1 = I1 and I2 = I2 (see [9, Lemma 7]). We define U(i) i−1 ˜ i+1 (Y1 , Ye , i), V1 (i)
(U(i), W1 ), and V2 (i)
(U(i), W2 ).
Using standard techniques (see, e.g., [82]), we introduce a random variable J, which is uniformly distributed over {1, · · · , N}, and continue as below. 1 R1 − ǫ ≤ ǫ1 + N = ǫ1 + = ǫ1 + j=1 N N i−1 ˜ i+1 I(W1 ; Y1(i)|Y1 , Ye ) i=1 N N
where the last inequality follows from the fact that V1 (j) → U(j) → V2 (j), which implies I(V1 (j); Y1 (j)|U(j)) ≤ I(V1 (j); Y1(j)|V2 (j), U(j)) after using the fact that conditioning does not increase entropy, and the last equality follows by using a standard information theoretic argument in which we define random variables for the single-letter expression, e.g., V1 has the same distribution as V1 (J). Hence, we obtain the bound, R1 ≤ [I(V1 ; Y1 |V2 , U) − I(V1 ; Ye |U)]+ , 134 (A.21)
for some auxiliary random variables that factors as p(u)p(v1 |u)p(v2|u) p(x1 |v1 )p(x2 |v2 ) p(y1 , y2 , ye |x1 , x2 ). Lemma A.1. The secrecy constraint R1 + R2 − implies that R1 − and R2 − Proof. 1 1 1 H(W1 |Ye ) = H(W1 , W2 |Ye ) − H(W2 |Ye , W1 ) N N N 1 ≥ R1 − ǫ + R2 − H(W2 |Ye , W1 ) N 1 1 = R1 − ǫ + H(W2 ) − H(W2 |Ye , W1 ) N N ≥ R1 − ǫ, (A.22) (A.23) (A.24) (A.25) 1 H(W2 |Ye ) ≤ ǫ. N 1 H(W1 |Ye ) ≤ ǫ, N 1 H(W1 , W2 |Ye ) ≤ ǫ N
where the second equality follows by H(W2 ) = NR2 , and the last inequality follows due to the fact that conditioning does not increase entropy. Second statement follows from a similar observation.
A.3
Proof of Theorem 2.5
From arguments given in [76, Lemma], the assumed property of the channel implies the following. I(V2 ; Y2 |V1 ) ≤ I(V2 ; Y1 |V1 ) 135 (A.26)
Then, by considering V1 (i) = W1 and V2 (i) = W2 , for i = 1, · · · , N, we get I(W2 ; Y2|W1 ) ≤ I(W2 ; Y1 |W1 ) We continue as follows. 1 1 1 H(W1 , W2 |Y1 ) = H(W1 |Y1 ) + H(W2 |Y1 , W1 ) N N N 1 ≤ ǫ1 + H(W2 |Y1 , W1 ) N 1 ≤ ǫ1 + H(W2 |Y2 , W1 ) N 1 ≤ ǫ1 + H(W2 |Y2 ) N ≤ ǫ1 + ǫ2 , (A.28) (A.27)
where the first inequality is due to the Fano’s inequality at the receiver 1 with some ǫ1 → 0 as N → ∞, the second inequality follows from (A.27), the third one is due to conditioning does not increase entropy, and the last one follows from the Fano’s inequality at the receiver 2 with some ǫ2 → 0 as N → ∞. We then proceed following the standard techniques given in [8, 9]. We first state the following definitions.
N
I1 i=1 N
i−1 ˜ i+1 I(Ye ; Y1 (i)|Y1 )
(A.29) (A.30) (A.31) (A.32)
ˆ I1 i=1 N
i−1 ˜ i+1 I(Y1 ; Ye (i)|Ye )
I3 i=1 N
i−1 ˜ i+1 I(Ye ; Y1 (i)|Y1 , W1 , W2 )
ˆ I3 i=1 i−1 ˜ i+1 I(Y1 ; Ye (i)|Ye , W1 , W2 ),
˜ where Y i+1
[Y (i + 1) · · · Y (N)] for random variable Y . 136
Then, we bound the sum rate as follows. R1 + R2 − ǫ ≤ 1 H(W1 , W2 |Ye ) N 1 = (H(W1 , W2 |Y1 ) + I(W1 , W2 ; Y1 ) − I(W1 , W2 ; Ye )) N N N 1 i−1 ˜ i+1 I(W1 , W2 ; Y1 (i)|Y1 ) − I(W1 , W2 ; Ye (i)|Ye ) ≤ ǫ1 + ǫ2 + N i=1 i=1 1 = ǫ1 + ǫ2 + N
N N i−1 ˜ i+1 I(W1 , W2 ; Y1(i)|Y1 , Ye ) + I1 − I3
i=1
−
i=1
i−1 ˜ i+1 ˆ ˆ I(W1 , W2 ; Ye (i)|Y1 , Ye ) − I1 + I3 N i−1 ˜ i+1 I(W1 , W2 ; Y1(i)|Y1 , Ye ) i=1
1 = ǫ1 + ǫ2 + N
N
−
i−1 ˜ i+1 I(W1 , W2 ; Ye (i)|Y1 , Ye ) , i=1
where the first inequality is due to the secrecy requirement, the last inequality follows ˆ ˆ by (A.28), and the last equality follows by the fact that I1 = I1 and I3 = I3 , which can be shown using arguments similar to [9, Lemma 7]. We define U(i) i−1 ˜ i+1 (Y1 , Ye , i), V1 (i)
(U(i), W1 ), and V2 (i)
(U(i), W2 ).
Using standard techniques (see, e.g., [82]), we introduce a random variable J, which is uniformly distributed over {1, · · · , n}, and continue as below.
where, using a standard information theoretic argument, we have defined the random variables for the single-letter expression, e.g., V1 has the same distribution as V1 (J). Now, due to the memoryless property of the channel, we have (U, V1 , V2 ) → (X1 , X2 ) → (Y1 , Y2 , Ye ), which implies p(y1 , y2 , ye |x1 , x2 , v1 , v2 , u) = p(y1 , y2 , ye |x1 , x2 ). As we define V1 (J) = (U(J), W1 ) and V2 (J) = (U(J), W2 ), we have V1 → U → V2 , which implies p(v1 , v2 |u) = p(v1 |u)p(v2 |u). Finally, as X1 (J) is a stochastic function of W1 , X2 (J) is a stochastic function of W2 , and W1 and W2 are independent, we have X1 (J) → V1 (J) → V2 (J), X2 (J) → V2 (J) → V1 (J), and X1 (J) → (V1 (J), V2 (J)) → X2 (J), which together implies that p(x1 , x2 |v1 , v2 , u) = p(x1 , x2 |v1 , v2 ) = p(x1 |v1 , v2 )p(x2 |v1 , v2 ) = p(x1 |v1 )p(x2 |v2 ) .
138
Hence, we obtain a sum-rate bound, R1 + R2 ≤ [I(V1 , V2 ; Y1 |U) − I(V1 , V2 ; Ye |U)]+ , (A.34)
for some auxiliary random variables that factors as p(u)p(v1 |u)p(v2|u) p(x1 |v1 )p(x2 |v2 ) p(y1 , y2 , ye |x1 , x2 ), if (2.9) holds.
A.4
Proof of Corollary 2.6
Achievability follows from Theorem 2.2 by only utilizing S1 and O2 together with the second equation in (2.12), where we set R2 = 0 and set R1 as follows. For a given p ∈ P(S1 , O2 ), if I(S1 ; Y1 |O2 , Q) ≤ I(S1 ; Ye |Q), we set R1 = 0; otherwise we assign the following rates. RS1 = I(S1 ; Y1 |O2 , Q) − I(S1 ; Ye |Q) x RS1 = I(S1 ; Ye |Q) x RO2 = I(O2 ; Ye |S1 , Q),
where R1 = RS1 . Converse follows from Theorem 2.4. That is, if (R1 , R2 ) is achieavable, then R1 ≤ max I(S1 ; Y1 |O2, Q) − I(S1 ; Ye |Q) and R2 = 0, due to the first condition given p∈PO in (2.12).
A.5
Proof of Corollary 2.7
Achievability follows from Theorem 2.2 by only utilizing S1 and C2 together with the channel condition given in (2.14). For a given p ∈ P(S1 , C2 ), if I(S1 , C2 ; Y1 |Q) ≤
139
I(S1 , C2 ; Ye |Q), we set R1 = R2 = 0; otherwise we assign the following rates. RS1 = I(S1 ; Y1 |C2 , Q) − I(S1 ; Ye |C2 , Q) x RS1 = I(S1 ; Ye |C2 , Q)
RC2 = I(C2 ; Y1 |Q) − I(C2 ; Ye |Q) x RC2 = I(C2 ; Ye |Q),
where R1 = RS1 and R2 = RC2 . Converse follows from Theorem 2.5 as the needed condition is satisfied by the channel.
A.6
Proof of Corollary 2.8
Achievability follows from Theorem 2.2 by only utilizing S1 and O2 together with the channel condition given in (2.15). For a given p ∈ P(S1 , O2 ), if I(S1 , O2; Y1 |Q) ≤ I(S1 , O2 ; Ye |Q), we set R1 = R2 = 0; otherwise we assign the following rates. RS1 = I(S1 , O2 ; Y1 |Q) − I(S1 , O2; Ye |Q) x RS1 = I(S1 , O2 ; Ye |Q) − I(O2 ; Y1|S1 , Q) x RO2 = I(O2 ; Y1 |S1 , Q),
where R1 = RS1 and R2 = 0. Converse follows from Theorem 2.5 as the needed condition is satisfied by the channel.
A.7
Proof of Corollary 2.9
Achievability follows from Theorem 2.2 by only utilizing S1 and O2 together with the channel condition given in (2.16). For a given p ∈ P(S1 , O2 ), if I(S1 , O2; Y1 |Q) ≤ 140
I(S1 , O2 ; Ye |Q), we set R1 = R2 = 0; otherwise we assign the following rates. RS1 = I(S1 , O2 ; Y1 |Q) − I(S1 , O2; Ye |Q) x RS1 = I(S1 ; Ye |Q) x RO2 = I(O2 ; Ye |S1 , Q),
where R1 = RS1 and R2 = 0. Converse follows from Theorem 2.5 as the needed condition is satisfied by the channel.
A.8
Proof of Corollary 2.11
For a MAC-E given by p(y1 , ye |x1 , x2 ), we consider an interference channel with an eavesdropper (IC-E) defined by p(y1 , y2 , ye |x1 , x2 ) = p(y1 , ye |x1 , x2 )δ(y2 − y1 ) and utilize Theorem 2.2 with p ∈ P(C1 , C2 ) satisfying (2.17). Then, the achievable region becomes x R1 = RC1 ≤ I(C1 ; Y1 |C2, Q) − RC1 x R2 = RC2 ≤ I(C2 ; Y1 |C1, Q) + RC1 − I(C1 , C2; Ye |Q),
x x x where I(C1 ; Ye |Q) ≤ RC1 ≤ I(C1 ; Ye |C2 , Q) and RC2 = I(C1 , C2 ; Ye |Q) − RC1 . Hence,
R1 + R2 = [I(C1 , C2 ; Y1 |Q) − I(C1 , C2 ; Ye |Q)]+ is achievable for any p ∈ P(C1 , C2 ) satisfying (2.17). The following outer bound on the sum rate follows by Theorem 2.5, as the constructed IC-E satisfies the needed condition of the theorem. R1 + R2 ≤ I(C1 , C2 ; Y1 |Q) − I(C1 , C2 ; Ye |Q), for any p ∈ P(C1 , C2 ). Which is what needed to be shown. 141
A.9
Proof of Corollary 2.12
We first remark that R[NF] will remain the same if we restrict the union over the set of probability distributions ˜ P(S1 , O2 , |Q| = 1) {p | p ∈ P(S1 , O2 , |Q| = 1), I(O2 ; Ye ) ≤ I(O2; Y1 )}.
As for any p ∈ P(S1 , O2 , |Q| = 1) satisfying I(O2 ; Ye ) ≥ I(O2 ; Y1), R1 (p) = [I(S1 ; Y1 |O2 ) − I(S1 ; Ye |O2 )]+ since I(O2 ; Y1) ≤ I(O2; Ye ) ≤ I(O2 ; Ye |S1 ) in this case. And the highest rate achievable with the NF scheme occurs if O2 is chosen to be deterministic, and hence I(O2 ; Y1 ) = I(O2 ; Ye ) case will result in the highest rate among the probability distributions p ∈ P(S1 , O2, |Q| = 1) satisfying I(O2; Ye ) ≥ I(O2 ; Y1 ). Therefore, without loss of generality, we can write R[NF] = max R1 (p),
˜ p∈P(S1 ,O2 ,|Q|=1)
where R1 (p) = [I(S1 ; Y1 |O2) + min{I(O2 ; Y1), I(O2 ; Ye |S1 )} − I(S1 , O2; Ye )]+ . x ˜ Now, fix some p ∈ P(S1 , O2 , |Q| = 1), and set RO2 = min{I(O2 ; Y1), I(O2 ; Ye |S1 )}, x RS1 = I(S1 , O2 ; Ye ) − min{I(O2; Y1 ), I(O2; Ye |S1 )}, and RS1 = I(S1 ; Y1 |O2)−
I(S1 , O2 ; Ye ) + min{I(O2 ; Y1), I(O2 ; Ye |S1 )}, where we set R1 = 0 if the latter is negative. Here, R1 = [I(S1 ; Y1 |O2 ) + min{I(O2 ; Y1 ), I(O2; Ye |S1 )} − I(S1 , O2 ; Ye )]+ ˜ is achievable, i.e., (R1 (p), 0) ∈ RRE for any p ∈ P(S1 , O2, |Q| = 1). Observing that (R[NF] , 0) ∈ RRE , we conclude that the noise forwarding (NF) scheme of [13] is a special case of the proposed scheme.
142
A.10
Proof of Corollary 2.13
For any given p ∈ P(S1 , O2, |Q| = 1) satisfying I(O2 ; Ye ) ≤ I(O2 ; Y1), we see that R1 = [I(S1 , O2; Y1 ) − I(S1 , O2; Ye )]+ is achievable due to (2.20) and Corollary 2.12. The converse follows by Theorem 2.5 as the needed condition is satisfied by considering an IC-E defined as p(y1 , ye |x1 , x2 )δ(y2 − y1 ), where we set |Q| = 1 in the upper bound as the time sharing random variable is not needed for this scenario, and further limit the input distributions to satisfy I(O2 ; Ye ) ≤ I(O2; Y1 ). The latter does not reduce the maximization for the upper bound due to a similar reasoning given in the Proof of Corollary 2.12.
143
APPENDIX B
Lemmas in Chapter 3
B.1
Lemma B.1
Lemma B.1. Consider receiver i ∈ K. For a given ǫ > 0 and d ∈ [0, 1], ∃ǫ∗ (i, ǫ, d) > 0 such that, if ∆K−i,i ≥ 1 − ǫ∗ (i, ǫ, d) then ∆S,i ≥ d − ǫ, ∀S ⊆ K − i. Proof. For a given i ∈ K, ǫ > 0, and level of secrecy d ∈ [0, 1], let ǫ∗ (i, ǫ, d) =
S⊆K−i H(WS ) min (1 + ǫ − d) H(WK−i ) . Then, denoting the received observation of the eavesdropper
as Yi and assuming ∆K−i,i ≥ 1 − ǫ∗ (i, ǫ, d), for any S ⊆ K − i we have H(WS |Yi) + H(WK−i |WS , Yi ) = H(WK−i |Yi ) ≥ H(WK−i ) − ǫ∗ (i, ǫ, d)H(WK−i) (B.1)
≥ H(WS ) + H(WK−i |WS ) − (1 + ǫ − d)H(WS ), where the first inequality follows from the assumption of ∆K−i,i ≥ 1 − ǫ∗ (i, ǫ, d) and the second inequality follows from the choice of ǫ∗ (i, ǫ, d) above. Continuing from above, ∆S,i = H(WS |Yi) H(WK−i |WS ) − H(WK−i |WS , Yi ) ≥ (d − ǫ) + ≥ (d − ǫ), H(WS ) H(WS )
as conditioning does not increase entropy. 144
We remark that a similar observation is used in [27]. The above proof is more complete than that of [27].
B.2
Lemma B.2
Lemma B.2. The gain matrix, resulting from the interference alignment scheme, ¯ between transmitter k and the receiver i, i.e., Hi,k Vk , has rank mk with probability ¯ one. As the dimension of Hi,k Vk is F × mk , these matrices have full rank with probability one. ¯ Proof. We have rank(Hk,k Vk ) = mk by the construction given in [85]. Now, the second observation follows by the design of interference alignment vectors, which have ¯ linearly independent columns. (If they had linearly dependent columns, then Hk,k Vk would not have mk linearly independent columns, contrary to the construction of ¯ the interference alignment matrices.) Here, rank(Hi,k Vk ) ≤ min{mk , F } = mk for ¯ i = k. We need only to show that the matrix Hi,k Vk has mk linearly independent columns. Considering any i = k, representing diagonal elements of Hi,k as {hi,k (1), hi,k (2), · · · , hi,k (F )} and denoting the rows of the interference alignment maT T T T T ¯ ¯ trix by vf , i.e., Vk = [v1 ; v2 ; · · · ; vF ]T , we have Hi,k Vk = [hi,k (1)v1 ; hi,k (2)v2 ; · · · ; T hi,k (F )vF ]T . At this point, as the channel gains are chosen according to a continu-
ous distribution, the hik (f )’s are non-zero with probability one for f ∈ {1, 2, · · · , F }. ¯ Hence, these row operations will not change the rank of a matrix, i.e., rank(Hi,k Vk ) = ¯ rank(Vk ) = mk . Therefore, the gain matrices seen by the receivers have full rank with probability one.
145
B.3
Lemma B.3
Lemma B.3. For any M, L ⊆ K satisfying M ∩ L = ∅, ˜ ¯ ˜ ¯ ˜ I(XM ; Ye |H, He ) ≤ I(XM ; Ye |XL , H, He ). Proof. ˜ ¯ ˜ ˜ ¯ I(XM; Ye |H, He) = H(XM|H, He) − H(XM|Ye , H, He) ˜ ˜ ˜ ¯ ˜ ≤ H(XM|XL , H, He) − H(XM|Ye , XL , H, He) ˜ ¯ ˜ = I(XM; Ye |XL , H, He ), where the inequality is due to the fact that conditioning does not increase entropy, ˜ ˜ ˜ and the last equality follows by H(XM|XL , H, He ) = H(XM |H, He) as M ∩ L = ∅ and messages of the users are independent. (B.2)
B.4
Lemma B.4
Lemma B.4. 1 1 ˜ ¯ ˜ ¯ ˜ E[I(XS c ; Ye |H, He )] ≤ E[I(XS ; Ye |XS c , H, He)] c| |S |S| (B.3)
Proof. Let us denote |S| = S; and define S = {s1 , · · · , sS } and S c = {sS+1 , · · · , sK }. Then we have
146
1 ˜ ¯ E[I(XS c ; Ye |H, He )] |S c |
=
1 ˜ ¯ ˜ ¯ ˜ E[I(XsS+1 ; Ye |H, He)] + E[I(XsS+2 ; Ye |XsS+1 , H, He)] + · · · K −S ˜ ¯ ˜ ˜ + E[I(XsK ; Ye |XsS+1 , · · · , XsK−1 , H, He)] 1 ˜ ¯ ˜ ˜ ¯ ˜ E[I(Xs1 ; Ye |XS c , H, He )] + E[I(Xs1 ; Ye |XS c , H, He )] + · · · K −S ˜ ¯ ˜ + E[I(Xs1 ; Ye |XS c , H, He)]
≤
=
1 ˜ ¯ ˜ (K − S)E[I(Xs1 ; Ye |XS c , H, He )] K −S 1 ˜ ¯ ˜ = SE[I(Xs1 ; Ye |XS c , H, He)] S 1 ˜ ¯ ˜ ˜ ¯ ˜ = E[I(Xs1 ; Ye |XS c , H, He )] + E[I(Xs2 ; Ye |XS c , H, He )] + · · · S ˜ ¯ ˜ + E[I(XsS ; Ye |XS c , H, He)]
≤
1 ˜ ¯ ˜ ˜ ¯ ˜ ˜ E[I(Xs1 ; Ye |XS c , H, He )] + E[I(Xs2 ; Ye |XS c , Xs1 , H, He )] + · · · S ˜ ¯ ˜ ˜ ˜ + E[I(XsS ; Ye |XS c , Xs1 , · · · , XsS−1 , H, He)]
=
1 ˜ ¯ ˜ E[I(XS ; Ye |XS c , H, He )], |S|
(B.4)
where we repeatedly use Lemma B.3 for the above inequalities and use the fact ˜ ¯ ˜ ˜ ¯ ˜ that E[I(Xk ; Ye |XL , H, He)] = E[I(Xi ; Ye |XL , H, He)] for any k = i and for any L ⊆ K − {k, i}. We note that the last property stated above is due to the symmetry between network users provided by the random choice of user ordering at each fading block.
147
B.5
Lemma B.5
1 th K
Lemma B.5. Each user can set the randomization rates to be
of the total DoF
per orthogonal time-frequency slot seen by the eavesdropper, i.e., with a rate choice of x Rk =
1 ˜ ¯ E[I(XK ; Ye |H, He)], KF
(B.5)
each randomization message (codeword index), given the secrecy message (bin index) of each user, is decodable at the eavesdropper. Proof. Let S ⊆ K. From Lemma B.4, we have 1 1 ˜ ¯ ˜ ¯ ˜ E[I(XS c ; Ye |H, He)] ≤ E[I(XS ; Ye |XS c , H, He )]. c| |S |S| We continue as below. 1 1 ˜ ¯ ˜ ¯ ˜ E[I(XS c ; Ye |H, He )] ≤ E[I(XS ; Ye |XS c , H, He)] c| |S |S| ˜ ¯ ˜ ¯ ˜ ⇔ |S|E[I(XS c ; Ye |H, He )] ≤ (K − |S|)E[I(XS ; Ye |XS c , H, He )] ⇔ |S| K − |S| ˜ ¯ ˜ ¯ ˜ E[I(XS c ; Ye |H, He )] ≤ E[I(XS ; Ye |XS c , H, He )] K K |S| ˜ ¯ ˜ ¯ ˜ ⇔ E[I(XK ; Ye |H, He )] ≤ E[I(XS ; Ye |XS c , H, He )], K
1 ˜ ¯ E[I(XK ; Ye |H, He )] KF
(B.6) (B.7) (B.8) (B.9)
x from which we readily conclude that Rk =
satisfies
x Rk = k∈S
|S| 1 ˜ ¯ ˜ ¯ ˜ E[I(XK ; Ye |H, He)] ≤ E[I(XS ; Ye |XS c , H, He)], ∀S ⊆ K, (B.10) KF F
and hence randomization messages are decodable at the eavesdropper with this rate assignment.
148
APPENDIX C
Lemmas and Proofs of the Theorems in Chapter 4
C.1
Lemmas used in Section 4.2
Lemma C.1 (Theorem 7.65, [93]). Let d, k ≥ 1. Consider random variables Yx and π π Zx taking values in {0, 1}, for x ∈ Zd . Denote Z π = {Zx : x ∈ Zd } as a family of π π independent random variables satisfying Pr{Zx = 1} = 1 − Pr{Zx = 0} = π. Also,
denote Euclidean distance in Zd as d(·, ·). If Y = {Yx : x ∈ Zd } is a k-dependent family of random variables, i.e., if any two sub-families {Yx : x ∈ A} and {Yx′ : x′ ∈ A′ } are independent whenever d(x, x′ ) > k, ∀x ∈ A, ∀x′ ∈ A′, such that Pr{Yx = 1} ≥ δ, ∀x ∈ Zd , then there exist a family of independent random variables Z π(δ) such that Y statistically dominates Z π(δ) , where π(δ) is a non-decreasing function π : [0, 1] → [0, 1] satisfying π(δ) → 1 as δ → 1. Proof. The proof is given in [105], where the authors also provide a construction of the independent model. See also [93].
149
Lemma C.2 (Theorem 5, [90]). Consider discrete edge percolation with edge existence probability p on a square grid of size m × m (number of edges). For any given κ > 0, partition the area into m (κ log m−ǫm )
rectangles of size m × (κ log m − ǫm ), where ǫm =
o(1) as m → ∞ and is chosen to have integer number of rectangles. Denote the i maximal number of edge-disjoint left to right crossings of the ith rectangle as Cm and i mini Cm . Then, ∀κ > 0 and ∀p ∈ ( 5 , 1) satisfying κ log(6(1 − p)) < −2, 6
let Nm
∃δ > 0 such that m→∞ lim Pr{Nm ≤ δ log m} = 0.
(C.1)
Proof. The proof is given in [90, Appendix I]. See also [95, Theorem 4.3.9]. Lemma C.3. Consider a Poisson random variable X of parameter λ. Then, P (X ≥ x) ≤ e−λ (eλ)x , for x > λ. xx (C.2)
Proof. The proof follows by an application of the Chernoff bound. Please refer to [90, Appendix II] or [95, Appendix]. Lemma C.4. Consider a Poisson random variable X of parameter λ. Then, for any ǫ ∈ (0, 1), λ→∞ lim P (X ≤ (1 − ǫ)λ) = 0,
(C.3)
and λ→∞ lim P (X ≤ (1 + ǫ)λ) = 1.
(C.4)
Proof. The proof follows by utilizing the Chebyshev inequality.
150
C.2
Ri > R for some constant R > 0 in (4.48) as n → ∞
E[ℜ{hi,e }] + jE[ℑ{hi,e }] n Consider that the statistics of hi,e s are given by 1) q
is a complex number with finite real and imaginary parts, and 2) s finite real number, ∀i ∈ K, e ∈ E. Let us further assume that I2 +
P N0
E[|hi,e |2 ] is a ˜ ˜ Hi,e H∗ is a i,e
i=1
positive definite matrix. Focusing on the second term of (4.48), we obtain P 1 E log det I2 + 2n N0 n ˜ ˜ Hi,e H∗ i,e i=1 (a)
≤ =
P 1 log det I2 + 2n N0
n
˜ ˜ E Hi,e H∗ i,e i=1 (b)
=
1 P P2 log 1 + 2ns + 2 n2 (s2 − |q|4) 2n N0 N0 O(log(n)) , (C.5) n
where (a) is due to Jensen’s inequality as log det(·) function is concave in positive definite matrices, and (b) follows from ˜ ˜ Hi,e H∗ = i,e which implies ˜ ˜ E Hi,e H∗ = i,e s |q|2 |q|2 s . |hi,e |2 ˜ hi,e h∗ ˜ hi,e h∗ i,e ˜ |hi,e |2 ,
i,e
Thus, the second term of (4.48) becomes insignificant, o(1) as n → ∞; and ∃R > 0 such that Ri > R, ∀i ∈ K for sufficiently large n. Note that the assumption
P that I2 + N0 n i=1
˜ ˜ Hi,e H∗ is a positive definite matrix holds in the limit of large n almost i,e
˜ ˜ surely. (Here, due to strong law of large numbers, the sum converges to nE Hi,e H∗ i,e with probability 1.)
151
C.3
Proof of Theorem 4.9
The proof follows along the same lines of the proof of Theorem 4.6 by generalizing the secrecy zone approach to multi-level zones, where the area of each zone is carefully chosen to obtain a (statistically) working bound for the SNR of the colluding eavesdropper. In Fig. C.1, we show the zones around a transmitting square: Zone of level k for k ∈ {1, · · · , L} has an area of Alk , and the associated distance is denoted with flk dc with some flk ≥ 1 and flk ≥ flk−1 . Note that, we take flk as a design parameter. We will choose flk differently, depending on whether a node is forwarding data over a highway or accessing to/accessed by a highway. Furthermore, d and flk may depend on n, i.e., expected number of users. We now provide generalization of Lemma 1 to the colluding eavesdropper case. Lemma C.5 (Secure Rate per Hop). In a communication scenario given by Fig. C.1 (no eavesdroppers in the first zone), the rate RT R = where SNRT R S(α) SNRE ∗ ft ≥ √ P (d + 1)−α c−α ( 2)−α , No + P 8(ft )−α d−α c−α S(α)
∞ i=1
1 log(1 + SNRT R ) − log(1 + SNRE ∗ ) (ft d)2
+
,
(C.6)
(C.7) (C.8)
i(i − 0.5)−α,
L
P (1 + ǫ)9c2−α d−α λe d 2 (flk )2 (flk−1 )−α , N0 k=2 2(d + 1) , d
(C.9) (C.10)
152
fl2 dc ft dc fl1 dc dc
e
c Al1 e e
Al2
Figure C.1: The second square surrounding the transmitter is the secrecy zone (zone of level 1), which is the region of points that are at most fl1 d squares away from the transmitter. The zone of level k is denoted with distance flk dc and has an area of Alk .
is w.h.p. securely and simultaneously achievable between any active transmitterreceiver pair if flk is chosen such that λe d2 (flk )2 → ∞, as n → ∞, for k = 2, 3, · · · . (C.11)
Proof. The steps of the proof are similar to that of Lemma 4.1. Here, we need to derive a working upper bound for the colluding eavesdropper SNR. In our case, secrecy is guaranteed assuming that the eavesdroppers are located on the boundary of each level of zones. We first bound the number of eavesdroppers at each level. We have Alk ≤ (2dflk + 1)2 c2 ≤ 9d2 (flk )2 c2 , 153 (C.12)
as d ≥ 1 and flk ≥ 1. Hence, the number of eavesdroppers in layer lk can be bounded, using the Chebyshev’s inequality (see Lemma C.4), by |El∗ | ≤ (1 + ǫ)λe 9c2 d2 (flk )2 k w.h.p., for a given ǫ > 0, as long as we choose flk to satisfy λe d2 (flk )2 → ∞, as n → ∞. Now, we place |El∗ | number of eavesdroppers from layer k at distance flk−1 dc for k k = 2, 3, · · · . This is referred to as configuration E ∗ . These colluding eavesdroppers can do maximal ratio combining (this gives the best possible SNR for them) to achieve the following SNR. (C.13)
L
P SNRE ∗ = k=2 |El∗ |(flk−1 )−α c−α d−α k N0
L
P (1 + ǫ)9c2−α d−α ≤ λe d 2 N0 SNRE ∗ .
(flk )2 (flk−1 )−α k=2 (C.14)
Note that the challenge here is to choose flk such that SNRE ∗ < ∞, and at the same time to satisfy (C.11). With some appropriate choices of these parameters, we generalize Lemma 4.4 and Lemma 4.5 to the colluding eavesdropper case. Lemma C.6 (Rate per Node on the Highways). If λe = O((log n)−2 ), each node on the constructed highways can transmit to their next hop at a constant secure rate. √ Furthermore, if the number of nodes each highway serves is O( n), each highway can w.h.p. carry a per-node throughput of Ω
1 √ n
.
154
Proof. We show the result for λe = Θ ((log n)−2 ), which will imply the desired result (as lowering the eavesdropper density can not degrade the performance). Consequently, there exists constants Λ, Λ, and n1 such that Λ(log n)−2 ≤ λe ≤ Λ(log n)−2 , for n ≥ n1 , where Λ < Λ. We choose each level of zones over the highways by setting flk = Here, λe (2fl1 d + 1)2 c2 ≤ λe 9(fl1 )2 d2 c2 = λe δ(log n)2 Λ (C.17) (C.18) (C.19) δ 9Λc2 d2
1 2
(C.15)
(log n)( 2 )
α k−1
.
(C.16)
≤ δ, for n ≥ n1 .
Therefore, due to our percolation result, i.e., Lemma 3, each member of a given highway does not have any eavesdropper within their first level secrecy zone as δ can be chosen arbitrarily small. Now, as the above choice also satisfies λe d2 (flk )2 → ∞, as n → ∞, for k = 2, 3, · · · , we can utilize Lemma 1 to achieve a secrecy rate of RT R = 1 1 1 log(1 + SNRT R ) − log(1 + SNRE ∗ ) . (ft d)2 2 2 (C.20)
Now, we provide an upper bound for SNRE ∗ . First, note that our setup results in (flk ) (flk−1 )
2 −α
= 155
δ 9Λc2 d2
2−α 2
.
Hence,
SNRE ∗
= ≤
P (1 + ǫ)9 λe (L − 1) N0
δ 9Λ
2−α 2
(C.21) δ 9Λ
2−α 2
P (1 + ǫ)9 Λ(log n)−2 (L − 1) N0 for n ≥ n1
, (C.22) (C.23)
→ 0, as n → ∞,
where the last step is due to the observation that the number of levels can be upper bounded by L−1 ≤ log(log n) . log( α ) 2 (C.24)
Therefore, there exists n2 such that for all n ≥ n2 , the rate expression satisfies RT R ≥ R for some constant R. The second claim follows from Lemma 3.
Lemma C.7 (Access Rate to Highways). Almost all source (destination) nodes can w.h.p. simultaneously transmit (receive) their messages to (from) highways with a secure rate of Ω ((log n)−3−α ), if λe = O (log n)−(2+ρ) for any ρ > 0. Proof. We show the result for λe = Θ (log n)−(2+ρ) , which will imply the desired result (as lowering the eavesdropper density can not degrade the performance). Consequently, there exists constants Λ, Λ, and n3 such that Λ(log n)−(2+ρ) ≤ λe ≤ Λ(log n)−(2+ρ) , for n ≥ n3 , where Λ < Λ. (C.25)
156
At this point, we can upper bound the fraction of nodes that can not access to a highway due to an existence of an eavesdropper in their first secrecy zone. Following the analysis in Lemma 4.5, as long as we satisfy λe (fl1 )2 d2 → 0, as n → ∞, (C.26)
almost all the nodes can access to the highways. To compute the achievable secrecy rate with Lemma 1, we need to satisfy λe (flk )2 d2 → ∞, as n → ∞, for k = 2, 3, · · · . Further, we can show that as long as we satisfy
L
(C.27)
λe d 2 k=2 (flk )2 (flk−1 )−α ≤ C, as n → ∞,
(C.28)
for some constant C, the achievable rate RT R in Lemma C.5 scales like Ω ((log n)−2−α ) as d = κ′′ log n. Due to time-division among the legitimate nodes accessing the highways (there are w.h.p. O(log n) nodes within small squares), the secrecy rate per user satisfies Ω ((log n)−3−α ). Here, to satisfy (C.26), (C.27), (C.28) with d = κ′′ log n, we choose the secrecy zones as flk = (log n)r( 2 ) with some r satisfying ρ α α k−1
,
(C.29)
< r < ρ. 2
Note that, Lemma 4.2 that the per hop security implies the multi-hop security also holds for the colluding eavesdropper scenario. That is, the security obtained for configuration E ∗ for each hop is sufficient to ensure secrecy against colluding 157
eavesdroppers listening all the hops. Combining these results with the percolation result given in Lemma 4.3 concludes the proof.
158
APPENDIX D
Additional Polar Coding Results and the Proof of Corollary 5.8
D.1 D.1.1
Additional Polar Coding Results Polarization for an arbitrary DMC
Recently, the channel polarization result of [110] has extended to arbitrary discrete memoryless channels in [122]. These extended result shows polar codes achieving the symmetric capacity of the q-ary DMC W given by W (y|x) 1 I(W ) W (y|x) logq , 1 q W (y|x′ ) q x∈X y∈Y x′ ∈X
(D.1)
where |X | = q.
D.1.2
Polar codes with non-uniform input distributions
The following method, given in [125], is used in [117] and [122] to construct polar codes with non-uniform input distributions. Let X and X ′ be two finite sets with |X ′ | = m. Then, any distribution p(x) for x ∈ X for which mp(x) is an integer ∀x can be implemented by a uniform distribution on X ′ and a deterministic map f : X ′ → X . Using this map, we define the augmented channel W ′ (y|x′) = W (y|f (x′)). Then, 159
the symmetric capacity of W ′ , I(W ′ ), is equal to I(X; Y ) with input distribution p(x). This technique can be used to approach the true capacity of any DMC by approximating the capacity achieving input distribution by a rational p(x) and using the above channel augmentation technique ( [122]).
D.2
Proof of Corollary 5.8
We define W1m , W1e , W2m , and W2e as given in the theorem. For a given sufficiently large N and β ∈ (0, 1 ), let 2 A1m = and A1e = i ∈ {1, · · · , N} : Z(W1e N ) ≤
(i)
i ∈ {1, · · · , N} : Z(W1m N ) ≤
(i)
1 −N β 2 N
,
1 −N β 2 N
.
Now, consider a polar code C1m
C(N, F1m , u1F1m ) for the channel W1m with some
u1F1m , where F1m = Ac . Due to Lemma 5.4, we have A1e ⊆ A1m and hence 1m F1m ⊆ F1e . Now, for any given length |F1e | − |F1m | vector v1m and u1 F1m , we define ¯ v v v ¯ the vector u1F1e (¯1m ) with u1F1m (¯1m ) = u1F1m and u1F1e \F1m (¯1m ) = v1m . Then, the code C1e (¯1m ) v C(N, F1e , u1F1e (¯1m )) will be a symmetric capacity achieving polar v
code for the channel W1e averaged over the ensemble. We similarly define A2m , A2e , C2m , and C2e for channels W2m and W2e by replacing the subscript 1 with 2 everywhere above. Encoding: A code is chosen uniformly from the ensemble by choosing u1F1m i.i.d. according to uniform distribution. User 1 maps the secrecy message to be transmitted to v1m and generate a random vector v1r , according to uniform distribution over X1 , of ¯ ¯ length |A1e |. Then, the channel input is constructed with x1 N = u1 N BN F ⊗n , where 1 1 u1F1m is the frozen vector of the polar code C1m , u1F1e \F1m = v1m , and u1A1e = v1r . ¯ ¯ 160
User 2 maps the secrecy message to be transmitted to v2m and generate a random ¯ vector v2r , according to uniform distribution over X2 , of length |A2e |. Then, the ¯ channel input is constructed with x2 N = u2 N BN F ⊗n , where the vector u2 N is designed 1 1 1 for channels W2m and W2e along the similar lines given above. ¯ ¯ Decoding: The main receiver, having u1F1m , decodes both V1m and V1r over the channel W1m (considering the other user’s input, x2 , as noise) with the SC decoder for polar codes with error probability Pe = O(2−N ) (averaged over the ensemble) achieving a rate R1 =
|¯1m | v N β = I(W1m ) − I(W1e ) for sufficiently large N.
¯ ¯ After having x1 N , it can decode both V2m and V2r over the channel W2m (given the 1 knowledge of u2F2m ) with the SC decoder for polar codes with error probability Pe = O(2−N ) (averaged over the ensemble) achieving a rate R2 = for sufficiently large N. Security: Employing the SC decoding, the eavesdropper can decode the random β ¯ vector V1r over the channel W1e with error probability Pe = O(2−N ) (averaged over β
v |¯2m | N
= I(W2m ) −I(W2e )
¯ V1m and U1F1e ). Utilizing the Fano’s inequality, similar to the proof of Theorem 5.5, we therefore have ¯ ¯ H(V1r |V1m , U1F1m , Ye N ) ≤ Nǫ1 (N), 1 where ǫ1 (N) → 0 as N → ∞. In addition, given the knowledge of x1 N (say by an oracle), the eavesdropper can 1 β ¯ decode V2r over the channel W2e with error probability Pe = O(2−N ) (averaged over
(D.2)
¯ V2m and U2F2e ). Utilizing the Fano’s inequality, we therefore have ¯ ¯ H(V2r |V2m , U2F2m , x1 N , Ye N ) ≤ Nǫ2 (N), 1 1 where ǫ2 (N) → 0 as N → ∞. 161 (D.3)
Combining the two above, we have ¯ ¯ ¯ ¯ H(V1r , V2r |V1m , V2m , U1 F1m , U2 F2m , Ye N ) 1
(a)
¯ ¯ ≤ H(V1r |V1m , U1F1m , Ye N ) 1 ¯ ¯ ¯ ¯ +H(V2r |V1m , V2m , U1F1m , U2F2m , V1r , Ye N ) 1
(b)
¯ ¯ = H(V1r |V1m , U1 F1m , Ye N ) 1 +
×N x1 N ∈X1 1
N ¯ ¯ H(V2r |V2m , U2F2m , X1 1 = x1 N , Ye N ) 1 1
(c)
≤ Nǫ(N),
(D.4)
where (a) is due to the fact that conditioning does not increase entropy and (b) is due
N ¯ ¯ ¯ ¯ to the fact that X1 1 is determined by V1m , V1r , and U1F1m ; and {V1m , V1r , U1F1m } →
X1 N → Ye N form a Markov chain; (c) follows from (D.2) and (D.3) with some ǫ(N) → 1 1 0 as N → ∞. Then, the mutual information leakage to the eavesdropper averaged over the ensemble of codes can be bounded as follows. ¯ ¯ I(M1 , M2 ; Ye N |U1F1m , U2F2m ) = I(V1m , V2m ; Ye N |U1F1m , U2F2m ) 1 1 ¯ ¯ ¯ ¯ = I(V1m , V2m , V1r , V2r ; Ye N |U1F1m , U2F2m ) 1 ¯ ¯ ¯ ¯ −I(V1r , V2r ; Ye N |V1m , V2m , U1 F1m , U2 F2m ) 1
N ¯ ¯ ≤ I(X1 N , X2 N ; Ye 1 ) − H(V1r , V2r ) 1 1
(D.5)
¯ ¯ ¯ ¯ +H(V1r , V2r |V1m , V2m , U1F1m , U2F2m , Ye N ) 1
(a)
≤ N {I(W1e ) + I(W2e )} − |A1e | − |A2e | + Nǫ(N),
N i=1
where in (a) we have I(X1 N , X2 N ; Ye N ) = 1 1 1
I(X1 N , X2 N ; Yei |Ye i−1 ) ≤ NI(X1 , X2 ; Ye ) 1 1 1
due to the fact that conditioning does not increase entropy; with uniformly distributed 162
channel inputs. As |A1e | + |A2e | = I(W1e ) + I(W2e ), N →∞ N lim (D.6)
due to the code construction, and ǫ(N) → 0 as N → ∞ from (D.4), we obtain that 1 N I(M1 , M2 ; Ye 1 |U1F1m , U2F2m ) ≤ ǫ N for any given ǫ > 0 for sufficiently large N. Therefore, after an expurgation argument, we say that there exist a code at each user satisfying both the reliability and secrecy constraints; and achieving the reported rates given in the theorem. (D.7)
163
BIBLIOGRAPHY
[1] O. Goldreich, Foundations of Cryptography: Volume II, Basic Applications. Cambridge University Press, 2004. [2] H. Delfs and H. Knebl, Introduction to Cryptography: Principles and Applications, 2nd ed. Springer, 2007. [3] G. S. Vernam, “Cipher printing telegraph systems for secret wire and radio telegraphic communications,” J. Amer. Inst. Elect. Eng., vol. 55, pp. 109–115, 1926. [4] X. Wang, D. Feng, X. Lai, and H. Yu, “Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD,” The 24rd Annual International Cryptology Conference (CRYPTO 2004), 2004. [5] FIPS 180-2: Secure hash signature standard. Federal Information Processing Standards Publication 180-2, U.S. Department of Commerce, National Institute of Standards and Technology (NIST), 2002. [6] NIST’s Policy on Hash Functions. National Institute on Standards and Technology (NIST), Computer Security Resource Center. [Online]. Available: http://csrc.nist.gov/groups/ST/hash/policy.html
164
[7] C. E. Shannon, “Communication theory of secrecy systems,” The Bell System Technical Journal, vol. 28, pp. 656–715, 1949. [8] A. Wyner, “The wire-tap channel,” The Bell System Technical Journal, vol. 54, no. 8, pp. 1355–1387, Oct. 1975. [9] I. Csisz´r and J. K¨rner, “Broadcast channels with confidential messages,” a o IEEE Trans. Inf. Theory, vol. 24, no. 3, pp. 339–348, May 1978. [10] S. Leung-Yan-Cheong and M. Hellman, “The Gaussian wire-tap channel,” IEEE Trans. Inf. Theory, vol. 24, no. 4, pp. 451–456, Jul. 1978. [11] U. Maurer and S. Wolf, “Information-theoretic key agreement: From weak to strong secrecy for free,” in Advances in Cryptology - EUROCRYPT 2000, Lecture Notes in Computer Science 1807, Springer, 2000, pp. 351–368. [12] Y. Oohama, “Coding for relay channels with confidential messages,” in Proc. 2001 IEEE Information Theory Workshop (ITW’01), Cairns, Australia, Sep. 2001, pp. 87–89. [13] L. Lai and H. El Gamal, “The relay-eavesdropper channel: Cooperation for secrecy,” IEEE Trans. Inf. Theory, vol. 54, no. 9, pp. 4005–4019, Sep. 2008. [14] E. Ekrem and S. Ulukus, “Secrecy in cooperative relay broadcast channels,” IEEE Trans. Inf. Theory, submitted for publication. [15] ——, “Secrecy in cooperative relay broadcast channels,” in Proc. 2008 IEEE International Symposium on Information Theory (ISIT’08), Toronto, ON, Jul. 2008. 165
[16] M. Yuksel and E. Erkip, “The relay channel with a wiretapper,” in Proc. 41st Annual Conference on Information Sciences and Systems (CISS’07), Baltimore, MD, Mar. 2007. [17] V. Aggarwal, L. Sankar, A. R. Calderbank, and H. V. Poor, “Secrecy capacity of a class of orthogonal relay eavesdropper channels,” EURASIP Journal on Wireless Communications and Networking, 2009. [18] X. He and A. Yener, “Two-hop secure communication using an untrusted relay,” EURASIP Journal on Wireless Communications and Networking, 2009. [19] N. Milosavljevic, M. Gastpar, and K. Ramchandran, “Secure communication using an untrusted relay via sources and channels,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009. [20] M. Yuksel, X. Liu, and E. Erkip, “A secure communication game with a relay helping the eavesdropper,” in Proc. 2009 IEEE Information Theory Workshop (ITW 2009), Taormina, Sicily, Italy, Oct. 2009. [21] L. Lai, H. El Gamal, and H. V. Poor, “The wiretap channel with feedback: Encryption over the channel,” IEEE Trans. Inf. Theory, vol. 54, no. 11, pp. 5059–5067, Nov. 2008. [22] X. Tang, R. Liu, P. Spasojevic, and H. V. Poor, “Multiple access channels with generalized feedback and confidential messages,” in Proc. 2007 IEEE Information Theory Workshop (ITW’07), Sep. 2007.
166
[23] E. Ekrem and S. Ulukus, “Effects of cooperation on the secrecy of multiple access channels with generalized feedback,” in Proc. 42nd Annual Conference on Information Sciences and Systems (CISS 2008), Mar. 2008. [24] D. Gunduz, D. R. Brown, and H. V. Poor, “Secret communication with feedback,” in Proc. 2008 IEEE International Symposium on Information Theory and its Applications (ISITA 2008), Auckland, New Zealand, Dec. 2008. [25] E. Ardestanizadeh, M. Franceschetti, T. Javidi, and Y.-H. Kim, “Wiretap channel with secure rate-limited feedback,” IEEE Trans. Inf. Theory, vol. 55, no. 12, pp. 5353–5361, Dec. 2009. [26] X. He and A. Yener, “The role of feedback in two-way secure communications,” IEEE Trans. Inf. Theory, submitted for publication. [27] E. Tekin and A. Yener, “The general Gaussian multiple-access and two-way wiretap channels: Achievable rates and cooperative jamming,” IEEE Trans. Inf. Theory, vol. 54, no. 6, pp. 2735–2751, Jun. 2008. [28] A. El Gamal, M. Youssef, and H. El Gamal, “Randomization for security in half-duplex two-way Gaussian channel,” in Proc. 2009 IEEE Global Telecommunications Conference (GLOBECOM 2009), Dec. 2009. [29] A. El Gamal, O. O. Koyluoglu, M. Youssef, and H. El Gamal, “New achievable secrecy rate regions for the two way wiretap channel,” in Proc. 2010 IEEE Information Theory Workshop (ITW 2010), Cairo, Egypt, Jan. 2010.
167
[30] E. Tekin, S. Serbetli, and A. Yener, “On secure signaling for the Gaussian multiple access wire-tap channel,” in Proc. 39th Asilomar Conference on Signals, Systems and Computers, 2005. [31] R. Liu, I. Maric, R. D. Yates, and P. Spasojevic, “The discrete memoryless multiple access channels with confidential messages,” in Proc. 2006 IEEE International Symposium on Information Theory (ISIT’06), Jul. 2006. [32] Y. Liang and H. V. Poor, “Secrecy capacity region of binary and gaussian multiple access channels,” in Proc. 44th Annual Allerton Conference on Communication, Control, and Computing, Sep. 2006. [33] E. Tekin and A. Yener, “Secrecy sum-rates for the multiple-access wire-tap channel with ergodic block fading,” in Proc. 45th Annual Allerton Conference on Communication, Control, and Computing, Sep. 2007. [34] Y. Liang and H. V. Poor, “Multiple-access channels with confidential messages,” IEEE Trans. Inf. Theory, vol. 54, no. 3, pp. 976–1002, Mar. 2008. [35] E. Tekin and A. Yener, “The gaussian multiple access wire-tap channel,” IEEE Trans. Inf. Theory, vol. 54, no. 12, pp. 5747–5755, Dec. 2008. [36] E. Ekrem and S. Ulukus, “On the secrecy of multiple access wiretap channel,” in Proc. 46th Annual Allerton Conference on Communications, Control, and Computing, Sep. 2008. [37] O. Simeone and A. Yener, “The cognitive multiple access wire-tap channel,” in 43rd Annual Conference on Information Sciences and Systems (CISS 2009), Mar. 2009. 168
[38] A. Khisti, A. Tchamkerten, and G. W. Wornell, “Secure broadcasting with multiuser diversity,” in Proc. Annual Allerton Conference on Communication, Control, and Computing, Sep. 2006. [39] R. Liu, I. Maric, P. Spasojevic, and R. D. Yates, “Discrete memoryless interference and broadcast channels with confidential messages,” in Proc. 44th Annual Allerton Conference on Communication, Control, and Computing, Sep. 2006. [40] R. Liu and H. V. Poor, “Multiple antenna secure broadcast over wireless networks,” in Proc. of the First International Workshop on Information Theory for Sensor Networks, Santa Fe, NM, June 18 - 20 2007. [41] Y. Liang, H. V. Poor, and S. Shamai (Shitz), “Secrecy capacity region of fading broadcast channels,” in Proc. 2007 IEEE International Symposium on Information Theory (ISIT’07), Jun. 2007. [42] A. Khisti, A. Tchamkerten, and G. W. Wornell, “Secure broadcasting over fading channels,” IEEE Trans. Inf. Theory, vol. 54, no. 6, pp. 2453–2469, Jun. 2008. [43] R. Liu, I. Maric, P. Spasojevic, and R. D. Yates, “Discrete memoryless interference and broadcast channels with confidential messages: Secrecy rate regions,” IEEE Trans. Inf. Theory, vol. 54, no. 6, pp. 2493–2507, Jun. 2008. [44] Y. Liang, H. V. Poor, and L. Ying, “Wireless broadcast networks: Reliability, security, and stability,” in Proc. 2008 Information Theory and Applications Workshop, Feb. 2008.
169
[45] E. Ekrem and S. Ulukus, “Ergodic secrecy capacity region of the fading broadcast channel,” in Proc. IEEE International Conference on Communications (ICC 2009), Dresden, Germany, Jun. 2009. [46] ——, “Secrecy capacity of a class of broadcast channels with an eavesdropper,” EURASIP Journal on Wireless Communications and Networking, 2009. [47] M. Kobayashi, Y. Liang, S. Shamai, and M. Debbah, “On the compound MIMO broadcast channels with confidential messages,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009. [48] R. Liu, T. Liu, H. V. Poor, and S. Shamai, “MIMO Gaussian broadcast channels with confidential messages,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009. [49] W. Kang and N. Liu, “The secrecy capacity of the semi-deterministic broadcast channel,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009. [50] G. Bagherikaram, A. S. Motahari, and A. K. Khandani, “The secrecy capacity region of the degraded vector Gaussian broadcast channel,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009. [51] R. Liu and H. V. Poor, “Secrecy capacity region of a multi-antenna Gaussian broadcast channel with confidential messages,” IEEE Trans. Inf. Theory, submitted for publication.
170
[52] G. Bagherikaram, A. S. Motahari, and A. K. Khandani, “Secure broadcasting: The secrecy rate region,” IEEE Trans. Inf. Theory, submitted for publication. [53] ——, “The secrecy capacity region of the Gaussian MIMO broadcast channel,” IEEE Trans. Inf. Theory, submitted for publication. [54] J. Xu, Y. Cao, and B. Chen, “Capacity bounds for broadcast channels with confidential messages,” IEEE Trans. Inf. Theory, vol. 55, no. 10, pp. 4529– 4542, Oct. 2009. [55] S. Goel and R. Negi, “Secret communication in presence of colluding eavesdroppers,” in Proc. 2005 IEEE Military Communications Conference (MILCOM 2005), Oct. 2005, pp. 1501–1506. [56] R. Negi and S. Goel, “Secret communication using artificial noise,” in Proc. 2005 IEEE 62nd Vehicular Technology Conference, (VTC-2005-Fall), Sep. 2005. [57] P. Parada and R. Blahut, “Secrecy capacity of SIMO and slow fading channels,” in Proc. 2005 IEEE International Symposium on Information Theory (ISIT’05), Sep. 2005. [58] Z.Li, W. Trappe, and R. Yates, “Secret communication via multi-antenna transmission,” in Proc. 41st Annual Conference on Information Sciences and Systems (CISS’07), Baltimore, MD, Mar. 2007. [59] A. Khisti and G. Wornell, “The MIMOME channel,” in Proc. 45th Annual Allerton Conference on Communication, Control, and Computing, Sep. 2007.
171
[60] S. Shafiee, N. Liu, and S. Ulukus, “Secrecy capacity of the 2-2-1 Gaussian MIMO wire-tap channel,” in Proc. 3rd International Symposium on Communications, Control, and Signal Processing (ISCCSP 2008), Mar. 2008. [61] M. Yuksel and E. Erkip, “Diversity-multiplexing tradeoff for the multipleantenna wire-tap channel,” in 42nd Annual Conference on Information Sciences and Systems (CISS 2008), Mar. 2008. [62] F. Oggier and B. Hassibi, “The secrecy capacity of the MIMO wiretap channel,” in Proc. 2008 IEEE International Symposium on Information Theory (ISIT’08), Toronto, ON, Jul. 2008. [63] S. Shafiee, N. Liu, and S. Ulukus, “Towards the secrecy capacity of the Gaussian MIMO wire-tap channel: The 2-2-1 channel,” IEEE Trans. Inf. Theory, vol. 55, no. 9, pp. 4033–4039, Sep. 2009. [64] T. Liu and S. Shamai (Shitz), “A note on the secrecy capacity of the multiantenna wiretap channel,” IEEE Trans. Inf. Theory, vol. 55, no. 6, pp. 2547– 2553, Jun. 2009. [65] Y. Liang, H. V. Poor, and S. Shamai (Shitz), “Secure communication over fading channels,” IEEE Trans. Inf. Theory, vol. 54, no. 6, pp. 2470–2492, Jun. 2008. [66] P. K. Gopala, L. Lai, and H. El Gamal, “On the secrecy capacity of fading channels,” IEEE Trans. Inf. Theory, vol. 54, no. 10, pp. 4687–4698, Oct. 2008.
172
[67] K. Khalil, M. Youssef, O. O. Koyluoglu, and H. El Gamal, “On the delay limited secrecy capacity of fading channels,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009. [68] G. T. Amariucai and S. Wei, “Active eavesdropping in fast fading channels: A block-markov Wyner secrecy encoding scheme,” in Proc. 2010 IEEE International Symposium on Information Theory (ISIT 2010), Austin, TX, Jun. 2010. [69] X. Tang, R. Liu, P. Spasojevic, and H. V. Poor, “On the throughput of secure Hybrid-ARQ protocols for Gaussian block-fading channels,” IEEE Trans. Inf. Theory, vol. 55, no. 4, pp. 1575–1591, Apr. 2009. [70] K. Khalil, O. O. Koyluoglu, H. El Gamal, and M. Youssef, “On the delay limited secrecy capacity of fading channels,” IEEE Trans. Inf. Theory, Jul. 2009, submitted for publication. [71] D. Tse and P. Viswanath, Fundamentals of Wireless Communications. bridge University Press, 2005. [72] L. Zheng and D. N. C. Tse, “Diversity and multiplexing: a fundamental tradeoff in multiple-antenna channels,” IEEE Trans. Inf. Theory, vol. 49, no. 5, pp. 1073–1096, May 2003. [73] T. S. Han and K. Kobayashi, “A new achievable rate region for the interference channel,” IEEE Trans. Inf. Theory, vol. 27, no. 1, pp. 49–60, Jan. 1981. [74] H. F. Chong, M. Motani, H. K. Garg, and H. El Gamal, “On the HanKobayashi region for the interference channel,” IEEE Trans. Inf. Theory, vol. 54, no. 7, pp. 3188–3195, Jul. 2008. 173 Cam-
[75] H. Sato, “The capacity of the Gaussian interference channel under strong interference,” IEEE Trans. Inf. Theory, vol. 27, no. 6, pp. 786–788, Nov. 1981. [76] M. H. Costa and A. El Gamal, “The capacity region of the discrete memoryless interference channel with strong interference,” IEEE Trans. Inf. Theory, vol. 33, no. 5, pp. 710–711, Sep. 1987. [77] X. Shang, G. Kramer, and B. Chen, “A new outer bound and the noisyinterference sum-rate capacity for Gaussian interference channels,” IEEE Trans. Inf. Theory, vol. 55, no. 2, pp. 689–699, Feb. 2009. [78] V. S. Annapureddy and V. V. Veeravalli, “Gaussian interference networks: Sum capacity in the low interference regime and new outer bounds on the capacity region,” IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3032–3050, Jul. 2009. [79] A. S. Motahari and A. K. Khandani, “Capacity bounds for the gaussian interference channel,” IEEE Trans. Inf. Theory, vol. 55, no. 2, pp. 620–643, Feb. 2009. [80] Y. Liang, A. Somekh-Baruch, H. V. Poor, S. Shamai, and S. Verdu, “Cognitive interference channels with confidential messages,” in Proceedings of the 45th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, Sep. 2007. [81] D. Slepian and J. K. Wolf, “Noiseless coding of correlated information sources,” IEEE Trans. Inf. Theory, vol. 19, pp. 471–480, Jul. 1973. [82] T. Cover and J. Thomas, Elements of Information Theory. Sons, Inc., 1991. 174 John Wiley and
[83] I. Sason, “On the achievable rate regions for the gaussian interference channel,” IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1345–1356, Jun. 2004. [84] A. Carleial, “Interference channels,” IEEE Trans. Inf. Theory, vol. 24, no. 1, pp. 60–70, Jan. 1978. [85] V. R. Cadambe and S. A. Jafar, “Interference alignment and degrees of freedom for the K-user interference channel,” IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3425–3441, Aug. 2008. [86] M. A. Maddah-Ali, A. S. Motahari, and A. K. Khandani, “Communication over MIMO X channels: Interference alignment, decomposition, and performance analysis,” IEEE Trans. Inf. Theory, vol. 54, no. 8, pp. 3457–3470, Aug. 2008. [87] Y. Liang, A. Somekh-Baruch, H. V. Poor, S. Shamai, and S. Verdu, “Capacity of cognitive interference channels with and without secrecy,” IEEE Trans. Inf. Theory, vol. 55, no. 2, pp. 604–619, Feb. 2009. [88] S. Leung-Yan-Cheong, “On a special class of wiretap channels,” IEEE Trans. Inf. Theory, vol. 23, no. 5, pp. 625–627, Sep. 1977. [89] P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388–404, Mar. 2000. [90] M. Franceschetti, O. Dousse, D. N. C. Tse, and P. Thiran, “Closing the gap in the capacity of wireless networks via percolation theory,” IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1009–1018, Mar. 2007.
175
[91] S. R. Broadbent and J. M. Hammersley, “Percolation processes. i. crytals and mazes,” Proceedings of the Cambridge Philosophical Society, vol. 53, no. 3, pp. 629–641, 1957. [92] H. Kesten, Percolation theory for mathematicians. Birkhauser, Boston, 1982. [93] G. Grimmett, Percolation, 2nd ed. Springer, 1999. [94] B. Bollob´s and O. Riordan, Percolation. Cambridge University Press, 2006. a [95] M. Franceschetti and R. Meester, Random Networks for Communication: From Statistical Physics to Information Systems. Cambridge University Press, 2007. [96] B. Nazer, S. A. Jafar, M. Gastpar, and S. Vishwanath, “Ergodic interference alignment,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009. [97] U. Niesen, “Interference alignment in dense wireless networks,” IEEE Trans. Inf. Theory, 2009, submitted for publication. ¨ u [98] A. Ozg¨ r, O. L´vˆque, and D. N. C. Tse, “Hierarchical cooperation achieves e e optimal capacity scaling in ad hoc networks,” IEEE Trans. Inf. Theory, vol. 53, no. 10, pp. 3549–3572, Oct. 2007. [99] U. Niesen, P. Gupta, and D. Shah, “On capacity scaling in arbitrary wireless networks,” IEEE Trans. Inf. Theory, vol. 55, no. 9, pp. 3959–3982, Sep. 2009. [100] J. Ghaderi, L.-L. Xie, and X. Shen, “Hierarchical cooperation in ad hoc networks: Optimal clustering and achievable throughput,” IEEE Trans. Inf. Theory, vol. 55, no. 8, pp. 3425–3436, Aug. 2009. 176
[101] V. Bhandari and N. H. Vaidya, “Secure capacity of multi-hop wireless networks with random key pre-distribution,” in Proc. 2008 IEEE INFOCOM Workshops, Apr. 2008. [102] M. Haenggi, “The secrecy graph and some of its properties,” in Proc. 2008 IEEE International Symposium on Information Theory (ISIT 2008), Toronto, ON, Jul. 2008, pp. 539–543. [103] P. C. Pinto, J. Barros, and M. Z. Win, “Physical-layer security in stochastic wireless networks,” in Proc. 11th IEEE Singapore International Conference on Communication Systems (ICCS 2008), Nov. 2008, pp. 974–979. [104] ——, “Wireless physical-layer security: The case of colluding eavesdroppers,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009, pp. 2442–2446. [105] T. M. Liggett, R. H. Schonmann, and A. M. Stacey, “Domination by product measures,” Annals of Probability, vol. 25, no. 1, pp. 71–95, 1997. [106] O. O. Koyluoglu, H. El Gamal, L. Lai, and H. V. Poor, “Interference alignment for secrecy,” IEEE Trans. Inf. Theory, to appear. [107] A. Thangaraj, S. Dihidar, A. R. Calderbank, S. W. McLaughlin, and J.-M. Merolla, “Applications of LDPC codes to the wiretap channel,” IEEE Trans. Inf. Theory, vol. 53, no. 8, pp. 2933–2945, Aug. 2007. [108] R. Liu, Y. Liang, H. V. Poor, and P. Spasojevic, “Secure nested codes for type II wiretap channels,” in Proc. 2007 IEEE Information Theory Workshop (ITW’07), Sep. 2007. 177
[109] E. Arıkan, “Channel polarization:
A method for constructing capacity-
achieving codes,” in Proc. 2008 IEEE International Symposium on Information Theory (ISIT 2008), Jul. 2008. [110] ——, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009. [111] H. Mahdavifar and A. Vardy, “Achieving the secrecy capacity of wiretap channels using polar codes,” in Proc. 2010 IEEE International Symposium on Information Theory (ISIT 2010), Austin, TX, Jun. 2010, also in CoRR, abs/1001.0210, Jan. 2010. [Online]. Available: http://arxiv.org/abs/1001.0210 [112] E. Hof and S. Shamai, “Secrecy-achieving polar-coding for binary-input memoryless symmetric wire-tap channels,” submitted for publication, also in CoRR, abs/1005.2759, May 2010. [Online]. Available: http://arxiv.org/abs/1005.2759 [113] O. O. Koyluoglu and H. El Gamal, “Polar coding for secure transmission and key agreement,” Technical Report, The Ohio State University, Feb. 2010, also in CoRR, abs/1003.1422, Mar. 2010. [Online]. Available:
http://hdl.handle.net/1811/44969,http://arxiv.org/abs/1003.1422 [114] E. Arıkan and E. Telatar, “On the rate of channel polarization,” in Proc. 2009 IEEE International Symposium on Information Theory (ISIT 2009), Seoul, Korea, Jun. 2009.
178
[115] E. Arıkan, “Channel combining and splitting for cutoff rate improvement,” in Proc. 2005 IEEE International Symposium on Information Theory (ISIT 2005), Sep. 2005. [116] ——, “Channel combining and splitting for cutoff rate improvement,” IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 628–639, Feb. 2006. [117] S. B. Korada, “Polar codes for channel and source coding,” Ph.D. dissertation, EPFL, Lausanne, Switzerland, 2009. [118] C. H. Bennett, G. Brassard, C. Crepeau, and U. M. Maurer, “Generalized privacy amplification,” IEEE Trans. Inf. Theory, vol. 41, no. 6, pp. 1915–1923, Nov. 1995. [119] M. Bloch, J. Barros, M. R. D. Rodrigues, and S. W. McLaughlin, “Wireless information-theoretic security,” IEEE Trans. Inf. Theory, vol. 54, no. 6, pp. 2515–2534, Jun. 2008. [120] J. L. Carter and M. N. Wegman, “Universal classes of hash functions,” J. Comput. Syst. Sci., vol. 18, no. 2, pp. 143–154, 1979. [121] K. Gomadam, V. R. Cadambe, and S. A. Jafar, “Approaching the capacity of wireless networks through distributed interference alignment,” in Proc. 2008 IEEE Global Telecommunications Conference (GLOBECOM 2008), Nov. 2008. [122] E. Sasoglu, E. Arıkan, and E. Telatar, “Polarization for arbitrary discrete memoryless channels,” in Proc. 2009 IEEE Information Theory Workshop (ITW 2009), Taormina, Sicily, Italy, Oct. 2009.
179
[123] A. J. Grant, B. Rimoldi, R. L. Urbanke, and P. A. Whiting, “Rate-splitting multiple access for discrete memoryless channels,” IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 873–890, Mar. 2001. [124] E. Sasoglu, E. Telatar, and E. Yeh, “Polar codes for the two-user binary-input multiple-access channel,” in Proc. 2010 IEEE Information Theory Workshop (ITW 2010), Cairo, Egypt, Jan. 2010. [125] R. G. Gallager, Information Theory and Reliable Communication. John Wiley & Sons, Inc., 1968.
