1Bull. Soc. Photogr. Imag. Japan. (2014) Vol. 24 No. 1: 1–5

Original Paper

Hierarchical Image Authentication Based on Reversible Data Hiding
Shoko Imaizumi* and Kanichi Taniguchi*

Abstract:

In this paper, we propose an image authentication based on hierarchical reversible data hiding. The proposed scheme decreases
the costs necessary to detect and locate tampered areas by using efficiently multiplexed layers. This scheme reduces both the payload size and the amount of hash operations. We improved the structure of layers and the division of blocks in the conventional
scheme. Performance analysis shows the validity of the proposed scheme.

Key words:

Authentication, Tamper detection, Tamper localization, Reversible data hiding, Hash function

1. Introduction
With the growth in computational performance, it has become
easy to modify digital images. Due to the increase in image
tampering, image authentication has become important. Many
tamper detection schemes have been studied to confirm image
authenticity.
By using reversible data hiding 1–4), tamper detection schemesthat recover the original image after authentication have been
proposed 5–8). The former schemes 5) 6) use highly costed compression based data hiding, while the latter schemes 7) 8) are freefrom compression techniques. This paper is focused on the latter
non-compression-based schemes and is especially aimed at improving the conventional scheme 8) in terms of the payload size
and the amount of hash operations.
The conventional scheme 8) detects tampered areas by comparing the hash values of recovered blocks with those extracted fromstego blocks. This scheme can easily embed the target data into
images and confirm image authenticity with accuracy. Moreover,it can detect not only tampering but also locate tampered areas inimages. However, the conventional scheme has two problems.
First, the embeddable pixels in each block are decreased because
the size of blocks gets smaller on the bottom layers. Second, theamount of hash operations increases, making the blocks smaller,
and the time for hash operations also increases. Therefore, we aim
not to reduce the size of the unit for embedding and solve theabove problems in the conventional scheme.
In this paper, we propose an efficient reversible image authentication that reduces both the payload size and the amount of hashoperations. The proposed scheme improves the structure of layers
and the division of blocks in the conventional scheme. It decreases
costs necessary to detect and locate tampered areas by using hierarchically multiplexed layers. Our scheme is based on reversible

data hiding. We give simulation results and show the validity ofthe proposed scheme.

2. Conventional Scheme
A conventional scheme 8) can be a reversible image authentication that detects tampering and locates tampered areas efficiently.
This scheme decreases costs through coarse-to-fine tamper localization by hierarchical data hiding, encipherment of only the top
layer rather than all data among all layers, and the use of reversible data hiding without highly costed compression techniques.
2.1 Data Hiding
We prepare image I with X × Y pixels and set I as Il.
1) l := 0, c := 0.
2) Fig. 1 shows the order for dividing image Il, hierarchically. We
divide image Il into Cl blocks in the l-th layer. The size of eachblock is Xl × Yl pixels.
Cl = [ X | Xl ] [ Y | Yl ],		(1)
l = 0, 1, ..., L – 1,
where L is the number of layers.
3) N-bit hash value hl,c of block Bl,c, which is given as,hl,c = {hl,c,n | hl,c,n  {0, 1}},		
(2)
c = 0, 1, ..., Cl – 1,   n = 0, 1, ..., N – 1,
is embedded into Bl,c itself by using reversible data hiding 4).
Stego block B̂l,c is obtained. Note that hL–1,0 is encrypted by using an encryption key and is embedded into the image forhigher security.
4) c := c + 1.
a) If c = C l , combine all stego blocks B̂l,c . Stego image Îl is
obtained.
b) Else, return to Step 3).
5) l := l + 1.

Received 19th, September 2013; Accepted 5th, March 2014
*Graduate School of Advanced Integration Science, Chiba University, 1-33 Yayoicho, Inage-ku, Chiba-shi, Chiba 263-8522, Japan

2

