ACM Multimedia and Security Workshop at 8th ACM International Conference on Multimedia 2000
Los Angeles, California
Electronic Proceedings
© 2000 ACM
Structural Digital Signature for Image Authentication: An Incidental Distortion Resistant Scheme
- Chun-Shien Lu
Institute of Information Science, Academia Sinica,
Nankang, Taipei, Taiwan,
ROC
+886-2-27883799 ext. 2415
http://smart.iis.sinica.edu.tw/~lcs
lcs@iis.sinica.edu.tw
Hong-Yuan Mark Liao
Institute of Information Science, Academia Sinica,
Nankang, Taipei, Taiwan,
ROC
+886-2-27883799 ext. 1811
http://www.iis.sinica.edu.tw/~liao
liao@iis.sinica.edu.tw
Abstract
The existing digital data authentication methods are able to detect tampered regions, but are too fragile to resist incidental distortions. This paper will present a new digital signature scheme for image authentication by making use of image content (in the wavelet domain). Based on this concept, a structural digital signature (SDS) is constructed. SDS is a signature that can be used to judge whether an incoming modification is incidental or malicious. When the structure of an SDS is maintained near-complete, we classify the incoming modification as incidental; otherwise, it is malicious. Many incidental manipulations, which cannot be tolerated in previous digital signature or fragile watermarking methods, can now survive under the proposed scheme.
Owing to the popularity of data digitization, it is easy to tamper with the digitized data while leaving no hints. This will raise an emergent need of data integrity verification in order to judge whether a data is authentic or fake. Conventionally, content verification can be roughly classified into two categories: digital signature-based [1,2,4,6,7] and watermark-based [3,5,8,10,12,13,14,15,16,17]. Digital signature represents the characteristic of an image and is stored as an extra file, which is used later for authentication. Watermarking, on the other hand, is a new method which embeds hidden information into an image and the hidden message is later extracted to verify the authenticity of the data. When an attack is applied, it will actually modify the content of the data. Under the circumstances, no matter a signature-based approach or a watermark-based approach is adopted, they all will be influenced. However, a good authentication scheme should be able to tolerate incidental modification while detecting the malicious update. Unfortunately, previous approaches are still vulnerable to some incidental image processings. The main reason is that the existing methods cannot define a good tradeoff between robustness and fragility.
According the underlying technology used, the above methods can be roughly classified into be quantization-based [5,8,10,16], feature-based [1,2], and relation-based [6,7]. For quantization-based approaches, Kundur and Hatzinakos [5] designed a wavelet-based quantization process, which is sensitive to modifications. The main disadvantages are that their method cannot resist incidental modifications and the tampering detection results are very unstable. Recently, we have proposed a multipurpose watermarking scheme [8,10] for image/audio authentication and protection. We combine a host data-dependent quantization and a complementary watermark hiding strategy [9] to conceal watermarks and present various detection techniques to achieve a certain degree of robustness and fragility simultaneously.
For feature-based authentication systems, Bhattacharjee and Kutter [1] proposed to generate a digital signature by encrypting the feature points of an image. Authentication is then accomplished by comparing the positions of the feature points with those decrypted from the previously encrypted feature points. Again, it is not shown whether this approach can resist JPEG compression with middle-to-high ratios. Recently, Dittmann et al. [2] presented a content-based digital signature approach for image/video authentication using edge characteristics. Their content feature is similar to [1], but different extraction techniques are used.
On the other hand, in order to make the designed image authentication system survive JPEG compression, Lin and Chang [6,7] proposed to preserve the invariance between the DCT coefficients before and after quantization. However, it was not shown how their method could survive other incidental manipulations. In addition, it should be noted that although the authors [6,7] used the invariance property to authenticate images, however, this relationship is random because the invariance property of any two "random" DCT blocks are stored as the digital signature. Under the circumstances, the merit of image structure is ignored.
In this paper, we shall develop a new image authentication scheme, which is totally different from the existing methods in that we don't care the magnitudes of coefficients or the relationship of random coefficients. On the contrary, we consider the ``structure'' of an image's characteristics as the digital signature. The structure of image content is composed of parent-child pairs in the wavelet domain. We investigate how this image structure can be robust under image content-preserving manipulations and can be fragile under image content-changing manipulations. Performance analysis on the structural digital signature is given and experimental results are demonstrated.
Our scheme is based on wavelet transform due to its excellent multiscale representation property, which is suitable for designing a structural digital signature.
Let ws,o(x,y) be a wavelet coefficient at the scale s, the orientation o, and the position (x,y) in an orthogonal downsampled wavelet transform. Suppose J-scale wavelet transform is performed, then 0<= s < J. Large/small scale represents coarser/finer resolution of an image, i.e., the low/high frequency part. Orientation o denotes horizontal, vertical, or diagonal direction. The interscale relationship of wavelet coefficients is defined for the parent node ws+1,o(x,y) and its four child nodes ws,o(2x+i,2y+j) as either |ws+1,o(x,y)| = |ws,o(2x+i,2y+j)| or |ws+1,o(x,y)| <= |ws,o(2x+i,2y+j)|, where 0<= s < J, 0<= i, j <= 1, and 1<= x<= N and 1<= y<= M (NM is the image size). Our idea is that the interscale relationship is difficult to be destroyed by content-preserving manipulations and is hard to be preserved by content-changing manipulations. Because these interscale relationships are resulted from the image structure, we call them as the structural digital signature (SDS).
In our scheme, the structural digital signature is designed to be composed of the relationships (see Sec. 2.2 for details) of those parent-child pairs, i.e., satisfies

