1. A method of embedding auxiliary data in coefficients generated for a compressed data stream, the method comprising: receiving coefficients in the data stream, the coefficients being divided into blocks; changing the value of selected coefficients to embed multi-bit message data in the coefficients, the changing including controlling changes to the selected coefficients from different blocks so that the relationship of the selected coefficients from the different blocks satisfy an embedding rule.