Cryptology ePrint Archive: Report 2000/058

Graph-Based Authentication of Digital Streams

Sara Miner and Jessica Staddon

Abstract: We consider the authentication of digital streams over a lossy network. The overall approach taken is graph-based, as this yields simple methods for controlling overhead, delay, and the ability to authenticate, while serving to unify many previously known hash- and MAC-based techniques. The loss pattern of the network is defined probabilistically, allowing both bursty and random packet loss to be modeled. Our authentication schemes are customizable by the sender of the stream; that is, within reasonable constraints on the input parameters, we provide schemes that achieve the desired authentication probability while meeting the input upper bound on the overhead per packet. In addition, we demonstrate that some of the shortcomings of previously known schemes correspond to easily identifiable properties of a graph, and hence, may be more easily avoided by taking a graph-based approach to designing authentication schemes.

Category / Keywords: authentication, digital streams, multicast, message authentication codes, signatures, graphs

Publication Info: This is the version of the paper that occurs in the proceedings of the 2001 IEEE Symposium on Security and Privacy, with several minor modifications.

Date: received 12 Nov 2000, last revised 25 Jul 2001

Contact author: sminer at cs ucsd edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20010831:065858 (All versions of this report)

Short URL: ia.cr/2000/058

Discussion forum: Show discussion | Start new discussion