Techniques for watermarking digital representations such as MPEG audio frames that spread the watermark information across the entire audio frame. The techniques work in conjunction with lossy compression techniques and are compatible with the perception models that are often used with lossy compression techniques. The watermark information is spread by means of transformations between the space/time domain and the frequency domain. When a MPEG audio frame is being watermarked, the compressed audio frame as it is produced by the quantizer is transformed from the frequency domain to the time domain; the time domain transformation is then randomized using a key and the randomized time domain transformation is transformed into the frequency domain. The watermark information is added at a predetermined frequency in the frequency domain transformation and the sequence of transformations is done in reverse order, with the randomization and derandomization serving to distribute the watermark information across the frequency domain representation of the watermarked audio frame.