Algorithms that perform data hiding directly in the compressed domain, without the need for partial decompression or transcoding, are highly desirable. We based this work on the recognition of the idea that only a limited amount of a possible codespace is actually used for any specific code. Therefore, if bits are chosen appropriately, watermarking them will place a codeword outside of the valid codespace. Variable length codes in compressed bitstreams, however, have virtually no redundancy to losslessly carry hidden data. Altered VLCs will likely remain valid. In this work, we examine the bitstream not as individual VLCs but as codeword-pairs. Pairing codewords conceptually shrinks the percentage of available codespace that is actually being used. This idea has a number of key advantages, including that the watermark embedding is mathematically lossless, file size is preserved and the watermarked bitstream will still remain format-compliant. This algorithm is most appropriate for compression algorithms that are error-resilient. For example, the error concealment property of MPEG-4 or H.263+ can also counter bit “errors” caused by the watermarking while playing the video. The off-line portion of the algorithm needs to be run only once for a given VLC table regardless of multiple mediums employing the table. This allows for the algorithm to be applied in real time, both in embedding and removal, due to implementation in the compressed domain.