Bull. Soc. Photogr. Imag. Japan. Vol. 24 No. 1 (2014)

Fig. 1.

Hierarchical division in the conventional scheme 8) (L = 3).

a) If l := L, stego image Î is obtained.
b) Else, c := 0, Il := Îl–1, and return to Step 2).
2.2 Tamper detection and localization
We investigate stego image Î with X × Y pixels and set Î as Îl.
1) l := L – 1, c := 0.
2) We divide stego image Îl into Cl blocks in the l-th layer, as
shown in Fig. 1.
3) a) If the target block is determined as a genuine block in l +1-th layer except in l = L – 1, go to 6).
b) Else, embedded hash value hl,c, which is given as Eq. (2), is
extracted from stego block B̂l,c by using reversible data hiding 4).
Block Bl,c is restored. Note that in case of l = L – 1, hL–1,0 is obtained by decryption using the key used in encryption.
4) N-bit hash value h l,c is calculated from restored block Bl,c.
h l,c = {h l,c,n | h l,c,n  {0, 1}}.
(3)5) Extracted hash value hl,c is compared with h l,c.
a) If hL–1,0 = hL–1,0, BL–1,0 is determined to be a genuine block,that is, restored image I is an original image without tampering. Exit this procedure.
b) If hl,c = h l,c (l ≠ L – 1), Bl,c is determined to be a genuine block.
c) Else, Bl,c is determined to be a tampered block.
Note that this step means tamper detection in l = L – 1 andtamper localization in l ≠ L – 1.
6) c := c + 1.
a) If c = Cl, combine all blocks Bl,c. Image Il is obtained.
b) Else, return to step 3).
7) l := l – 1,a) If l = –1, all tampered blocks are obtained.
b) Else, c := 0, Îl := Il+1, and return to step 2).

2.3 Problems of the conventional scheme
The conventional scheme 8) using hash operations can detect
tampering without multiple encryption procedures. It can also
localize the positions of tampering by using the hierarchicalstructure. This scheme, however, increases both the payload size
and the amount of hash operations when given a large number for
hierarchy L.
In the next section, we propose an efficient scheme for composing a hierarchical structure. Our scheme reduces the above problems in the conventional scheme.

3. Proposed Scheme
In this section, we describe a novel authentication scheme basedon reversible data hiding. The proposed scheme efficiently introduces a multiplex hierarchy to reduce both the payload size andthe amount of hash operations. In this paper, we suppose that we
divide an original image into 16 blocks. In case of 16 blocks, thenumber of layers L is four. Note that even if an image is tampered
in multiple blocks, our scheme can correctly detect and locate thetampered blocks by the combination of these multiplexed layers.
3.1 Data Hiding
We prepare image I with X × Y pixels and set I as Il.

1) l := 0, m := 0.
2) We divide image Il into 16 blocks and assign numbers to them,as shown in Figs. 2 and 3. The size of each block is [X /4 ×
Y /4] pixels.
a) If l = 0, assign each block B 0,c to groups G 0,m , as shown in
Fig. 4(a).
G 0,0 = {B 0,0, B 0,5, B 0,10, B 0,15},(4)
G 0,1 = {B 0,1, B 0,6, B 0,11, B 0,12},(5)
G 0,2 = {B 0,2, B 0,7, B 0,8, B 0,13},(6)
G 0,3 = {B 0,3, B 0,4, B 0,9, B 0,14}.
(7)b) If l = 1, assign each block B1,c to groups G1,m , as shown in
Fig. 4(b).
G1,0 = {B1,0, B1,4, B1,8, B1,12},(8)
G1,1 = {B1,1, B1,5, B1,9, B1,13},(9)
G1,2 = {B1,2, B1,6, B1,10, B1,14},(10)
G1,3 = {B1,3, B1,7, B1,11, B1,15}.
(11)c) If l = 2, assign each block B2,c to groups G 2,m , as shown in
Fig. 4(c).
G 2,0 = {B2,0, B2,1, B2,2, B2,3},(12)
G 2,1 = {B2,4, B2,5, B2,6, B2,7},(13)
G 2,2 = {B2,8, B2,9, B2,10, B2,11},(14)
G 2,3 = {B2,12, B2,13, B2,14, B2,15}.
(15)d) If l = 3, assign all blocks B3,c to group G3,0, as shown in Fig.
4(d).
G 3,0 = {B3,0, B3,1, B3,2, B3,3, B3,4, B3,5, B3,6, B3,7, B3,8,(16)
	   B3,9, B3,10, B3,11, B3,12, B3,13, B3,14, B3,15}.
