A Coding Approach to the Multicast Stream Authentication Problem

Christophe Tartary

Macquarie University

We address the multicast stream authentication problem when the communication channel is under the control of an opponent who can drop, reorder or inject data. In such a network model, packet overhead and computing efficiency are important parameters to be taken into account when designing a multicast authentication protocol.
In this presentation, we will show how coding theory can be employed in such a context. Using a class of rateless codes called Luby Transform codes, we will design an authentication scheme allowing every received data packet to be authenticated with probability arbitrary close to 1. We will improve this result thanks to a family of Maximal Distance Separable codes which will enable us to recover from channel erasures and authenticate erased data as well.
Non-repudiation will be provided via digital signatures. In both cases the number of signature verifications to be performed per block of n data packets will be O(1) (as a function of n) due to the properties of a list decoding algorithm designed by V. Guruswami and M. Sudan in 1999.