Combining prediction hashing and MDS codes for efficient multicast stream authentication

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. In this work, we consider that the stream to be authenticated is divided into block of n packets and we assume that the sender can memorize λ such blocks. Two important parameters for stream authentication protocols are packet overhead and computing efficiency. Our construction will exhibit the following advantages. First, our packet overhead will be a few hashes long. Second, the number of signature verifications per family of λ blocks will be O(1) as a function of both λ and n. Third, hash chains will enable the receiver to check the validity of received elements upon reception. As a consequence he will only buffer those consistent with the original data packets. Fourth, the receiver will be able to recover all the data packets emitted by the sender despite erasures and injections by running the decoding algorithm of the maximal distance separable code onto the elements which have passed the previous filtering process.15 page(s