David Freeman: Homomorphic Signatures: Message Integrity for Network Coding and Beyond
Channel: Stanford Computer Science Theory
Date: 16/10/2011

David Freeman: Homomorphic Signatures: Message Integrity for Network Coding and Beyond

Network coding is a routing mechanism that offers increased throughput and improved robustness to random faults in completely decentralized networks. In contrast to traditional routing schemes, however, network coding requires intermediate nodes to modify data packets en route; for this reason, standard signature schemes are unable to ensure message integrity, and it is a challenge to provide resilience to tampering by malicious nodes.

In this talk we will survey cryptographic methods for ensuring integrity in network coding. We will discuss three different methods, whose security depends on the difficulty of (variants of) of three different computational problems, respectively: computing discrete logarithms, factoring large integers, and finding short vectors in lattices. These schemes are examples of "homomorphic signatures," which are schemes that can authenticate computations on signed data. We will conclude with a more general example of homomorphic signatures.

This talk will cover joint research with Dan Boneh, Jon Katz, and Brent Waters.