Percolation and Connectivity in the Intrinsically Secure Communications Graph
Preprint
Abstract
The ability to exchange secret information is critical to many commercial, governmental, and military networks. The intrinsically secure communications graph (iS-graph) is a random graph which describes the connections that can be securely established over a large-scale network, by exploiting the physical properties of the wireless medium. This paper aims to characterize the global properties of the iS-graph in terms of: (i) percolation on the infinite plane, and (ii) full connectivity on a finite region. First, for the Poisson iS-graph defined on the infinite plane, the existence of a phase transition is proven, whereby an unbounded component of connected nodes suddenly arises as the density of legitimate nodes is increased. This shows that long-range secure communication is still possible in the presence of eavesdroppers. Second, full connectivity on a finite region of the Poisson iS-graph is considered. The exact asymptotic behavior of full connectivity in the limit of a large density of legitimate nodes is characterized. Then, simple, explicit expressions are derived in order to closely approximate the probability of full connectivity for a finite density of legitimate nodes. The results help clarify how the presence of eavesdroppers can compromise long-range secure communication.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Stochastic geometry and random graphs for the analysis and design of wireless networksIEEE Journal on Selected Areas in Communications, 2009
- Applications of LDPC Codes to the Wiretap ChannelIEEE Transactions on Information Theory, 2007
- Secret Key Agreement from Correlated Source Outputs Using Low Density Parity Check MatricesIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2006
- Connectivity of Wireless Multihop Networks in a Shadow Fading EnvironmentWireless Networks, 2005
- The Number of Neighbors Needed for Connectivity of Wireless NetworksWireless Networks, 2004
- Unconditionally secure key agreement and the intrinsic conditional informationIEEE Transactions on Information Theory, 1999
- Critical Power for Asymptotic Connectivity in Wireless Networks1999
- Common randomness in information theory and cryptography. I. Secret sharingIEEE Transactions on Information Theory, 1993
- Secret key agreement by public discussion from common informationIEEE Transactions on Information Theory, 1993
- Broadcast channels with confidential messagesIEEE Transactions on Information Theory, 1978