Real-time streaming services are attracting attention. However, an adversary can compromise the safety of these services in ways such as data tampering, spoofing, and repudiation. In this paper we propose a real-time Stream Authentication scheme for Video streams called SAVe. Each packet in the stream is authenticated to correspond to the packet loss seen in UDP-based streaming. The amount of redundancy distributed to each frame is also adjusted according to the importance of each frame, to take account of the special characteristics of video such as differences in importance of and dependencies between frames. Since temporal and spatial compression techniques are adopted for video stream encoding, SAVe is efficient in terms of making important frames robust to packet loss. The simulation results show that the authentication rate is on average approximately equivalent to that of previously proposed schemes. An improvement of 50% in the playing rate over previously proposed schemes can be seen when the packet loss rate is 20%.