Abstract
With the advent of Internet image authentication has become a central part of research in secu rity. Since JPEG has recommended discrete co sine transform as one of the steps in image com pression systems, a hash function which utilizes discrete cosine decomposition is desirable. In this paper, we propose a discrete cosine based hash function which distinguishes acceptable level of compression from image processing modifications such as Median filtering, Gaussian noise addition, and FMLR attack. To increase manipulation de tection, we optimize the number of AC coefficients needed in smoothing.
1

Introduction
Image authentication plays an important role in security and communication. Images are being transferred over the Internet and are readily avail able for access from any part of the world and without introducing authentication mechanism, it is almost impossible to distinguish if an image is original or being manipulated.
Introduction
Using cryptographic methods to authenticate image data will result in an unworkable systems or unacceptable systems because data authentica-1 tion are sensitive to single bit change in the origi nal data while image authentication systems need to be mainly content sensitive. This is because images undergo a range of processing including lossy compression that result in changes in bits that are deemed acceptable. Such changes must be tolerable by the authentication system while it is essential for the system to remain sensitive to malicious manipulations.
Introduction
The three main approaches to image authenti cation have been watermarking in which a fragile watermark is embedded in the image, image hash ing, also called feature extraction, in which a digest of the image capturing its main features is gener ated, and message authentication codes (MAC), also known as keyed hashing which uses a key in hash generation process. The image hash can be encrypted or digitally signed to generate an au thentication tag to be appended to the image. In all approaches there is also a verification system that takes an image with the authentication infor mation including the secret key, and produces a true/false value, depending on the authenticity, of the image. In recent years there has been numer ous proposals in each category. However assess ment of security in all cases have been ad-hoc and mainly through experiments. tion system depends on the size of the key, and the amount of computation required for genera tion and verification of the authentication tag. In this paper we are mainly concerned with hashing method. We propose hashing methods that use discrete cosine transform of an image.
Introduction
Two transform based authentication schemes known to date can be found in [1] and [2] . The one proposed by Bhattacharjee and Kutter [1] re lies on visually salient image features which are ex tracted using scale interaction based on Mexican Hat wavelet. In particular, their scheme looks at if the maximum of I;j = IWi(X) -, W j(x ) 1 in a circular neighbourhood with a radius of 5 around a pixel x is above a certain threshold T between scales i and j, and if the variance around x on the original image is above a cer tain threshold t. If the above two conditions are satisfied, the pixel x becomes a potential candi date for a feature point. The scheme proposed by Chun-Shin Lu and Hong-Yuan Mark Liao [2] relies on the fact that the interscale relationship is difficult to be destroyed by content preserv ing manipulations and is hard to be preserved by content changing manipulations. In particular, their scheme encodes the parent child relationship II Ws+1,o -Ws, o(2x+i, 2y+ j) 11 < P as a sequence of bits, which becomes the hash of an image.
Image Hashing
An image hashing algorithm H takes an arbitrary image I and produces a bit string XI. Unlike cryptographic hash functions, image hashing al gorithms must be bit insensitive and produce the same value for similar images that are defined through a set A of admissible transformations. These are transformations that do not modify the main features of the image. We say an image I' is similar to I if I' = a(I), a E A. We also need to define the set A' of inadmissible transformations, that consists of transformations that are applied to the whole image, such as compression at a low quality factor with the aim of damaging important details of the image, and localized modification of the content.
2
The hashing algorithm must produce 'close' val ues for images that are obtained through accept able transformations, and 'distant' values for im ages that are obtained through forbidden ones. To quantify the notions 'close' and 'distant' we re quire a distance function.
2
Some possible measures of distance between two hash values, v and v', are the correlation coeffi
2
and Euclidean distance dED(V, v').
2
If two hash values are close, that is dec{H(I),H(I')) E (1 -€, 1 + €) or dED(H(I),H(I')) < €, we say the two images are similar, or collide, and attach a confidence level to this statement. The threshold and the confidence level needs to be determined using the set A and
2
Image hash algorithms that are used for im age authentication must have the property that it must be difficult to construct two images I and I' that collide and 1=1= a(I'), a E A. This property is also called collision intractability and ensures that a manipulated image has a different hash value and so the authentication tag is only valid for sim ilar images.
2
A hash algorithm may produce a close value for an image that is obtained through a non admissible transformation, that is a collision, or produce a distant value for an image obtained through admissible transformation. These two will result in a false positive and false negative re sult, when the hashing is used for image authenti cation. For a good hash algorithm, the probability of false positive and false negative, taken over all possible inputs must remain small.
2
The basic idea of our proposal is to find the crit ical co-ordinates that capture the main features of an image and remain essentially unchanged through acceptable transformations. Here, essen tially unchanged means the hash value is consid ered close. For A, the set of admissible trans formations, we only consider JPEG compression with different quality levels. All other transforma tions, including filtering, are considered inadmissi ble manipulations that must be detectable by the system. However the proposed systems are flexi ble and can be used with other definitions of A. The larger transformation set means wider band for acceptance and hence higher rate of false ac ceptance.
2
The critical co-ordinates are found by taking the difference between the original image pixels and the corresponding low frequency (low pass) im age pixels, obtained by applying a discrete cosine transform (DCT), and keeping the co-ordinates of those differences which are above a certain thresh old. By doing this we essentially capture the high frequency edge co-ordinates of an image. To be more precise in selecting the final critical set, we take a range of images in an admissible transfor mation and use the intersection of all those critical sets as the final critical set in the hash value. To make a fair comparison, we fixed the size of the critical set by choosing the other parameters ap propriately. In order to optimize detection perfor mance, varying number of AC coefficients are in corporated in smoothing an image. The following section gives a brief description of discrete cosine transform.
2.1

