Covert and Secure Communicatio

In this thesis I consider two problems related to secure communication { that of covert communication, and that of network communication in the presence of node adversaries.;In the covert communication problem, Alice may wish to communicate with Bob reliably to a receiver Bob over a binary symmetric channel (BSC), and covertly from an eavesdropper Willie. That is, Willie should not be able to determine whether Alice is communicating with Bob or not. For this problem, I consider two scenarios. In my first scenario, I assume that the channel transition probability from Alice to Bob (if communication is indeed happening), and from Alice to Willie is perfectly known to all parties. Here, even when Alice's (potential) communication scheme is known priori to Willie (with no common randomness between Alice and Bob), I prove that over n channel uses Alice can transmit a message of length O (√n) bits to Bob, while being covert from Willie. I also prove information-theoretic order-optimality of this result. In my second scenario, I allow uncertainty in the knowledge of the channel transition probability parameters. In particular, I assume that the channel noise parameters of both the channel from Alice to Bob (if it is being used) and the channel from Alice to Willie are drawn from a distribution known a priori to all parties. Here, I show that, in contrast to the previous setting, Alice can communicate O( n) bits of message reliably and covertly (again, with no common randomness). I give both an achievability result and a matching converse for this setting.;In the problem of network communication in the presence of adversarial nodes, I consider secure unicast transmission between two nodes in a directed graph, where an adversary eavesdrops/ jams a subset of nodes. This adversarial setting is in contrast to the most studied model in the literature, where the adversary controls a subset of links. In particular, I study, in the main, the class of routing-only schemes (as opposed to those allowing coding inside the network). Routing-only schemes usually have low implementation complexity, yet a characterization of the rates achievable by such schemes was open prior to this work. I first propose an LP-based solution for communication secure against eavesdropping, and show that it is information-theoretically rateoptimal among all routing-only schemes. The idea behind my design is to balance information ow in the network so that no subset of nodes observes "too much" information. Interestingly, I show that the rates achieved by my routing-only scheme are always at least as good as (and sometimes better than) those achieved by "naive" network coding schemes (i.e., schemes designed for the scenario wherein the adversary controls links [rather than nodes] and is known to be optimal for such a scenario.) I also demonstrate non-trivial network coding schemes that achieve rates at least as high as (and again sometimes better than) those achieved by my routing schemes, but leave open the question of characterizing the optimal rate-region of the problem under all possible coding schemes. I then extend these routing-only schemes to adversarial node-jamming scenarios and show similar results. The techniques I develop for this problem have the potential to derive non-trivial bounds for general secure-communication schemes.