Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

6-2012

Abstract

We 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 realtime 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 we explore how the structure of the Merkle tree can be adapted to improve playback performance for streaming content. We make three specific contributions: First, we develop a new unbalanced authentication tree structure called the α-leaf tree that is a generalisation of the Merkle tree. We derive several key properties of this tree, highlighting the impact of the imbalance parameter α. Second, we present a theoretical model to quantify the benefits of our unbalanced tree structure in reducing startup delays for streaming applications by optimally readjusting the burden of authentication across packets. Third, we validate via simulation the suitability of our scheme to two representative applications, namely audio streaming to a low-cost sensor device and video streaming to a mobile phone, and demonstrate that start-up delays can be reduced without affecting stall rates. We believe our authentication tree structure is of importance both theoretically, as a generalisation of the Merkle hash tree, as well as practically, for applications requiring real-time verification of streaming content.

Keywords

Content Authentication, Digital Signature, Merkle Tree

Discipline

Databases and Information Systems | Software Engineering

Research Areas

Software and Cyber-Physical Systems

Publication

Proceedings of the 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), Seoul, South Korea, 2012 June 18-21

Volume

1

First Page

488

Last Page

496

ISBN

9781467319058

Identifier

10.1109/SECON.2012.6275816

Publisher

IEEE Computer Society

City or Country

Washington, DC

Additional URL

https://doi.org/10.1109/SECON.2012.6275816

Download

Share

COinS