A Caltech Library Service

On Delay and Security in Network Coding


Dikaliotis, Theodoros K. (2013) On Delay and Security in Network Coding. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/1KE1-DW91.

This is the latest version of this item.


In this thesis, delay and security issues in network coding are considered. First, we study the delay incurred in the transmission of a fixed number of packets through acyclic networks comprised of erasure links. The two transmission schemes studied are routing with hop-by-hop retransmissions, where every node in the network simply stores and forwards its received packets, and linear coding, where nodes mix their packets by forwarding linear combinations of all their previously received packets. We show that even though the achievable rates of coding and routing are the same, network coding can have an increasingly better performance than routing as the number of packets increases.

Secondly, we investigate the security benefits of network coding. We investigate the achievable secrecy rate region in a general network of noisy wiretap channels with general communication demands. The eavesdropper has access to an unknown set of links, and on the wiretapped links observes a degraded version of the intended receiver's observation. While characterizing the capacity in general is an open problem, in the noise-free case there exist inner and outer bounds. In the noisy case, we show how one can change any of the wiretap channels to a noiseless degraded broadcast channel, so that the derived network's rate region bounds, and under certain conditions is equivalent, to that of the initial network. Specifically, we showed that in case the eavesdropper can choose only a single link to wiretap at each time, then one can change all the links in the network with corresponding noiseless ones, creating an equivalent noiseless secrecy problem. In the case where the eavesdropper can wiretap multiple links simultaneously, we derive upper and lower bounding noiseless network problems.

Finally, we consider design practical code design for the detection of adversarial errors in a distributed storage system. We build on work of functions that can fool linear polynomials to create and communicate hash functions of the data in order to detect with high probability the maliciously attacked nodes in the system.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:information theory, network coding, secrecy
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Ho, Tracey C.
Thesis Committee:
  • Ho, Tracey C. (chair)
  • Effros, Michelle
  • Hassibi, Babak
  • Low, Steven H.
  • Vaidyanathan, P. P.
Defense Date:31 May 2012
Record Number:CaltechTHESIS:09292012-041022964
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7217
Deposited By: Theodoros Dikaliotis
Deposited On:21 Nov 2012 17:32
Last Modified:07 Jun 2023 17:14

Available Versions of this Item

  • On Delay and Security in Network Coding. (deposited 21 Nov 2012 17:32) [Currently Displayed]

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page