where
.
These relationships are encrypted (e.g., by RSA) and stored in the database for verification later. We do not intend to keep all the parent-child pairs as the SDS because some of them are not significant. The significance of a parent-child pair is completely determined by their magnitude of difference. The larger the difference is, the more significant the parent-child pair is. Those parent-child pairs with small differences are very similar to the ``small'' quantization interval in those quantization-based approaches [5,8,10,16]. They are very sensitive to modifications and are not beneficial to incidental distortions. Therefore, we only keep those parent-child pairs with larger differences as the elements of a structural digital signature. This also means that the size of a structural digital signature plays the trade-off role between robustness and fragility. Construction of a structural digital signature is very easy and fast because feature selection [1,2] is not required.
According to the interscale relationship of wavelet coefficients, there are four types of relationship between SDS's elements. For example, let a parent node (p) be larger than its child node (c) (i.e., |p|>|c|). Then, the four types of SDS's elements are (i) p >= 0, c >= 0; (ii) p >= 0, c <= 0; (iii) p <= 0, c >= 0; (iv) p <= 0, c <= 0. Under the condition that |p|>|c|, c is possible to be small or not large enough. In order for the pair (p,c) (|p|>|c|) to be credible when incidental modifications are encountered, the types (i) and (ii) are combined to from a new type I (p >= 0 and c don't care) and the types (iii) and (iv) are condensed to a new type II (p<= 0 and c don't care). In other words, we hope to keep the sign of the larger element unchanged while do not care the small one under the constraint that the original interscale relationship is preserved. The types III (c>= 0 and p don't care) and IV (c<= 0 and p don't care) can be similarly defined under the situation |p|<|c|.
In the verification process, for an image (\tilde{I}) to be verified, it is firstly wavelet transformed. According the decrypted structural digital signature of the original image I, we check the relative parent-child interscale relationship of \tilde{I}. Then, we calculate the completeness of SDS (CoSDS) of \tilde{I}, which is defined as the similarity of SDS(I) and SDS(\tilde{I}):
where N+ and N- represent, respectively, the number of the same type and that of the different type (defined in Sec. 2.2). The higher completeness of SDS means that the suspect image \tilde{I} is reliable; otherwise it is maliciously tampered.
Let I be an image, A be any incidental manipulation, and \psi be a wavelet function.
The distorted image will be I*A (denoted as
and * is a convolution operation), which will be authenticated in the wavelet domain.
The whole transformation process can be derived as
where
is the wavelet transformed image in the space-frequency domain.
Eq. 3 indicates that the wavelet transform of the distorted image IA is the same as the modification (by A) of the wavelet transformed image I\psi.
If A is a quantization operation in some compression methods, any coefficient in
will be only affected by itself through A.
Owing to the behavior of compression like SPIHT [11] is easy to be predicted, we will analyze its effects.
SPIHT is a progressive image coding scheme in which the most significant bits are transmitted first.
In the SDS, suppose p (a parent node) and c (a child node) form a parent-child pair and they satisfy the relation 2k>|p|>2k-1>...>2k-j>|c|>2k-(j+1) with j=1.
During the SPIHT compression process, we may face three conditions: (1) Under high compression ratio, suppose 2t is the threshold finally used in the dominant process and t>=k, the reconstructed values, pr and cr, will be both zeros.
This means the original structure $|p|>|c|$ is preserved due to pr=cr=0 which satisfies one of the four types of parent-child relationship.
(2) Under middle compression ratio, suppose k-1>=t>=k-j, we will obtain |pr|>|cr|=0.
Again, the parent-child structure is preserved.
(3) Under small compression ratio, suppose k-(j+1)>= t, we will obtain |pr|>|cr|!= 0.
Again, the parent-child structure is preserved. According to the basis of SPIHT, it is guaranteed that the proposed SDS will survive SPIHT compression with any ratio. The preservation of SDS under JPEG can be analyzed similarly. On the other hand, if A is another incidental manipulation (excluding compressions), its behaviors may not be easily controlled. This is because the effect of one specific coefficient's change is determined by A (for example A is a Gaussian filter Ce(-(x2)/(\sigma2)).
But, we seize the rule that the unavoidable manipulations will not destroy the image structure, so a structural digital signature is expected to survive their attacks.
Let the differences of parent-child pairs be arranged in a decreasing order in a structural digital signature (SDS) and n be the size of SDS. No matter either an incidental modification or a malicious tampering is encountered, the preceding elements are not easily attacked (changed). Therefore, they are suitably used for the robustness purpose. If the size (n) of SDS is long enough, then the robustness property will be more or less affected. On the other hand, the posterior elements are easy to be changed, so they are suitably used for the fragility purpose. If the size (n) of SDS is short enough, then the fragility property may be disappeared. At present, owing to the lake of a systematic way to determine n, n is chosen according to the image size. From the experimental results (to be shown later), it is found that n can be flexibly determined because the compromise between robustness and fragility is not hard to attain.
Owing to SDS is composed of elements with larger \rho (by Eq. 1), false positive can never be occurred merely from the rounding errors. This is due to the rounding error is significantly smaller than \rho. The problem of false positive due to SPIHT and JPEG is equivalent to robustness capability.
Suppose a parent node p (p>0) and a child node c is a pair and has the relation |p|= |c| and ||p|-|c||=\rhoi (\rho in Eq. 1). For simplicity, let p be decreasingly changed with p-Mp by a malicious manipulation. If |p-Mp|>|c| holds under the condition that |p|>|c|, then a false negative is resulted due to 0<= Mp<= \rhoi. If the modification quantity Mp is assumed to be Gaussian distributed (with variance \sigma2), then the false negative probability of a pair will be defined as
(C is a constant). When a malicious distortion is applied to an image, let \beta (0<=\beta<= 1) be the ratio of parent-child pairs that has been maliciously tampered. If the original interscale relationships still hold, the total false negative probability will be
. It is predictable that Pfn will be very small value.
Our structural digital signature-based image authentication scheme was tested using the Beach image of size 256X256, as shown in Fig. 1(a). The image with a large object placed (shown in Fig. 1(b)), was used to test the fragile capability of our scheme. First, 1000 parent-child pairs consisting of the first $SDS$ were used to authenticate the tampered image shown in Fig. 1(b). The detected results at different scales were shown in Figs. 1(c)-(e). Besides, the second SDS, which was composed of 3000 parent-child pairs, was also used for verification. The detected results were shown in Figs. 1(f)-(h). As one can expect, SDS of small size will lose some tampered pixels. However, the integration of tampered results from different scales was sufficiently to indicate the tampered area. In addition, another similar set of results was shown in Fig. 2, where a very small object was placed in the original image. This example is mainly used to demonstrate the compromise between robustness and fragility with respect to different sizes of SDS. On the other hand, the robustness of our scheme was tested on many incidental distortions using the image shown in Fig. 1(a). Table 1 shows the results obtained under SPIHT compression with different ratios and three different sizes of SDS. For JPEG compression, perfect preservation of SDS was obtained with quality factors ranging from 60% (6:1) to 10% (20:1). Furthermore, Table 2 shows the results obtained under other incidental distortions. >From the results shown in the above tables, we can see that the completeness of a structural digital signature is very high, which means that our method is really able to resist common incidental modifications.

