A Novel Unbalanced Tree Structure for Low-Cost Authentication of Streaming Content on Mobile and Sensor Devices

The authors consider stored content being streamed to a resource-poor device (such as a sensor node or a mobile phone), and address the issue of authenticating such content in real-time at the receiver. Per-packet digital signatures incur high computational cost, while per-block signatures impose high delays. A Merkle hash tree combines the benefits of the two by having a single signature per-block (at the root of the tree), while allowing immediate per-packet verification by following a hash-path logarithmic in the number of packets. In this paper, they explore how the structure of the Merkle tree can be adapted to improve playback performance for streaming content.