Discrete Cosine Transform
Current standards for compression of still images [3] and moving images use DCT which represents an image as a superposition of cosine functions with different discrete frequencies. The trans formed signal is a function of two spatial dimen sions, and its components are called DCT coef ficients or spatial frequencies. DCT coefficients measure the contribution of the cosine functions at different discrete frequencies. DCT has been recommended by JPEG because of its excellent energy compaction property.
Our Image Hash Algorithm
In this section we give the description of our image hash algorithm. This method of hashing is based on finding the significant co-ordinates, which are considered at a range of acceptable compression levels. We call this set of points the critical set 8e for compres sion and keep this set as one of the parameters of the hash value. By keeping this critical set we not only avoid insignificant co-ordinates, but also reduce the length of hash. This critical set will be well estimated if many compression levels are considered.
Hash Generation Algorithm
1. Given an image I, apply a discrete cosine transform to produce the low pass image hL without sub-sampling. The low pass image using a discrete cosine transform could be ob tained by applying the forward discrete cosine transform, removing the high frequency coef ficients by making them 0, and then applying the inverse discrete cosine transform.
Hash Generation Algorithm
2. Let p be an appropriately chosen threshold.
3.
Compare the corresponding pixel values of I and hL to determine the set of all pixel co ordinates whose differences are above p. Let us denote this set of pixel co-ordinates as 80
3.
4. Assuming compression level of 25 to be used as the threshold to distinguish compression from other manipulations, JPEG compress image I at quality levels 75, 50, and 25 to produce the compressed images hs, Iso, and 12s·
3.
5. Apply steps (1)-(3) on compressed images hs, Iso, and hs to produce the set of pixel co ordinates 87S, 8so, and 82S, using the same p.
3.
6. Let us define a critical set 8e = 80 n 87S n 8so n 82S. Higher the number of compression levels are considered, the better the critical set 8e is approximated.
3.
7. Since we haven't used many compression lev els in determining the critical set 8e, a confidence interval must be set on the number of image became less smooth (close to original) and matching co-ordinates for authentication. hence the number of pixel differences above a cer tain threshold decreased. This led to reduced 8. Hash of an image will consist of wavelet basis used, Be, p, and t-a confidence measure.
Verification Algorithm
1. Upon receiving an image IT and its hash, ap ply the discrete cosine transform to produce the low pass image Ih. This is same as the step 1 above.
Compare the corresponding pixel values of IT
and Ih to determine the set of all pixel co ordinates whose differences are above the re ceived p. Let us denote this set of pixel co ordinates as BT•
If the number of matching co-ordinates in Be and Br belongs to the interval [lBel-t, IBel+t]
, the received image is considered to be authen tic.
4