Note that the number of groups Ml is one in l = 3, while that isfour in l = 0, 1, and 2.

Imaizumi and Taniguchi   Hierarchical Image Authentication Based on Reversible Data Hiding

3

Fig. 2. Division of image.

Fig. 3.

Block numbers.

3) N-bit hash value hl,m of group Gl,m , which is given as,hl,m = {hl,m,n | hl,m,n  {0, 1}},		
(17)
n = 0, 1, ..., N – 1.
is embedded into Gl,m itself by using reversible data hiding 4).
Stego group Ĝl,m is obtained. Note that h3,0 is encrypted by using an encryption key and is embedded into the image forhigher security.
4) m := m + 1.
a) If m = Ml, we combine all stego groups Ĝl,m. Stego image Îlis obtained.
b) Else, return to step 3).
5) l := l + 1.
a) If l = 4, stego image Î is obtained.
b) Else, m := 0, Il := Îl–1, and return to step 2).
3.2 Tamper detection and localization
We investigate stego image Î with X × Y pixels and set Î as Îl.
1) l := 3, m := 0.
2) We divide stego image Îl into 16 blocks and assign numbers tothem, as shown in Figs. 2 and 3, and assign each block Bl,c togroups Gl,m , as shown in Fig. 4.
3) Embedded hash value hl,m of original group Gl,m , which is
given as Eq. (17), is extracted from stego group Ĝl,m by using
reversible data hiding 4). Group Gl,m is restored. If l = 3, h3,0 is
obtained by decryption using the key used in encryption.
4) N-bit hash value h l,m is calculated from restored group Gl,m.
h l,m = {h l,m,n | h l,m,n  {0, 1}}.
(18)5) Extracted hash value hl,m is compared with h l,m.
a) If h3,0 = h 3,0, G 3,0 is determined to be a genuine group, thatis, restored image I is an original image without tampering.
Exit this procedure.

Fig. 4.

Hierarchical division and grouping in the proposed scheme.

b) If hl,m = h l,m (l ≠ 3), Gl,m is determined to be a genuine group.
c) Else, Gl,m is determined to be a tampered group.
Note that this step means tamper detection in l = 3 and tamper
localization in l ≠ 3.
6) m := m + 1.
a) If m = Ml, combine all groups Gl,m. Image Il is obtained.
b) Else, return to step 3).
7) l := l – 1.
a) If l = –1, all tampered groups are obtained.
b) Else, m := 0, Îl := Il+1, and return to step 2).

4

Bull. Soc. Photogr. Imag. Japan. Vol. 24 No. 1 (2014)

Fig. 5. 256 × 256-sized grayscale images from SIDBA 9).
Table 1.
Layer

Payload size [bits].
Proposed

Table 3. Experimental Conditions.
Conventional

8)

Image size [pixels]

256 × 256
SHA-256

L0

256

256

Hash function

L1

1024

1024

L2

1024

4096

Hash length N [bits]

L3

1024

—

Total

3328

5376

Number of layers L

256
Proposed

Conventional 8)

43

Table 2. Amount of hash operations [times].
Layer

Proposed

Conventional 8)

L0

1

1

L1

4

4

L2

4

16

L3

4

—

Total

13

21

