Medium access control and in particular resource allocation is one of the most important tasks when designing wireless communication systems as it determines the overall performance of a system. For the particular allocation of the available resources it is of crucial importance to know whether or not a channel supports a certain quality-of-service (QoS) requirement. This paper develops a decision framework based on Turing machines and studies the algorithmic decidability of whether or not a QoS requirement is met. Turing machines have no limitations on computational complexity, computing capacity, and storage. They can simulate any given algorithm and therewith characterize the fundamental performance limits for today’s digital computers. In this paper, secure communication and identification systems are considered both under channel uncertainty and adversarial attacks. While for perfect channel state information, the question is decidable since the corresponding capacity function is computable, it is shown that the corresponding questions become semidecidable in the case of channel uncertainty and adversarial attacks. This means there exist Turing machines that stop and output the correct answer if and only if a channel supports the given QoS requirement. Interestingly, the opposite question of whether a channel capacity is below a certain threshold is not semidecidable.
Medium access control and in particular resource allocation is one of the most important tasks when designing wireless communication systems as it determines the overall performance of a system. For the particular allocation of the available resources it is of crucial importance to know whether or not a channel supports a certain quality-of-service (QoS) requirement. This paper develops a decision framework based on Turing machines and studies the algorithmic decidability of whether or not a QoS requirement is met. Turing machines have no limitations on computational complexity, computing capacity, and storage. They can simulate any given algorithm and therewith characterize the fundamental performance limits for today’s digital computers. In this paper, secure communication and identification systems are considered both under channel uncertainty and adversarial attacks. While for perfect channel state information, the question is decidable since the corresponding capacity function is computable, it is shown that the corresponding questions become semidecidable in the case of channel uncertainty and adversarial attacks. This means there exist Turing machines that stop and output the correct answer if and only if a channel supports the given QoS requirement. Interestingly, the opposite question of whether a channel capacity is below a certain threshold is not semidecidable.
Modern communication systems need to satisfy pre-specified requirements on spectral efficiency and security. Physical layer security is a concept that unifies both and connects them with entropic quantities. In this paper, a framework based on Turing machines is developed to address the question of deciding whether or not a communication system meets these requirements. It is known that the class of Turing solvable problems coincides with the class of algorithmically solvable problems so that this framework provides the theoretical basis for effective verification of such performance requirements. A key issue here is to decide whether or not the performance functions, i.e., capacities, of relevant communication scenarios, particularly those with secrecy requirements and active adversaries, are Turing computable. This is a necessary condition for the corresponding communication protocols to be effectively verifiable. Within this framework, it is then shown that for certain scenarios including the wiretap channel the corresponding capacities are Turing computable. Next, a general necessary condition on the performance function for Turing computability is established. With this, it is shown that for certain scenarios, including the wiretap channel with an active jammer, the performance functions are not computable when deterministic codes are used. As a consequence, such performance functions are also not computable on all other computer architectures such as the von Neumann-architecture or the register machines.
Communication systems need to satisfy pre-specified requirements on spectral efficiency and security. Physical layer security is a concept that unifies both and connects them with entropic quantities. This paper presents a frame-work based on Turing machines to address the question of deciding whether or not a communication system meets these requirements. It is known that the class of Turing solvable problems coincides with the class of algorithmically solvable problems so that this framework allows for effective verification of such performance requirements. In this paper, it is shown that certain scenarios such as the wire-tap channel or compound channel are Turing computable so that the corresponding communication protocols can be effectively verified. A condition is presented and proved under which a communication scenario is not Turing computable. The channel with an active jammer falls into this category when deterministic codes are used. Interestingly, random codes robustify the channel with an active jammer in the sense that it becomes Turing computable and the corresponding communication protocol effectively verifiable.
In this dissertation, we present novel physical (PHY) and cross-layer design guidelines and resource adaptation algorithms to improve the security and user experience in the future wireless networks. Physical and cross-layer wireless security measures can provide stronger overall security with high efficiency and can also provide better flexibility in response to the typically time-varying wireless environment. To better utilize limited wireless resources, we present approaches and techniques based on new performance criteria for wireless system optimization by thoroughly exploiting user information including its Quality of Service (QoS) requests and channel state information (CSI) to improve network throughput and security.
In recent years, there has been a growing research interest in wireless system security from PHY layer perspective. In a wiretap channel model introduced in the seminal work by Wyner, a sender “Alice” wishes to transmit a secret message to the intended receiver “Bob” in presence of a passive eavesdropper “Eve”. Existing works have characterized maximum achievable secrecy rate or secrecy capacity for single- and multiple-antenna systems by applying Gaussian signaling and secrecy code. Despite the impracticality of Gaussian input, its compact closed-form expression of mutual information motivated the wide use of Gaussian input assumption in theoretical analysis. In contrast to the Gaussian codebook, practical wiretap codes must consist of finite-alphabet symbols. Because of this constraint, the achievable secrecy rate for a finite-alphabet input scenario would differ from the secrecy rate achievable by a Gaussian codebook. In this thesis, we quantify the effect of finite discrete-constellation on instantaneous and ergodic secrecy rate of multiple-antenna wire-tap channels. Our results demonstrate substantial performance difference between systems involving finite-alphabet inputs and systems with Gaussian inputs. In addition, we investigate the secrecy performance of multi-terminal wiretap systems when a codebook based transmission beamforming is implemented. We characterize the secrecy outage probability of a communication link under eavesdropping. We consider a limited feedback scenario where the transmitter uses a pre-defined codebook known to both the transmitter and the receiver for beamforming, and analyze the secrecy outage probability of the link when it being eavesdropped.
Next, we consider the security of wireless multi-hop networks. Certainly, network security is an overarching issue that transcends all layers of communication protocol stack. Therefore, we tackle the problem of network security by proper user scheduling, routing, and resource management. Our approach of secrecy is complementary to the traditional cryptography based techniques. Together, they can provide stronger overall security and flexibility in selecting the desired solution and can reduce bandwidth and energy overhead as much as possible. Multi-hop wireless networks frequently employ the traditional routing and resource allocation strategies. Such strategies often fail to take into account the additional need for protection against security vulnerabilities due to the wireless medium. Thus, to address security concerns, we investigate the problem of eavesdropping control by proposing security-aware power allocation strategies and routing algorithms for multi-hop networks.
The future wireless infrastructure will consists of a plethora of heterogeneous collections of applications and services. A differentiated service structure would therefore be an essential part of the future wireless infrastructure. In addition to the security consideration of wireless network, we focus on the heterogeneous structure of the network. We study the problem of cross-layer resource allocation and admission control in a multiuser heterogeneous OFDMA network providing both QoS-constrained user servicesand best-effort services. Such heterogeneous networks provide service to both High-Priority (HP) users and Best-Effort (BE) users. By clustering subcarriers, efficient algorithms for cluster and power allocation have been proposed. Our strategy maximizes the total network utility of the BE users while satisfying the QoS request for maximum number of HP users. The feasibility of the resource allocation problem depends on the number of HP users in the network. Since a large number of demanding HP users would render the resource allocation problem infeasible, a joint admission control and resource allocation scheme could be an efficient way of tackling both problems with less overhead. By incorporating admission control, we propose an efficient and optimal joint admission control and resource allocation algorithm.
This paper studies the computability of the secrecy capacity of fast-fading wiretap channels from an algorithmic perspective, examining whether it can be computed algorithmically or not. To address this question, the concept of Turing machines is used, which establishes fundamental performance limits of digital computers. It is shown that certain computable continuous fading probability distribution functions yield secrecy capacities that are non-computable numbers. Additionally, we assess the secrecy capacity's classification within the arithmetical hierarchy, revealing the absence of computable achievability and converse bounds.
Secret key generation refers to the problem of generating a common secret key without revealing any information about it to an eavesdropper. All users observe correlated components of a common source and can further use a noisy public channel for discussion, which is open to eavesdroppers. A related problem is that of secure authentication, which has structural similarities and connections to the first problem. For authentication, users need to be enrolled and securely authenticated while minimizing the privacy leakage rate. This paper studies the algorithmic computability of the forward secret key capacity and the secure authentication capacity. For the algorithmic computability, the concept of a Turing machine is used as it provides fundamental performance limits for today's digital computers. In this paper, it is shown that the forward secret key capacity with a noisy public channel is not computable and consequently, there is no algorithm that can simulate or compute the secret key capacity; even if there are no limitations on computational complexity and computing power. On the other hand, if the public channel is noiseless so that there are no rate constraints on the public communication, the secret key capacity is a computable continuous function, which is the strongest form of computability. A similar behavior is subsequently observed for the authentication problem: The secure authentication capacity under storage rate and privacy leakage rate constraints is not computable, while the case without privacy leakage rate constraints is computable.
This paper investigates secure transmission and the corresponding resource allocation policy with statistical delay Quality of Service (QoS) guarantees in the presence of an eavesdropper. Our eavesdropper can be viewed as the wireless counterpart of Wyner's wiretapper. To measure the secrecy capacity with delay QoS guarantees of such a system, we propose a concept of secure effective capacity based on the effective capacity theory. Then an optimization problem aiming at maximizing the secure effective capacity subject to a given delay QoS constraint is formulated. Lagrangian dual-based approach is used to solve this problem. Theoretical results show that the optimal power allocation depends on the delay QoS requirements and the channel states of eavesdropper. Experimental results show that the proposed policy has a superior performance in improving the system throughput over other policies, which is coherent with our theoretical analysis.