A reversible watermarking method embeds auxiliary data into a data set, such as an image, audio, video or other data, in a manner that enables full recovery of the original, un-modified data set. This method may be used to determine whether the data set has been tampered. To improve embedding capacity without the need for compression of the auxiliary data, the method uses an expansion technique. One particular approach exploits the correlation or redundancy within the data set to convert the data to a set of small, expandable values, such as difference values. These small values are then expanded by inserting auxiliary data as one or more additional bits, increasing the number of bits without causing an underflow or overflow. This approach also uses a property of the data set that is invariant to the embedding operation to identify embedding locations, obviating the need for separate data to identify where data is embedded in a data set.