Video authentication techniques are used to prove the originality of received video content and to detect malicious tampering. Existing authentication techniques protect every single bit of the video content and do not allow any form of manipulation. In real applications, this may not be practical. In several situations, compressed videos need to be further processed to accommodate various application requirements. Examples include bitrate scaling, transcoding, and frame rate conversion. The concept of asking each intermediate processing stage to add authentication codes is flawed in practical cases. In this paper, we extend our prior work on JPEG- surviving image authentication techniques to video. We first discuss issues of authenticating MPEG videos under various transcoding situations, including dynamic rate shaping, requantization, frame type conversion, and re-encoding. Different situations pose different technical challenges in developing robust authentication techniques. In the second part of this paper, we propose a robust video authentication system which accepts some MPEG transcoding processes but is able to detect malicious manipulations. It is based on unique invariant properties of the transcoding processes. Digital signature techniques as well as public key methods are used in our robust video authentication system.