In this paper, a new structural digital signature scheme has been proposed for image authentication. Performance analysis on structural digital signature has been provided and experimental results show that our scheme is really robust to content-preserving manipulations and fragile to content-changing distortions. Future work will focus on developing structural watermarking, which can be used for public-key detection from the viewpoint that the watermark structure can only be removed if its structure is destroyed. However, destroying the watermark structure will get more penalties on image quality.
[1] S. Bhattacharjee and M. Kutter, ``Compression Tolerant Image Authentication'', IEEE Inter. Conf. on Image Processing, USA, 1998.
[2] J. Dittmann, A. Steinmetz, and R. Steinmetz, ``Content-based Digital Signature for Motion Pictures Authentication and Content-Fragile Watermarking'', Proc. IEEE Conf. Multimedia Computing and Systems, Vol. II, Italy, 1999.
[3] J. Fridrich, ``Methods for Detecting Changes in Digital Images'', Proc. IEEE Int. Workshop on Intell. Signal Processing and Communication Systems, 1998.
[4] G. L. Friedman, ``The Trustworthy Digital Camera: Restoring Credibility to the Photographic Image'', IEEE Trans. Consumer Electronics, Vol. 39, pp. 905-910, 1993.
[5] D. Kundur and D. Hatzinakos, ``Digital Watermarking for TellTale Tamper Proofing and Authentication'', Procceedings of the IEEE, Vol. 87, pp. 1167-1180, 1999.
[6] C.-Y. Lin and S.-F. Chang, ``A Robust Image Authentication Method Surviving JPEG Lossy Compression'', SPIE Storage and Retrieval of Image/Video Database, Vol. 3312, San Jose, 1998 (www.ctr.columbia.edu/~cylin/auth/auth.html).
[7] C.-Y. Lin and S.-F. Chang, ``Generating Robust Digital Signature for Image/Video Authentication'', Multimedia and Security Workshop at ACM Multimedia, UK, 1998.
[8] C. S. Lu, H. Y. Mark Liao and C. J. Sze, ``Combined Watermarking for Image Authentication and Protection'', Proc. 1st IEEE Int. Conf. on Multimedia and Expo, USA, 2000.
[9] C. S. Lu, H. Y. Mark Liao, S. K. Huang, and C. J. Sze, ``Cocktail Watermarking on Images'', Proc. 3rd Inter. Workshop on Information Hiding, LNCS 1768, pp. 333-347, Sept. 29-Oct. 1, 1999 (smart.iis.sinica.edu.tw/~lcs).
[10] C. S. Lu, H. Y. Mark Liao and L. H. Chen, ``Multipurpose Audio Watermarking'', Proc. 15th Int. Conf. on Pattern Recognition, Spain, 2000.
[11] A. Said and W. A. Pearlman, "A New, Fast, and Efficient Image Codec based on Set Partitioning in Hierarchical Trees'', IEEE Trans. Circuit and Systems for Video Technology, Vol. 6, pp. 243-250, 1996.
[12] S. Walton, ``Image Authentication for A Slippery New Age'', Dr. Dobb's Journal, Vol. 20, pp. 18-26, 1995.
[13] R. B. Wolfgang and E. J. Delp, ``Fragile Watermarking Using the VW2D Watermark'', Proc. SPIE/IS\&T Inter. Conf. Security and Watermarking of multimedia Contents, Vol. 3657, pp. 40-51, 1999.
[14] M. Wu and B. Liu, ``Watermarking for Image Authentication'', Proc. IEEE Int. Conf. Image Processing, 1998.
[15] M. M. Yeung and F. Mintzer, ``An Invisible Watermarking Technique for Image Verification'', IEEE Int. Conf. Image Processing, Vol. 2, pp. 680-683, 1997.
[16] G. J. Yu, C. S. Lu, H. Y. Mark Liao and J. P. Sheu, ``Mean Quantization Blind Watermarking for Image Authentication,'' Proc. 7th IEEE Int. Conf. on Image Processing, Canada, 2000.
[17] B. Zhu, M. D. Swanson, and A. H. Tewfik, ``Transparent Robust Authentication and Distortion Measurement Technique for Images'', 7th IEEE Digital Signal Processing Workshop, pp. 45-48, 1996.