Experimental Results

4.1

Objective and Experiment
As noted before the basic approach in deriving the critical set was to find a smooth version of the im age. In DCT based approach the smooth version could be obtained by considering a subset, for ex ample DC together with AC1 and AC2, and use the inverse transform to construct the smooth ver sion. The number of coefficients that were used to construct the smooth version was investigated in this experiment. AC coefficients were diagonally incorporated (ie. DC-AC5, DC-AC9, ... ). We kept the threshold p at a fixed value of 27, and evalu ated the size of the critical set as the AC coeffi cients were being added.
Observations
The higher the number of low frequency AC co efficients were incorporated in smoothing an im age, the lesser the number of critical points were found in the critical set. This was because when more AC coefficients were considered, the low pass 4 number of points in the critical set. Next we kept the size of the hash roughly equal, and evaluated the performance of manipulation detection with respect to various combinations of AC and DC coefficients (ie. DC-AC5, DC-AC9, ... ). Incorporating more number of AC coefficients in smoothing did improve manipulation detection for modifications such as compression at quality level of 10, and Gaussian noise addition. Performance deteriorated for FMLR with the addition of AC coefficients. Mixed results were found for Median filtering.
Observations
As we kept on adding AC coefficients, critical points found at the compression level of 25 de creased due to the closeness of compressed image and the low passed version of the compressed im age.
Observations
Since the compressed image had already under gone a low pass filtering, slight low pass filtering again wouldn't pick many high frequency points in the critical set. This reduced the number of points in the critical set as more and more AC coefficients were being added even if the threshold had been lowered. Since we included compression quality level of 25 in our critical set computation to give enough tolerance for compression, the property mentioned above limited us from going for higher number of AC coefficients being added if we wanted to have a reasonable size critical set.
Observations
From these experiments we found that for a fixed size hash, there was a trade off between the level of compression and the number of AC coef ficients considered in smoothing the image. For a fixed level of compression tolerance, adding more number of AC coefficients decreased the size of the hash. This in turn reduced the manipulation detection.
Observations
For a reliable system there must be a compro mise between the following:
Observations
• Size of the hash or critical set,
Observations
• Number of AC coefficients used in smoothing,
Observations
• Compression tolerance level.
Observations
The experiment we did on Lenna and Peppers images revealed that adding 44% of the AC coef ficients diagonally from left to right decreased the size of the critical set to 596 (from 738) and 541 (from 1291) even though the threshold had been reduced to 1. Almost a similar observation was found for Pills image. For Paper and Corrosion images, adding 56% of the AC coefficients diago nally from left to right decreased the size of the critical set from their original sizes. Tables 1-5 in appendix illustrates our experimental results.
Observations
This shows that the optimal percentages of AC coefficients that give the highest level of detection while keeping the size of the critical set roughly equal are 33% for Lenna, Peppers and Pills im ages, and 44% for Paper and Corrosion images. the same critical set. We have noticed this from some of our experiments. This is also not a very good key selection because the overlap between two critical sets derived from two sets of compres sion levels is almost close to 100%.
Low-pass Filter as a Key
For a fixed size critical set, two distinct filters pro duce more than 36% of non overlapping points. That is, by knowing a critical set produced using a filter, it is extremely hard to guess another crit ical set produced using a different filter. This is also evident from some experiments we have per formed. Since there are numerous filters we can choose by selecting different basis functions, keep ing the low pass filter (ie. filter and its properties) as a key is an attractive idea for avoiding attacks. The above analysis explains the limitations of incorporating more and more AC coefficients in smoothing an image in our critical set based hash 6 function surviving acceptable level of compression.
6.1

Size of Key Space p as a Key
We found that the optimum percentage of AC co efficients needed to maximize the manipulation de tection for an equal size hash were about 33% to Lenna, Peppers and Pills images and about 44% to Paper and Corrosion images.
Security Analysis

