We propose a video data embedding scheme in which the embedded signature data is reconstructed without knowing the original host video. The proposed method enables high rate of data embedding and is robust to motion compensated coding, such as MPEG-2. Embedding is based on texture masking and utilizes a multi-dimensional lattice structure for encoding signature information. Signature data is embedded in individual video frames using the block DCT. The embedded frames are then MPEG-2 coded. At the receiver, both the host and signature images are recovered from the embedded bit stream. We present examples of embedding image and video in video.