A Novel Unbalanced Tree Structure for Low-Cost Authentication of Streaming Data

Select |


Kandappu, Thivya; Sivaraman, Vijay; Boreli, Roksana


Conference Material

IEEE Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON)

Seoul, South Korea


We consider content being streamed to a resource-poor de- vice (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 computa- tional cost, while per-block signatures impose high delays. A Merkle 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 per-block. However, the balanced nature of Merkle trees equalises au- thentication cost among packets, which can result in higher start-up delay for the application. In this paper we propose a generalisation of the Merkle tree, called the α-Leaf Tree, that is unbalanced, allowing faster authentication of initial packets at the expense of increased authentication for later packets. We derive several proper- ties of the α-Leaf tree, and show that readjusting the burden of authentication across the packets allows streaming appli- cations to have a lower start-up delay. We demonstrate the suitability of our scheme via simulation to a wide range of applications ranging from video streaming and virtual envi- ronments to sensor-node reprogramming.

Content Authentication, Digital Signature, Merkle Tree.



Kandappu, Thivya; Sivaraman, Vijay; Boreli, Roksana. A Novel Unbalanced Tree Structure for Low-Cost Authentication of Streaming Data.[Conference Material]. 2012-06-18. <a href="http://hdl.handle.net/102.100.100/100439?index=1" target="_blank">http://hdl.handle.net/102.100.100/100439?index=1</a>

Loading citation data...

Citation counts
(Requires subscription to view)