A generalized block diagram that is representative of the prior lossless authentication watermarking schemes is seen in Fig. 1. In these methods, the watermark embedding phase has two stages: a) an authentication-information (e.g., digital signature) computation step; and b) a lossless (reversible) data embedding step, in which the computed information is inserted into the image data in a reversible manner. During the recovery and verification phase, first the data embedding process is reversed to yield an estimate for the original image and the authentication information. If the watermarked image has not been altered, the extracted information validates the estimated image and this estimate is labeled as an authentic original.
Virtually all existing schemes [9]–[14] follow this framework with differences in the lossless data embedding step. In [9], Fridrich et al. implemented the lossless data embedding step by compression and replacement of one or more least-signifi- cant bit planes of the image data. Later, the authors proposed a more efficient algorithm based on RS-embedding method [13]. Meanwhile, Honsinger et al. [10] proposed using a spread-spec- trum watermark with modulo-addition for lossless reconstruc- tion. Similarly, De Vleeschouwer et al., Tian and van der Veen have proposed methods based on the circular interpretation of the image histogram [14], difference expansion [11], and his- togram modifications [15], respectively.
In [16], Dittmann et al. proposed an alternative protocol based on the least significant bit (LSB) compression technique of [9]. The protocol utilizes a public and a private key signature corre- sponding to the most and least significant bit planes, respectively. When combined with the encryption of the compressed LSB information, the method allows for public-key verification of the watermarked image while reserving the reconstruction of the perfect original to the authorized parties that hold the private-key. Despite the added functionality, the protocol is not extensible to all lossless embedding methods, for instance Honsinger’s method [10]. Furthermore, it requires an increased payload, thus a higher embedding distortion, due to the second signa- ture. Note that none of the lossless authentication methods in the literature offer tamper localization capability, which is one of the major advantages of authentication watermarks over con- ventional digital signatures