8) Determine the blocks, all of whose groups Gl,m have been tampered, as the tampered blocks.

Fig. 6.

Stego images by using the proposed scheme and the conventional
scheme 8).

3.3 Feature
Tables 1 and 2 show comparisons of the payload size and theamount of hash operations, respectively. Our scheme has reduced
both payload and hash operations by 38%, respectively, comparedwith the conventional scheme 8). A single hash operation is needed
for tamper detection in both the proposed and the conventional
schemes. In this example, the amount of hash operations for tamper localization is 12 times in the proposed scheme, while that is
20 times in the conventional scheme.

4. Experimental Results
The proposed scheme was evaluated with 256 × 256-sized, i.e.,
X = Y = 256, 8-bit grayscale bitmap images from SIDBA 9), as shownin Fig. 5. We summarize the conditions of the experiments inTable 3.
Figs. 6(a) and 6(b) show a couple of examples of stego images
for the proposed scheme and the conventional scheme 8), respectively. We summarize the evaluation for the stego images by
PSNR in Fig. 7. The PSNR for the stego image “Lenna” using the

Fig. 7.

PSNRs of the stego images.

proposed scheme was 42.11 dB, while that using the conventional
scheme was 35.43 dB. In the cases for “Airplane” and “Text,” theproposed scheme similarly improved the PSNR over the conventional scheme. Thus, the proposed scheme is efficient for embed-

Imaizumi and Taniguchi   Hierarchical Image Authentication Based on Reversible Data Hiding

5

Acknowledgement
This work was supported by the Photographic Research Fundof Konica Minolta Science and Technology Foundation.

References

Fig. 8.

Result of tamper localization.

ding data.
For example, a tampered area is shown in Fig. 8(a). In this case,the tampered blocks are detected as shaded ones in the proposed
scheme, as shown in Fig. 8(b).

5. Summary
We proposed an efficient image authentication based on reversible data hiding. The proposed scheme introduces hierarchicallymultiplexed layers to detect and locate tampered areas. This
scheme decreases both the payload size and the amount of hashoperations. We improved the structure of layers and the divisionof blocks in the conventional scheme. Through comparison withthe conventional scheme, we showed the validity of the proposed
scheme.

1) J. Tian, “Reversible data embedding using a difference expansion”,
IEEE Trans. Circuits Syst. Video Technol., 13(8), 890–896 (2003).
2) A. M. Alattar, “Reversible watermark using the difference expansionof a generalized integer transform”, IEEE Trans. Image Process.,
13(8), 1147–1156 (2004).
3) D. M. Thodi and J. J. Rodriguez, “Expansion embedding techniques
for reversible watermarking”, IEEE Trans. Image Process., 16(3),721–730 (2007).
4) H. L. Jin, M. Fujiyoshi, and H. Kiya, “Lossless data hiding in thespatial domain for high quality images”, IEICE Trans. Fundamentals., E90-A(4), 771–777 (2007).
5) J. Fridrich, M. Goljan, and R. Du, “Invertible authentication”, Proc.
SPIE, 4314, 197–208 (2001).
6) M. U. Celik, G. Sharma, and A. M. Tekalp, “Lossless watermarking
for image authentication: a new framework and an implementation”,
IEEE Trans. Image Process., 15(4), 1042–1049 (2006).
7) K. Watanabe, M. Fujiyoshi, and H. Kiya, “Image Authentication
with Access Control Based on Reversible Data Hiding”, Technicalreport of IEICE, 110(115), 81–86 (2010), (in Japanese, ICSS2010-25).
8) S. Han, M. Fujiyoshi, and H. Kiya, “A reversible image authentication method without memorization of hiding parameters”, IEICE
Trans. Fundamentals., E92-A(10), 2572–2579 (2009).
9) M. Onoe, M. Sasaki, and Y. Inamoto, “SIDBA Standard Image
Data Base”, MIPC Report, 79(1) (1979).