A. James Clark School of Engineering
Permanent URI for this communityhttp://hdl.handle.net/1903/1654
The collections in this community comprise faculty research works, as well as graduate theses and dissertations.
Browse
5 results
Search Results
Item Private Information Retrieval and Security in Networks(2018) Banawan, Karim; Ulukus, Sennur; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation focuses on privacy and security issues in networks from an information-theoretic perspective. Protecting privacy requires protecting the identity of the desired message from the data source. This is highly desirable in next-generation networks, where data-mining techniques are present everywhere. Ensuring security requires that the data content is not interpretable by non-authorized nodes. This is critical in wireless networks, which are inherently open. We first focus on the privacy issue by investigating the private information retrieval (PIR) problem. PIR is a canonical problem to study the privacy of the downloaded content from public databases. In PIR, a user wishes to retrieve a file from distributed databases, in such a way that no database can know the identity of the user's desired file. PIR schemes need to be designed to be more efficient than the trivial scheme of downloading all the files stored in the databases. Fundamentally, PIR lies at the intersection of computer science, information theory, coding theory, and signal processing. The classical PIR formulation makes the following assumptions: The content is exactly replicated across the databases; the user wishes to retrieve a single file privately; the databases do not collude; the databases answer the user queries truthfully; the database answers go through noiseless orthogonal channels; there are no external security threats; the answer strings have unconstrained symmetric lengths. These assumptions are too idealistic to be practical in modern systems. In this thesis, we introduce extended versions of the classical PIR problem to be relevant to modern applications, namely: PIR from coded databases, multi-message PIR, PIR from colluding and Byzantine databases, PIR under asymmetric traffic constraints, noisy PIR, and PIR from wiretap channel II. We characterize the fundamental limits of such problems from an information-theoretic perspective. This involves two parts: first, we devise a practical scheme that retrieves the desired file(s) correctly and privately; second, we mathematically prove that no other retrieval scheme can achieve any higher rate than the proposed scheme. The optimal retrieval rate is called the PIR capacity reminiscent of the capacity of communication channels. First, we consider PIR from MDS-coded databases. Due to node failures and erasures that arise naturally in any storage system, redundancy should be introduced. However, replicating the content across the databases incurs high storage cost. This motivates the content of the databases to be coded instead of merely being replicated. We investigate the PIR problem from MDS-coded databases. We determine the optimal retrieval scheme for this problem, and characterize the exact PIR capacity. The result implies a fundamental tradeoff between the retrieval cost and the storage cost. Second, we consider the multi-message PIR. In this problem, the user is interested in retrieving multiple files from the databases without revealing the identities of these messages. We show that multiple messages can be retrieved more efficiently than retrieving them one-by-one in a sequence. When the user wishes to retrieve at least half of the files stored in the databases, we characterize the exact capacity of the problem by proposing a novel scheme that downloads MDS-coded mixtures of all messages. For all other cases, we develop a near-optimal scheme which is optimal if the ratio between the total number of files and the number of desired files is an integer. Third, we consider PIR from colluding and Byzantine databases. In this problem, a subset of the databases, called Byzantine databases, can return arbitrarily corrupted answers. In addition, a subset of the databases can collude by exchanging user queries. The errors introduced by the Byzantine databases can be unintentional (if databases store outdated message set), or even worse, can be intentional (as in the case of maliciously controlled databases). We propose a Byzantine and collusion resilient retrieval scheme, and determine the exact PIR capacity for this problem. The capacity expression reveals that the effect of the Byzantine databases is equivalent to removing twice the number of Byzantine databases from the system. Fourth, we consider PIR under asymmetric traffic constraints. A common property of the schemes constructed for the existing PIR settings is that they exhibit a symmetric structure across the databases. In practice, this may be infeasible, for instance when the links from the databases have different capacities. To that end, we develop a novel upper bound for the PIR capacity that incorporates the traffic asymmetry. We propose explicit achievability schemes for specific traffic ratios. For any other traffic ratio, we employ time-sharing. Our results show that asymmetry fundamentally hurts the retrieval rate. Fifth, we consider noisy PIR, where the returned answers reach the user via noisy channel(s). This is motivated by practical applications, such as, random packet dropping, random packet corruption, and PIR over wireless networks. We consider two variations of the problem, namely: noisy PIR with orthogonal links, and PIR from multiple access channel. For noisy PIR with orthogonal links, we show that channel coding and retrieval scheme are almost separable in the sense that the noisy channel affects only the traffic ratio. For the PIR problem from multiple access channel, the output of the channel is a mixture of all the answers returned by the databases. In this case, we show explicit examples, where the channel coding and the retrieval scheme are inseparable, and the privacy may be achieved for free. Sixth, we consider PIR from wiretap channel II. In this problem, there is an external eavesdropper who wishes to learn the contents of the databases by observing portions of the traffic exchanged between the user and the databases during the PIR process. The databases must encrypt their responses such that the eavesdropper learns nothing from its observation. We design a retrieval code that satisfies the combined privacy and security constraints. We show the necessity of using asymmetric retrieval schemes which build on our work on PIR under asymmetric traffic constraints. Next, we focus on the security problem in multi-user networks by physical layer techniques. Physical layer security enables secure transmission of information without a need for encryption keys. Hence, it mitigates the problems associated with exchanging encryption keys across open wireless networks. Existing work in physical layer security makes the following assumptions: All nodes are altruistic and follow a prescribed transmission policy to maximize the secure rate of the entire system; the channel inputs to Gaussian channels are constrained by a total transmitter-side power constraint; and in secure degrees of freedom studies for interference channels, users have a single antenna each. We address these issues by investigating the MIMO interference channel with confidential messages, security in networks with user misbehavior, and MIMO wiretap channel under receiver-side power constraints. We characterize the optimal secure transmission strategies in terms of the secrecy capacity and its high-SNR approximation, the secure degrees of freedom (s.d.o.f.). First, we determine the exact s.d.o.f. region of the two-user MIMO interference channel with confidential messages (ICCM). To that end, we propose a novel achievable scheme for the 2x2 ICCM system, which is a building block for any other antenna configuration. We show that the s.d.o.f. region starts as a square region, then it takes the shape of an irregular polytope until it returns back to a square region when the number of transmit antennas is at least twice the number of receiving antennas. Second, we investigate the security problem in the presence of user misbehavior. We consider the following multi-user scenarios: Multiple access wiretap channel with deviating users who do not follow agreed-upon optimum protocols, where we quantify the effect of user deviations and propose counter-strategies for the honest users; the broadcast channel with confidential messages in the presence of combating helpers, where we show that the malicious intentions of the helpers are neutralized and the full s.d.o.f. is retained; and interference channel with confidential messages when the users are selfish and have conflicting interests, where we show that selfishness precludes secure communication and no s.d.o.f. is achieved. Third, we consider the MIMO wiretap channel with a receiver-side minimum power constraint in addition to the usual transmitter-side power constraint. This problem is motivated by energy harvesting communications with wireless energy transfer, where an added goal is to deliver a minimum amount of energy to a receiver in addition to delivering secure data to another receiver. We prove that the problem is equivalent to solving a secrecy capacity problem with a double-sided correlation matrix constraint on the channel input. We extend the channel enhancement technique to our setting. We propose two optimum schemes that achieve the optimum rate: Gaussian signaling with a fixed mean and Gaussian signaling with Gaussian artificial noise. We extend our techniques to other related multi-user settings.Item Alignment and Cooperation for Secrecy in Multi-User Channels(2011) Bassily, Raef Bahi; Ulukus, Sennur; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The study of the physical layer has offered a new perspective to the problem of communication security. This led to the development of a vast set of ideas and techniques rooted in information theory which can be employed in practice to provide unbreakable security. The information-theoretic approach relies mainly on the physical nature of the communication medium. In a wireless medium, the unique features of the wireless communication channel, such as its fading and broadcast nature, can be exploited to achieve higher secure information rates. In this dissertation, we study the secure transmission problem in wireless channels from an information-theoretic perspective. We first consider the fading multiple access wiretap channel. We give two new achievable schemes that use the time-varying (fading) nature of the channel to align the interference from different users at the eavesdropper perfectly in a one-dimensional space while creating a higher-dimensional space for the interfering signals at the legitimate receiver hence allowing for better chance of recovery. While we achieve this alignment through signal scaling at the transmitters in our first scheme (scaling based alignment), we let nature provide this alignment through the ergodicity of the channel coefficients in the second scheme (ergodic secret alignment). For each scheme, we show that the achievable secrecy rates scale logarithmically with the signal-to-noise ratio (SNR). Next, we study the security gains that can be achieved in a wireless network by employing cooperation among the nodes which is possible due to the broadcast nature of the wireless channel. We investigate the role of passive (also known as deaf) cooperation in improving the achievable secrecy rates in a Gaussian multiple relay network with an external eavesdropper. We distinguish between two modes of deaf cooperation, namely, cooperative jamming (CJ) and noise forwarding (NF). We derive the conditions in which each mode of deaf cooperation achieves secrecy rates that are higher than the secrecy capacity of the original Gaussian wiretap channel. As a result, we show that a deaf helper cannot be a useful cooperative jammer and noise forwarder at the same time. We derive the optimal power control policy for each mode. We consider the deaf helper selection problem where a fixed-size set of deaf helpers (possibly operating in different modes) are to be selected from the set of available relays so that the achievable secrecy rate is maximized. We propose a simple and efficient suboptimal strategy for selection which is shown to be optimal when only one helper is selected. Furthermore, we study the role of a multi-antenna deaf helper. Unlike the single antenna case, we show that, in general, it is useful to split the helper's power between cooperative jamming and noise forwarding. Hence, we propose a deaf cooperation strategy for this model and derive its optimal power control policy. We also show, for specific class of relay-eavesdropper channels, that a simple cooperative jamming strategy yields a secrecy rate that approaches the secrecy capacity as the helper's power is increased. Finally, we consider the role of active cooperation for secrecy in the multiple relay networks. We propose several relaying strategies for secure communication and derive the achievable secrecy rate for each strategy. In our strategies the relays decode the source signal and then forward it to the destination either in a single-hop or a multi-hop fashion. Each relay scales its transmitted signal in a way that ensures that signal components from different relays are canceled out at the eavesdropper.Item Random Codes and Graphs for Secure Communication(2009) Anthapadmanabhan, Nagaraj Prasanth; Barg, Alexander; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation considers two groups of problems related to secure communication. The first line of research is devoted to theoretical problems of copyright protection of digital content. Embedding identification data in the content is a well-developed technique of content protection known under the name of fingerprinting. Schemes that provide such protection are known as fingerprinting codes in the literature. We study limits of the number of users of a fingerprinting system as well as constructions of low-complexity fingerprinting codes that support a large number of users. The second problem that is addressed in the dissertation relates to connectivity analysis of ad hoc wireless networks. One of the basic requirements in such environments is to ensure that none of the nodes are completely isolated from the network. We address the problem of characterizing threshold parameters for node isolation that enable the system designer to choose the power needed for network operation based on the outage probability of links in the network. The methods of this research draw from coding theory, information theory and random graphs. An idea that permeates most results in this dissertation is the application of randomization both in the analysis of fingerprinting and node isolation. The main contributions of this dissertation belong in the area of fingerprinting and are described as follows. We derive new lower and upper bounds on the optimal trade-off between the number of users and the length of the fingerprints required to ensure reliability of the system, which we call fingerprinting capacity. Information-theoretic techniques employed in our proofs of bounds on capacity originate in coding theorems for channels with multiple inputs. Constructions of fingerprinting codes draw on methods of coding theory related to list decoding and code concatenation. We also analyze random graph models for ad hoc networks with link failures and secure sensor networks that employ randomized key distribution. We establish a precise zero-one law for node isolation in the model with link failures for nodes placed on the circle. We further generalize this result to obtain a one-law for secure sensor networks on some surfaces.Item Information Theoretic Generation of Multiple Secret Keys(2005-10-21) Ye, Chunxuan; Narayan, Prakash; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation studies the problem of secret key generation for encrypted group communication in a network, based on an information theoretic approach. This approach, which relies on a provable form of security, also provides suggestions for key constructions. We examine the problem of the simultaneous generation of multiple keys by different groups of terminals intended for encrypted group communication, in certain three-terminal source models, which capture the salient features of general multiterminal models. We characterize the rates at which two designated pairs of terminals can simultaneously generate private keys, each of which is effectively concealed from the remaining terminal, and the rates at which the following two types of keys can be generated simultaneously: (i) all the three terminals generate a (common) secret key, which is effectively concealed from an eavesdropper; and (ii) a designated pair of terminals generate a private key, which is effectively concealed from the remaining terminal as well as the eavesdropper. Furthermore, we develop an approach for the construction of a new class of provably secure secret keys by terminals in several simple multiterminal source models, which exploits innate connections between secret key generation and multiterminal Slepian-Wolf near-lossless data compression (sans secrecy restrictions). Implementations of these constructions using low density parity check (LDPC) channel codes are illustrated.Item Achievable Rates, Optimal Signalling Schemes and Resource Allocation for Fading Wireless Channels(2005-08-04) Kaya, Onur; Ulukus, Sennur; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The proliferation of services involving the transmission of high rate data traffic over wireless channels makes it essential to overcome the detrimental effects of the wireless medium, such as fading and multiuser interference. This thesis is devoted to obtaining optimal resource allocation policies which exploit the transmitters' and receiver's knowledge about the fading to the network's advantage, to attain information theoretic capacity limits of fading wireless channels. The major focus of the thesis is on capacity results for fading code division multiple access (CDMA) channels, which have proved to be a robust way of combatting the multiuser interference in practical wireless networks. For these channels, we obtain the capacity region achievable with power control, as well as the power control policies that achieve the desired rate points on the capacity region. We provide practical one-user-at-a-time iterative algorithms to compute the optimal power distributions as functions of the fading. For the special case of sum capacity, some properties of the optimal policy, such as the number of simultaneously transmitting users, are obtained. We also investigate the effects of limited feedback on the capacity, and demonstrate that very coarse channel state information (CSI) is sufficient to benefit from power control as a means of increasing the capacity. The selection of the signature sequences also plays an important role in determining the capacity of CDMA systems. This thesis addresses the problem of jointly optimizing the signature sequences and power levels to maximize the sum capacity. The resulting policies are shown to be simple, consisting of orthogonal transmissions in time or signal space, and requiring only local CSI. We also provide an iterative way of updating the joint resource allocation policy, and extend our results to asynchronous, and multi-antenna CDMA systems. Rather than treating the received signal at the transmitters as interference, it is possible to treat it as free side information and use it for cooperation. The final part of the thesis provides power allocation policies for a fading Gaussian multiple access channel with user cooperation, which maximize the rates achievable by block Markov superposition coding, and also simplify the coding strategy.