p as a Key
Though keeping p as a key is not a bad idea, it has a shortcoming. We believe the shortcoming is as follows.
p as a Key
1. If the algorithm to find the critical set is known or public except for the key p, it would not be difficult to guess p from an image crit ical set pair.
Compression Levels as Keys
Keeping compression levels as keys and then choosing the p that gives the correct size critical set will not only avoid attacks, but also protect p from being guessed. This is because choosing dif ferent compression levels does not always lead to
5
Since the maximum value of pixel value difference between the original image and the lowpass image is 255, p can take values ranging from 0 to 255. Keeping pa sO will include all pixel points as crit ical points and keeping p as 255 will include none of the pixel points as critical points. Therefore, the size of the key space of p is upper bounded by the value of 255.
Compression Levels as Keys
JPEG compression quality level range from 0 to 100. Choosing quality levels below certain value l may not produce good quality images and so lead to great proportion of insignificant critical points. Suppose l has been set to an appropriate quality level (close to 100), there are 100-l possible values to choose from. Since a quality level chosen to produce a set of points should not be repeated for producing another set of points, each level chosen must be distinct in the range of l to 100. If p (less than or equal to 100 -l + 1) levels are chosen, the size of the key space will be (100 -l + 1) (100 -l) ... (100 -l-p+ 2)) which is equal to l �g���;! i!
Low-pass Filter as a Key
In the case of DCT, there are 64 DCT coefficients available for each 8x8 block. In low pass filtering using DCT, if m high frequency coefficients are made 0 uniformly among all blocks, there are m possible keys. If the number of high frequency coefficients that are made 0 is varied among blocks and kept within the range of 1 to m, assuming n blocks are there, the size of the key space will be less than or equal to m n .
A Comparison
In this section we compare our scheme with the Battacharjee's [1] and Chun-Shien's [2] wavelet based authentication schemes with re spect to wavelets chosen, scales and size of filters used, computations involved, thresholds selected for compression tolerance, and the amount of re dundant information involved. Battacharjee's scheme uses Mexican-Hat wavelet which is isotropic in nature. Chun-Shien's method does not mention which wavelet is chosen. In our scheme, DCT with varying number of AC coefficients are chosen for smoothing.
A Comparison
Bathacharjee's scheme uses the parent child re lationship between the scales which are apart (not adjacent). Sizes of filters are never taken into con sideration. Chun-Shien's scheme uses the parent child relationship between adjacent scales. Since ours is a DCT based scheme, filter sizes or scales can not be changed.
A Comparison
Battacharjee's scheme involves a huge amount of computation. In Chun-shien's scheme, compu tation performance improves with an increase in scale. Our method also involves a lot of computa tion because of the application of DCT and IDCT.
A Comparison
To give provision for compression tolerance, Battacharjee's scheme must set the thresholds T and t appropriately. Chun-shien's scheme does not look at the performance with respect to differ ent thresholds. Our scheme should set the thresh old p for adjusting the size of the critical set and then decide on another threshold for giving com pression tolerance based on matching critical co ordinates.
6
Battacharee's scheme does not give any provi sion for frequency bands within each scale because Mexican-hat wavelet is used. Chun-shien's scheme uses information in the higher sub-bands which contains irrelevant information for distingushing JPEG compression, which is a lowpass filtering. Our scheme has been experimented incorporat ing varying percentage of low frequency AC co efficients.
8

Conclusion
In this paper, we have proposed a variant to the already existing wavelet based image authentica tion schemes using discrete cosine transform. The use of critical set has increased performance at the cost of more computations. We have showed that the optimal percentages of AC coefficients that give the highest level of detection while keeping the size of the critical set roughly equal are 33% for Lenna, Peppers and Pills images, and 44% for Paper and Corrosion images.

{'paper_id': '9772766', 'title': 'Compression tolerant DCT based image hash', 's2_url': 'https://api.semanticscholar.org/CorpusID:9772766', 'source': 'S2ORC'}