Authentication of Digital Streams

We study the multicast stream authentication problem when the communication channel is under control of an opponent who can drop, reorder and inject data packets. Recently, many coding theory based protocols have been developed to treat the stream authentication problem over such a channel. In this paper, our goal is to provide a general coding approach for multicast stream authentication. We design an authentication protocol which combines any list recoverable code (provided some conditions on its construction parameters). We demonstrate that the previous schemes can be viewed as instances of our construction when a Reed-Solomon code is used as a list recoverable code. In such settings, we also show that our approach leads to a better upper bound on the number of signature verification queries for each receiver.