International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Graph-Based Authentication of Digital Streams

Sara Miner
Jessica Staddon
Search ePrint
Search Google
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.
  title={Graph-Based Authentication of Digital Streams},
  booktitle={IACR Eprint archive},
  keywords={authentication, digital streams, multicast, message authentication codes, signatures, graphs},
  note={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. 11529 received 12 Nov 2000, last revised 25 Jul 2001},
  author={Sara Miner and Jessica Staddon},