Paper 2000/058

Graph-Based Authentication of Digital Streams

Sara Miner and Jessica Staddon


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.

Available format(s)
Publication info
Published elsewhere. 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.
authenticationdigital streamsmulticastmessage authentication codessignaturesgraphs
Contact author(s)
sminer @ cs ucsd edu
2001-07-26: last of 4 revisions
2000-11-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sara Miner and Jessica Staddon},
      title = {Graph-Based Authentication of Digital Streams},
      howpublished = {Cryptology ePrint Archive, Paper 2000/058},
      year = {2000},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.