15 Polynomial-Based Image Sharing

The concept of secret sharing comes from the method of secret key management and was first seen in the following works [1, 7]. The secret's owner wants to share the secret with other participants, but no participants can obtain the secret alone. When some of the participants work together, the secret is then revealed. From a technical viewpoint, this secret sharing scheme may also be referred to as the (t, n)-threshold, where t denotes the threshold value that will reveal the secret and n is the total number of holding shadows. In this method, when a secret is given, it must be divided into n shadows and it is then reconstructed by t or more shadows, possessed by the shadow holders; no information can be conjectured by fewer than t shadows. In the wake of this cryptographic application proposal, many related methods were further proposed to enrich secret sharing diversity in both theoretical and practical arenas [4, 6, 8, 12].

Visual security was proposed by Naor and Shamir [6] in 1994, where an image could be reconstructed by superimposing two shares. The shares issued in this scheme are made up of random binary patterns. The target secret, recognized by the human visual system, is finally stacked by the (t, n)-threshold scheme. One of the main advantages, in this scheme, is that it does not require complicated computations, which traditional numeric cipher-text in secret decryption does, while the sizes of the enlarged shares, and target secrets are left the same. Thien and Lin [8] proposed an applied secret image scheme for image embedding to improve upon Naor and Shamir's method. The concealment of a secret image avoids cipher-based attacks on the basis of stego-image imperceptibility. In 2006, Horng et al. uncovered another way to cheat the (t, n)-threshold under visual cryptography (VC) applications [3]. In their proposal, a scenario was successfully put forward showing that shareholders were able to collaborate with each other by sending fake shares to other shareholders. Accordingly, the final target secret image was different from the genuine one, corrupting the secret sharing system.

Steganography is a kind of data hiding technique that provides another method of security protection for digital image data. The purpose of steganography is to embed secret data in preselected meaningful images, called cover images, with people being visually unaware of the secret's existence. Numerous schemes have been developed to achieve successful data hiding [2, 5]. To prevent the fake stego-image from the dishonest participants, Lin and Tsai [4] authored an authentication-based steganography study, where their detection technique tested whether the offered shares were genuine or not. In their scheme, parity checks were applied to prevent the modified shares from malicious attacks. Later on, in 2007, Yang et al. [12] enhanced the mechanism of Lin and Tsai by proposing a revised scheme in which more detailed fake shares were created so that they would be detected by those malicious shareholders in the target secret image (t, n)-threshold system, thus acting as a deterrent.

In 2008, Wang et al. [10] took advantage of the CRC (Cyclic Redundant Code) in conjunction with the hash function to make authentication-based steganography more robust, in order to prevent the attacks of fake share offerings. In addition to making it more robust, both the capacity and the image quality remain comparable to the scheme suggested by the scheme in [12]. In this chapter, we introduce the polynomial-based image sharing scheme by reviewing some preliminaries and related works and depicting Wang et al.'s approach. Moreover, some improvements of Wang et al.'s approach are proposed in this chapter.

The presentation of this chapter is organized as follows. In Section 15.2, the concept of the polynomial-based sharing scheme is introduced. In Section 15.3, we introduce some preliminaries and related works about the polynomial-based image sharing scheme. Wang et al.'s scheme and its improvements are presented in Section 15.4. Observations and experiments of benchmark images are presented and discussed in Section 15.5. Finally, conclusions are offered in Section 15.6.

15.2 Polynomial-Based Sharing Scheme

15.2.1 Shamir's Secret Sharing Scheme

A (t, n)-threshold scheme is a method of sharing a secret among n participants such that any subset consisting of t participants can reconstruct the secret, but no subset of smaller size can reconstruct the secret. The first method was provided in 1979 by Shamir [7] and is known as Shamir's secret sharing scheme. In the initial state, a dealer chooses a large prime number p, and makes p public. The following calculation is performed on Z_p: A secret, s ∈ Z_p exists, so the dealer randomly generates a (t-1)th degree polynomial, in Z_q:

q (x) \equiv x + q 1 x + q 2 x 2 + \dots + q t - 1 x t - 1 (m o d p)

$q (x) \equiv x + q_{1} x + q_{2} x^{2} + \dots + q_{t - 1} x^{t - 1} (m o d p)$

where q(0) = s is the secret. The dealer distributes the shadow, y_i ≡ q(x_i)(mod p) to node P_i, where x_i is the ID number for P_i.

Suppose that t participants get together to reconstruct the polynomial. Also, assume that their pairs are (x₁,y₁), (x₂,y₂), ⋯, (x_t,y_t). The polynomial q(x) can be reconstructed by solving the following equation:

⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ 11 ⋮ 1 x 1 x 2 ⋮ x t \dots \dots ⋱ \dots x t - 1 1 x t - 1 2 ⋮ x t - 1 t ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ s q 1 ⋮ q t - 1 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ \equiv ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ y 1 y 2 ⋮ y t ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ (m o d p)

$[\begin{matrix} 1 & x_{1} & \dots & x_{1}^{t - 1} \\ 1 & x_{2} & \dots & x_{2}^{t - 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & x_{t} & \dots & x_{t}^{t - 1} \end{matrix}] [\begin{matrix} s \\ q_{1} \\ ⋮ \\ q_{t - 1} \end{matrix}] \equiv [\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{t} \end{matrix}] (m o d p)$

The equation has a unique solution if the determinant of the matrix is nonzero mod p. It can be shown that the determinant of the matrix is nonzero mod p if all x_i, i = 1, 2,⋯, t, are different. After the polynomial is reconstructed, the secret s is obtained by the output of q(0).

15.2.2 Lagrange Interpolation Scheme

An efficient method to obtain the sharing polynomial f is to use the Lagrange interpolation. Assume that the pairs (x₁, y₁), (x₂, y₂),⋯, (x_t, y_t) are used to reconstruct the polynomial q(x). For k = 1, 2,⋯, t, let

l k (x) = \prod i = 1, i \neq k x - x i x k - x i m o d p

$l_{k} (x) = \prod_{i = 1, i \neq k} \frac{x - x_{i}}{x_{k} - x_{i}} m o d p$

We know that

l k (x j) = {1, w h e n k = j 0, w h e n k \neq j

$l_{k} (x_{j}) = {\begin{matrix} 1, w h e n k = j \\ 0, w h e n k \neq j \end{matrix}$

Then, the Lagrange interpolation polynomial is formed as follows:

q' x = \sum t k = 1 y k l k m o d p

$q_{x}^{'} = \sum_{k = 1}^{t} y_{k} l_{k} m o d p$

Because y_i ≡ q′(x_i)(modp) for i = 1, 2,⋯, t and q′(x) has degree t − 1, q′(x) is equal to the polynomial q(x). Finally, the secret s can be obtained by evaluating q(x) at x = 0. That is,

s = \sum t k = 1 y k \prod t j = 1, j \neq b - x i x k - x i m o d p

$s = \sum_{k = 1}^{t} y_{k} \prod_{j = 1, j \neq b}^{t} \frac{- x_{i}}{x_{k} - x_{i}} m o d p$

In fact, all coefficients in q(x) can be seen as secrets. We show an example for the Lagrange interpolation polynomial.

Example 1.

Take a (2, 4)-threshold scheme. In the share generation phase, assume that the pixels of the target secret image S indexed in order of left-to-right and top-to-down is S_i, I = 0, 1, 2, ⋯, n. The first two pixels, for instance, S₀ = 100 and S₁ = 200 are set in this case. First of all, a polynomial of q(x) = 200x + 100 mod 251 is given according to the S′is ${S^{'}}_{i} s$ . Compute the shares y′js ${y^{'}}_{j} s$ associated with each participants as y₁ = q(x₁=1) = 49, y₂ = q(x₂=2) = 249, y₃= q(x₃=3) = 198, and y₄ = q(x₄=4) = 147, where x′is ${x^{'}}_{i} s$ are the identity numbers of the four participants. Next, consider the recovery of the pixels of the target secret image in this case. In the (2, 4)-threshold scheme, any two participants who own the shares y′js ${y^{'}}_{j} s$ can gather to recover the secret, for example, the participants nos. x₂ and x₄. There are two pairs of (x₂, y₂) = (2, 249) and (x₄, y₄) = (4, 147) offered from the participants. In such a way that a polynomial of q′(x) is constructed as follows:

g (x) = (249 \times ( x - 4 ) ( x - 1 ) + 147 \times ( x - 2 ) ( x - 4 )) m o d 251 = (249 \times (- 2) - 1 \times (x - 4) + 147 \times (2) - 1 \times (x - 2)) m o d 251 = (200 x + 100) m o d 251

$\begin{array}{l} g (x) = (249 \times \frac{(x - 4)}{(x - 1)} + 147 \times \frac{(x - 2)}{(x - 4)}) m o d 251 \\ = (249 \times {(- 2)}^{- 1} \times (x - 4) + 147 \times {(2)}^{- 1} \times (x - 2)) m o d 251 \\ = (200 x + 100) m o d 251 \end{array}$

Following up the result, the first two pixels of the target secret image, S₀ = 100 and S₁ = 200 are obtained from the coefficients of q′(x) = 200x + 100 mod251.

15.3 Preliminaries and Related Works

15.3.1 Thien-Lin Scheme

The (t, n)-threshold scheme in visual cryptography was proposed by Naor and Shamir [6], where the target secret (image) could only be recognized by the human eye if there were exactly t or more than t share-images stacked. However, the share-images generated could only reveal one target secret. When there are more than 2 target secrets, the numbers of share-images required, increases. As a result, the occupied share-images, held by participants, also increase. Inspired by these observations, Thien and Lin (Thien-Lin scheme) [8] proposed a specific method to accommodate a higher number of share-images, with the normal storage requirements, using LaGrange polynomial construction. In this method, there are a total of n share-images, with each of them being only 1t $\frac{1}{t}$ times the target secret image. This is also done in the ( t, n)-threshold scheme.

15.3.2 Lin-Tsai Scheme

In [4], Lin and Tsai (Lin-Tsai scheme) proposed a scheme of sharing image, where the requirements of capacity and detecting ability are further considered when compared to the study of [8]. Similarly, a polynomial of q(x)=(a0+a1x+a2x2+⋯+ai−1xi−1) $q (x) = (a_{0} + a_{1} x + a_{2} x^{2} + \dots + a_{i - 1} x^{i - 1})$ of degree t-1 is applied upon the concept of the (t, n)-threshold scheme. The q(x) is then devised for exact reconstruction when t pairs of (x_i, q(x_i)) are offered among n share holders, where x_i is one of the pixels of a pixel-value and q(x_i) is the share held in the share holder. Accordingly, the pixels of the target secret image can be obtained from the coefficients of the new one of q′(x) via the (t, n)-threshold polynomial construction. The procedures in [4] are briefly given as follows:

Images

FIGURE 408.15
The format of B_ij, where x_i, w_i, v_i, and u_i are represented as binary pattern.

Notations:

q(x): The (t − 1)-degree polynomial of q(x) = (a₀ + a₁x + a₂x² + … + a_t−ix^t−1) mod p, where p = 251.

S : The target secret image with the size of m × m. The pixel S_i ∈ [0, 250] in S, 1≤ i ≤ m². It is caught by up-to-down and left-to-right in order.

I_j: The jth cover image with the size of 2m× 2m pixels. There are m² blocks, B′ijs ${B^{'}}_{i j} s$ , where each one is the size of 2 × 2 containing four pixels as x_i, w_i, v_i, and u_i in the order of left-to-right and up-to-down and 1 ≤ i ≤ m² and 1 ≤ j ≤ n. The pixel format of B_ij is shown in Figure 15.1.

Î_j: The jth stego-image with the size of 2m × 2m. There are m² blocks, Bˆij' ${\hat{B}}_{i j}'$ s. Bˆij ${\hat{B}}_{i j}$ is stego-block when the secret is embedded the B_ij. The corresponding pixels in Bˆij ${\hat{B}}_{i j}$ to B_ij is xˆi, wˆi,vˆi, ${\hat{x}}_{i}, {\hat{w}}_{i}, {\hat{v}}_{i},$ and uˆi ${\hat{u}}_{i}$ , respectively.

b_i: Generate a random bit-string with the form of (b1,b2, ⋯,bm2) $(b_{1}, b_{2}, \dots, b_{m^{2}})$ , where 1 ≤ i ≤ m².

The procedure to generate the stego-image, named as Proc-Lin-Tsai, is briefly given in the following:

Procedure Proc-Lin-Tsai

Input: S, I_j, j = 1, 2,⋯, n.

Output: I, j = 1, 2, •⋯, n.

Step 1. Generate the random bit string (b1,b2, ⋯,bm2) $(b_{1}, b_{2}, \dots, b_{m^{2}})$ .

Step 2. Set a₀=S_i, i ∈ [1, m²]. For each S_i chooses a (t−1)-degree polynomial q(x) = (a₀ + a₁x + a₂x² + •⋯ + a_i−1xⁱ⁻¹) mod p, where randomly choose t-1 value a₁ , a₂ ,⋯, a_i− 1 under the modulo p. Calculate y_i = q_i(x_i), where x_i is obtained and defined from x_i in the I_j and represent y_i as the bit string with the form of y_i = (y_i1, y_i2, ⋯ , y_i8).

Step 3. Generate the stego-block, Bˆij ${\hat{B}}_{i j}$ , comprised of the four bit strings as

xˆi=(xi1,xi2,⋯,xi8) ${\hat{x}}_{i} = (x_{i 1}, x_{i 2}, \dots, x_{i 8})$ ,

ŵ_i = (w_i1; w_i2; ⋯ ; w_i5, b_′i, y_i1; y_i2),

vˆi=(vi1,vi2,⋯,vi5,yi6,yi7,yi8) ${\hat{v}}_{i} = (v_{i 1}, v_{i 2}, \dots, v_{i 5}, y_{i 6}, y_{i 7}, y_{i 8})$ ,

and û_i =(u_i1, u_i2, ⋯ , u_i5, y_i6, y_i7, y_i8),

where b′i ${b^{'}}_{i}$ is the parity bit, which is chosen to make wˆi ${\hat{w}}_{i}$ including the corresponding bit-string b_i. The format of stego-block Bˆij ${\hat{B}}_{i j}$ is shown in Figure 15.2.

Images

FIGURE 15.2
The format of stego-block Bˆij ${\hat{B}}_{i j}$ with the size of 2 × 2 gray-level pixels.

Images

FIGURE 15.3
Stego-block Bˆij ${\hat{B}}_{i j}$ used in Yang et al. which is revised from Figure 15.2, where hash is used in the pixel of wˆi=(wi1,⋯,wi5,hi,yi3,yi4) ${\hat{w}}_{i} = (w_{i 1}, \dots, w_{i 5}, h_{i}, y_{i 3}, y_{i 4})$ .

Step 4. Collect Bˆij ${\hat{B}}_{i j}$ generated in the Step 3 to create stego-image Î_j.

15.3.3 Yang et al.'s Scheme

As observed from the Lin-Tsai scheme, the fake shares can be easily made by the manner of fixing the parity bit b′i ${b^{'}}_{i}$ . For example, if aˆi=(wi1,wi2,⋯,wi5,b′i,yi1,yi2)=(0,0,1,1,0,1,1) ${\hat{a}}_{i} = (w_{i 1}, w_{i 2}, \dots, w_{i 5}, {b^{'}}_{i}, y_{i 1}, y_{i 2}) = (0, 0, 1, 1, 0, 1, 1)$ , the parity bit b′ $b^{'}$ is all the same when the original wˆi ${\hat{w}}_{i}$ is changed to a new wˆi ${\hat{w}}_{i}$ as wˆi=(1,0,1,1,1,0,0,1) ${\hat{w}}_{i} = (1, 0, 1, 1, 1, 0, 0, 1)$ . In such a way, the malicious attackers can easily modify wˆ′is ${\hat{w}}^{'}_{i} s$ in the stego-image to pass the authentication detection. As a result, the revelation of the target secret image is not a right one. Next, Yang et al. [12] proposed a revised version to set a new check function, e.g., hash function, instead of parity bit in [4]. The stego-block Bˆij ${\hat{B}}_{i j}$ in [4] is then revised as the format shown in Figure 15.3. As analyzed in Yang et al., the probability of passing the detection with the fake share offers is (12)m2 ${(\frac{1}{2})}^{m^{2}}$ .

15.3.4 Inverted Pattern LSB Scheme

In order to conceal the existence of shadow data, steganographic methods are used to keep the shadows imperceptible. The steganographic method is a kind of data hiding technique that embeds secret data in preselected meaningful images, called cover images, with people being visually unaware of the secret's existence. One common technique to achieve the data hiding is the LSB-based approach, in which secret data are embedded by directly replacing the least significant bits (LSBs) with equal bits of the secret for each pixel. Moreover, some papers applied various strategies to improving the quality of stego-images generated by LSB-based approaches. In 2008, Yang [11] proposed an Inverted-Pattern-LSB information hiding algorithm (IPLA for short) to further highlight the quality of the stego-image. His method combines the idea of processing secret messages before embedded and processing the stego-image after embedding. Before embedding, the secret is transformed into a suitable format so as to benefit the next embedding step. Moreover, the bits that are used to record the transformation are the critical key in the course of the secret revelation. The IPLA algorithm is shown below, which was applied in Wang et al.'s scheme.

Inverted-Pattern-LSB Algorithm (H, S, k, n)

Input: A cover image H and a secret string S for k-bit LSB substitution, z is the number of sections.

Output: A stego-image and an inverted pattern P.

Step 1. Partition both H and S into z sections evenly. Let H = H₀, H₁, ⋯, H_z-1, S=S₀,S1,⋯,S_z-1 and R=R₀,R₁,⋯R_z-1, where R is the replaced string of H. Also, let the inverted pattern P = p₀,p₁, ⋯, p_z-1, where p_i is a bit, for i = 0,1, ⋯, z −1.

Step 2. For i = 0 to z − 1

If MSEsiRi ≤ MSEsiR¯¯¯i $M S E_{s_{i} R_{i}} \leq M S E_{s_{i} {\bar{R}}_{i}}$

Then p_i =0

Else p_i = 1

Step 3. For i = 0 to z − 1

If p_i =0

Then Embed S_i into H_i

Else embed S_i into H_i

Step 4. Return the inverted pattern P.

15.3.5 Scalable Secret Image Sharing

The conventional secret image sharing (SIS) scheme, such as the Thien-Lin scheme [8], only has the threshold property that recovers either the entire image or nothing. For the ( t, n)-SIS scheme, the target secret image could only be reconstructed by only t or more than t qualified participants. This limits its possible applications. Recently, Wang and Shyu recommended adding the scalable decoding capability (the scalability) into the threshold scheme [9]. The so-called scalability is that the amount of secret information is proportional to the number of shadows used in reconstruction. Wang and Shyu constructed a polynomial based (2, n) scalable SIS (SSIS) scheme, which not only had the threshold property but also the scalability. The clarity of an image in [9] is measured in terms of three modes: the multisecret mode (spatially partitioning the target image into disjoint subimages), the priority mode (dividing the target image according to the bitplanes), and the progressive mode (combining the multisecret mode and the priority mode). To extend Wang and Shyu's (2, n)-SSIS scheme, Yang and Huang proposed (t, n)-SSIS schemes where a qualified set of participants consists of any t participants [13]. Two approaches were proposed for a general construction for any t, 2 ≤ t ≤ n. For t = 2, Approach 1 has the lesser shadow size than Wang and Shyu's (2, n)-SSIS scheme, and Approach 2 is reduced to Wang and Shyu's (2, n)-SSIS scheme. The following is the shadow constructing algorithm of their Approach 1.

Shadow Constructing Algorithm

Input: a secret image O.

Output: n shadows S_i, i = 1, 2,⋯, n.

Step 1. Divide image O into (nt) $(\begin{array}{l} n \\ t \end{array})$ subimages O_x, x =1.2, ⋯, (nt) $(\begin{array}{l} n \\ t \end{array})$ by one of the three modes.

Step 2. For every image O_x, use a polynomial-based (t,t)-SIS scheme to create t subshadows (O1x,O2x,⋯,Otx) $(O_{x}^{1}, O_{x}^{2}, \dots, O_{x}^{t})$ .

Step 3. Set S₁ = S₂ = ⋯= S_n = Φ.

Step 4. Choose a binary matrix B_n,t = [b_i,j].

Step 5. For j = 1 to (nt) $(\begin{array}{l} n \\ t \end{array})$

Set y =1;

For i = 1 to n

If b_i,j = 1 then Oˆij=Oyy ${\hat{O}}_{j}^{i} = O_{y}^{y}$ and y = y + 1.

else Oˆij=Φ ${\hat{O}}_{j}^{i} = Φ$ .

Step 6. (nt)S1=∪j=1Oij, i=1,2,⋯,n $\begin{array}{r} (\begin{array}{l} n \\ t \end{array}) \\ S_{1} = \cup_{j = 1} & O_{j}^{i}, i = 1, 2, \dots, n \end{array}$

The binary matrix B_nt = [b_i,j] is a (nt) $(\begin{array}{l} n \\ t \end{array})$ matrix, where b_i,j ∈[0,1], 1 ≤ i ≤ n, and 1 ≤ i ≤ (nt) $(\begin{matrix} n \\ t \end{matrix})$ . Every column vector has a Hamming weight t. For example, the matrix B_nt=B₄₃ of a (3, 4)-SSIS scheme is

B 4, 3 = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ b 1, 1 b 2, 1 b 3, 1 b 4, 1 b 1, 2 b 2, 2 b 3, 2 b 4, 2 b 1, 3 b 2, 3 b 3, 3 b 4, 3 b 1, 4 b 2, 4 b 3, 4 b 4, 4 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ 1110110110110111 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥

$B_{4, 3} = [\begin{array}{l} b_{1, 1} & b_{1, 2} & b_{1, 3} & b_{1, 4} \\ b_{2, 1} & b_{2, 2} & b_{2, 3} & b_{2, 4} \\ b_{3, 1} & b_{3, 2} & b_{3, 3} & b_{3, 4} \\ b_{4, 1} & b_{4, 2} & b_{4, 3} & b_{4, 4} \end{array}] = [\begin{array}{l} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{array}]$

The corresponding matrix [Oˆij] $[{\hat{O}}_{j}^{i}]$ is created as follows.

[O ˆ i j] = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ O ˆ 11 O ˆ 21 O ˆ 31 O ˆ 41 O ˆ 12 O ˆ 22 O ˆ 32 O ˆ 42 O ˆ 13 O ˆ 23 O ˆ 33 O ˆ 43 O ˆ 14 O ˆ 24 O ˆ 34 O ˆ 44 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ O 11 O 21 O 31 ϕ O 12 O 22 ϕ O 32 O 13 ϕ O 23 O 33 ϕ O 41 O 24 O 34 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥

$[{\hat{O}}_{j}^{i}] = [\begin{array}{l} {\hat{O}}_{1}^{1} & {\hat{O}}_{2}^{1} & {\hat{O}}_{3}^{1} & {\hat{O}}_{4}^{1} \\ {\hat{O}}_{1}^{2} & {\hat{O}}_{2}^{2} & {\hat{O}}_{3}^{2} & {\hat{O}}_{4}^{2} \\ {\hat{O}}_{1}^{3} & {\hat{O}}_{2}^{3} & {\hat{O}}_{3}^{3} & {\hat{O}}_{4}^{3} \\ {\hat{O}}_{1}^{4} & {\hat{O}}_{2}^{4} & {\hat{O}}_{3}^{4} & {\hat{O}}_{4}^{4} \end{array}] = [\begin{matrix} O_{1}^{1} & O_{2}^{1} & O_{3}^{1} & ϕ \\ O_{1}^{2} & O_{2}^{2} & ϕ & O_{1}^{4} \\ O_{1}^{3} & ϕ & O_{3}^{2} & O_{4}^{2} \\ ϕ & O_{2}^{3} & O_{3}^{3} & O_{4}^{3} \end{matrix}]$

Then, four shadows S₁ , S₂, S₃, and S₄ are generated as follows.

S 1 = O ˆ 11 \cup O ˆ 12 \cup O ˆ 13 \cup O ˆ 14 = O 11 \cup O 12 \cup O 13 \cup ϕ = O 11 \cup O 12 \cup O 13; S 2 = O ˆ 21 \cup O ˆ 22 \cup O ˆ 23 \cup O ˆ 24 = O 21 \cup O 22 \cup ϕ \cup O 14 = O 21 \cup O 22 \cup O 14; S 3 = O ˆ 31 \cup O ˆ 32 \cup O ˆ 33 \cup O ˆ 34 = O 31 \cup ϕ \cup O 23 \cup O 24 = O 31 \cup O 23 \cup O 24; S 4 = O ˆ 41 \cup O ˆ 42 \cup O ˆ 43 \cup O ˆ 44 = ϕ \cup O 32 \cup O 33 \cup O 34 = O 32 \cup O 33 \cup O 34;

$\begin{array}{l} S_{1} = {\hat{O}}_{1}^{1} \cup {\hat{O}}_{2}^{1} \cup {\hat{O}}_{3}^{1} \cup {\hat{O}}_{4}^{1} = O_{1}^{1} \cup O_{2}^{1} \cup O_{3}^{1} \cup ϕ = O_{1}^{1} \cup O_{2}^{1} \cup O_{3}^{1}; \\ S_{2} = {\hat{O}}_{1}^{2} \cup {\hat{O}}_{2}^{2} \cup {\hat{O}}_{3}^{2} \cup {\hat{O}}_{4}^{2} = O_{1}^{2} \cup O_{2}^{2} \cup ϕ \cup O_{4}^{1} = O_{1}^{2} \cup O_{2}^{2} \cup O_{4}^{1}; \\ S_{3} = {\hat{O}}_{1}^{3} \cup {\hat{O}}_{2}^{3} \cup {\hat{O}}_{3}^{3} \cup {\hat{O}}_{4}^{3} = O_{1}^{3} \cup ϕ \cup O_{3}^{2} \cup O_{4}^{2} = O_{1}^{3} \cup O_{3}^{2} \cup O_{4}^{2}; \\ S_{4} = {\hat{O}}_{1}^{4} \cup {\hat{O}}_{2}^{4} \cup {\hat{O}}_{3}^{4} \cup {\hat{O}}_{4}^{4} = ϕ \cup O_{2}^{3} \cup O_{3}^{3} \cup O_{4}^{3} = O_{2}^{3} \cup O_{3}^{3} \cup O_{4}^{3}; \end{array}$

15.4 Wang et al.'s Scheme

In this section, we describe in detail Wang et al.'s scheme [10] to introduce the standard method of polynomial-based image sharing. Some notations in Wang et al.'s scheme have been trimmed for easy description. Also, the Galois Field GF(2⁸) operations are applied to their scheme such that the all gray-level values 0~255 can be completely represented. Therefore, the secret image is completely lossless. The detailed approaches in Wang et al.'s scheme are introduced in the following subsections.

15.4.1 Secret Image Sharing

Based on the study in the literature [8], a secret image sharing technique was applied in our scheme. In their proposal, the size of shadows could be dramatically reduced, with n shares being embedded into n different host images to avoid the attention of hackers. However, if malicious participants deliver fake stego-images, the receivers may recover a fake secret image, thus misleading those participating in the secret sharing scheme, due to poor detection. Thus, yet another secret sharing function was invented, that we also applied in our proposal, using detection authentication to enhance security. Below, a revised algorithm is presented to achieve both high capacity and extended applications, where participants can recover two or more secret images from a stego-image. The notations for the Revised Algorithm of High-Capacity and Applications (RAHA for short) are given prior to all the steps shown.

Notations:

S: The target secret image with size m × m.

t: More than or equal to t shadows possessed by the participants that can recover the target secret image.

n: The number of participants.

S_t: Each pixel of the target secret image S, i = 1, 2, ⋯, m².

B_i,j: The g th block (size of 1 × 8) in the j th cover image, where j = 1, 2,⋯, n and g = 1, 2, [m2t] $[\frac{m^{2}}{t}]$ ,. Each block is made of 8 pixels.

B(d)g,j $B_{g, j}^{(d)}$ : The dth pixel of block B_i,j. The bit string of each pixel B(d)g,j $B_{g, j}^{(d)}$ is shown as the form ( x_d1, x_d2,⋯, x_d7, x_d8) where 1 ≤ d ≤ 8.

Bˆg,j ${\hat{B}}_{g, j}$ : The gth block in the jth stego-image.

f_j: The feature value of the jth stego-image (or the jth cover image) when the block B(d)g,j $B_{g, j}^{(d)}$ (orB_gj) is processed, where the stego-image size is of 2m × 2m. f_j = (x₁₁, x₁₂, x₁₃, x₁₄, x₂₁, x₂₂, x₂₃, x₂₄) is created from the first two pixels in block B(d)g,j $B_{g, j}^{(d)}$ (orB_{g, j}), for j = 1, 2, ⋯ , n. If f_j is equal to one of feature values f₁, f₂, ⋯, f_j-1, keep looking at the next possible pair of pixels in block B(d)g,j $B_{g, j}^{(d)}$ (orB_{g, j}) following a fixed order. (Note that there are C (8, 2) × 2 = 56 possible choices in a block.)

PV (g)−yj $P V_{- y_{j}}^{(g)}$ : The gth pixel in jth shadows, g = 1, 2, ⋯ , [m2t] $[\frac{m^{2}}{t}]$ and j = 1, 2,⋯, n. The bit-string format of PV (g)−yj $P V_{- y_{j}}^{(g)}$ is (y_g1, y_g2, ⋯, y_g8).

p: 256 for the Galois Field GF(2⁸).

Revised Algorithm of High-Capacity and Applications (RAHA) Part I: Aim at the high capacity approaching:

For g−1, 2, ⋯, [m2t] $[\frac{m^{2}}{t}]$ , do a loop as follows:

Step 1. Generate the polynomial q_g (x) of t − 1 degrees as follows:

q(x) = (a₀ +a₁x + a₁x² + ⋯ + a_i-1x^i-1)

where a₀ = S_i, a₁ = S_i + 1, ⋯ , a_t−1=S_i+t−1, i = (g − 1)t, and all operations are over the Galois Field GF(2⁸).

Step 2. Get block B_{g, j}• from the jth cover image. Set f_j as the feature value of block B_g,j, j = 1, 2,⋯, n.

Step 3. Compute PV (g)−yj=qg(fi),j=1,2,…,n $P V_{- y_{j}}^{(g)} = q_{g} (f_{i}), j = 1, 2, \dots, n$ .

Step 4. Assign each PV (g)−yj $P V_{- y_{j}}^{(g)}$ to the jth shadow, j = 1, 2, ⋯ , n.

Images

FIGURE 414.15
Demonstration of steps in RAHA.

The steps stated in RAHA are also demonstrated in Figure 15.4.

Part II. Aim at the recovery of the original secret image.

Step 1. Collect at least t shadows among n shadows. Renumber t of them as 1, 2, …, t in order.

For g = 1, 2, ⋯ , [m2t] $[\frac{m^{2}}{t}]$ , do a loop of the following steps:

Step 2. Chose the t feature value f_j, j = 1 , 2, ⋯, t forms the collected stegoimages.

Step 3. Let x_j = f_j, for j = 1, 2,⋯, t. Reconstruct q_g (x)by using the pair of (x_j, PV (g)−yj $P V_{- y_{j}}^{(g)}$ ) as follows:

q g (x) = \sum t b = 1 P V (g) - y b \prod t j = 1, j \neq b x - x j x b - x j m o d p

$q_{g} (x) = \sum_{b = 1}^{t} P V_{- y_{b}}^{(g)} \prod_{j = 1, j \neq b}^{t} \frac{x - x_{j}}{x_{b} - x_{j}} m o d p$

Step 4. Restore t pixels of the secret image from the t coefficients in the polynomial function q_g (x) = (a₀ + a₁x +⋯+ a_t−1x^t−1 ).

15.4.2 Set-Up Authentication

In Thien and Lin's proposal [8], the size of shadows could be dramatically reduced, with n shares being embedded into n different host images to avoid the attention of hackers. However, if malicious participants deliver fake stegoimages, the receivers may recover a fake secret image, thus misleading those participating in the secret sharing scheme, due to poor detection. Thus, yet another secret sharing function was invented in Wang et al.'s scheme to enhance security by introducing an authentication procedure. The CRC (Cyclic Redundancy Code Check) and hash function are therefore considered to prevent the fake shares from the malicious participants who offer in the course of revealing the secret image, where the CRC is implemented by CRC-8. Based on the CRC adoption, once the participants receive the stego-image, the CRC will be launched to check all pixels in the stego-image prior to the reconstruction of secret image. The CRC-based detecting authentication procedure for each block in the stego-image is presented as follows:

Step 1. Let G(x) be the polynomial generator. Set/Reset the authentication code of CRC-8 as C_g = (c_g1, c_g2, ⋯, c_g8) = "00000000," g = 1, 2, ⋯, [m2t] $[\frac{m^{2}}{t}]$ . MAC (Message Authentication Code) with hash implementation is used as Hk(Bˆg,j∥g∥IDstego−image∥yg8) $H_{k} ({\hat{B}}_{g, j} ‖ g ‖ I D_{s t e g o - i m a g e} ‖ y_{g 8})$ , where K is a secret key. Set B(x) = (Bˆg,j∥∥Hk(Bˆg,j∥g∥IDstego−image∥yg8))(x) $({\hat{B}}_{g, j} ‖ H_{k} ({\hat{B}}_{g, j} ‖ g ‖ I D_{s t e g o - i m a g e} ‖ y_{g 8})) (x)$ , where Bˆg,j ${\hat{B}}_{g, j}$ is the stego-block, and ID_stego--mage is the identity of a stego-image, i.e., the block message Bˆg,j ${\hat{B}}_{g, j}$ is then followed by the MAC of Hk(Bˆg,j∥g∥IDstego−image∥yg8) $H_{k} ({\hat{B}}_{g, j} ‖ g ‖ I D_{s t e g o - i m a g e} ‖ y_{g 8})$ .

Step 2. Obtain remainder polynomial R(x) = B(x)modG(x).

Step 3. Assign the coefficient of R(x) to C_g.

Step 4. Store C_g to the block Bˆg,j ${\hat{B}}_{g, j}$ of the stego-image.

Step 5. Compare the R(x) and C_g. If the result is the same, the block Bˆg,j ${\hat{B}}_{g, j}$ of the stego-image is a legal one. Otherwise reject it whenever the compared result is different.

Example 2.

Consider a gray-level block with a size of 8 pixels. Assume that the Bˆg,j= ”A1A2A3A4” ${\hat{B}}_{g, j} = ” A1A2A3A4”$ = (it is caught by up-to-down and left-to-right in order), where C_g = "00000000", and the output of HMAC is Hk(Bˆg,j∥g∥IDstego−image∥yg8)=” D08932564F74499D4EC45CA9EBD54B64” $H_{k} ({\hat{B}}_{g, j} ‖ g ‖ I D_{s t e g o - i m a g e} ‖ y_{g 8}) = ” D08932564F74499D4EC45CA9EBD54B64”$ . Set Bx=(Bˆg,j∥∥Hk(Bˆg,j∥g∥IDstego−image∥yg8))(x) $B_{x} = ({\hat{B}}_{g, j} ‖ H_{k} ({\hat{B}}_{g, j} ‖ g ‖ I D_{s t e g o - i m a g e} ‖ y_{g 8})) (x)$ = (A1A2A3A4D08932564F74499D4 EC45CA9EBD54B64)(x). Let the generator polynomial G(x) = 100110001(x)= x⁸ + x⁵ + x⁴ + 1. The CRC code is then generated as C_g = R(x) = B(x)modG(x) = (c_g1, c_g2,⋯,c_g8) = "00110000". Then store C_g into Bˆg,j ${\hat{B}}_{g, j}$ of the stego-image. In the request of detecting the stego-image, pick up the embedded C_r and Let T = Cr = "00110000" and reset C_g = "00000000." Run the CRC-based detecting authentication procedure again to obtain R(x) = (00110000)(x). Compare if T is equal to the coefficient of R(x) as "00110000." Clearly, in this case, they are consistent with each other. In a word, the block Bˆg,j ${\hat{B}}_{g, j}$ of the stego-image remains the safe one from the malicious attacks.

15.4.3 Main Algorithms

In this subsection, Wang et al.'s main algorithm, Secret Embedding and Detecting Algorithm (SEDA for short) and Target Secret Image Recovery Algorithm (TSIRA) are presented. More notations are given together with the above-mentioned notations as follows.

Notations:

I_j: The jth cover image with the size 2m × 2m pixels.

I_j The jth stego-image with the size of 2m × 2m.

B(d)g,j $B_{g, j}^{(d)}$ The dth pixel value of the gth block B_g,j• in the jth cover image.

Bˆ(d)b,j ${\hat{B}}_{b, j}^{(d)}$ The dth pixel value of the gth block Bˆg,j ${\hat{B}}_{g, j}$ • in the jth stego-image.

K : A secret key K used in the hash function.

Secret Embedding and Detecting Algorithm: The SEDA aims at the secret embedding and detecting authentication.

Input: S, I_j, j = 1, 2, ⋯, n, k.

Output: Î_j, j = 1 , 2, ⋯, n.

Step 1. Get the distinct feature-value f_j = (x₁₁, x₁₂, x₁₃, x₁₄, x₂₁, x₂₂, x₂₃, x₂₄) from B_{g, j} of the cover image I_j, where j = 1, 2,⋯ , n. If f_i is equal to one of the feature-values f₁ , f₂, ⋯, f_j-1, then keep looking for the next pair of pixels in block B_{g, j}.

Step 2. Call RAHA to compute PV (g)−yj=qg(fi) $P V_{- y_{j}}^{(g)} = q_{g} (f_{i})$ and let each PV (g)−yj $P V_{- y_{j}}^{(g)}$ be the bit-string format as (y_g,1, y_g,2, ⋯ , y_{g, 8}).

Step 3. Apply IPLA to generate a pattern-string. Inspecting each block Bˆg,j ${\hat{B}}_{g, j}$ , set the bit string of (y_r1,y_r2, ⋯ ,y_r8) to be the input of IPLA, for g=1,2,⋯,[m2t] $g = 1, 2, \dots, [\frac{m^{2}}{t}]$ . The output of IPLA, a k-bit pattern-string of (p1,p2,⋯,pm2t) $(p_{1}, p_{2}, \dots, p_{\frac{m^{2}}{t}})$ is then generated after [m2t] $[\frac{m^{2}}{t}]$ blocks Bˆ′g,js ${\hat{B}}^{'}_{g, j} s$ are given.

Step 4. According to CRC-based detecting authentication procedure, generate [m2t] $[\frac{m^{2}}{t}]$ authentication codes of (c_g1, c_g2), ⋯, c′g8s ${c^{'}}_{g 8} s$ , for g=1,2,⋯,[m2t] $g = 1, 2, \dots, [\frac{m^{2}}{t}]$

Step 5. Arrange all pixels in block Bˆg,j, ${\hat{B}}_{g, j},$ for g=1,2,⋯,[m2t] $g = 1, 2, \dots, [\frac{m^{2}}{t}]$ , as the following rule:

B ˆ 1 g, j = (x 11, \dots, x 16, y g 1, c g 1), B ˆ 2 g, j = (x 21, \dots, x 26, y g 2, c g 2), B ˆ 3 g, j = (x 31, \dots, x 36, y g 3, c g 3), B ˆ 4 g, j = (x 41, \dots, x 46, y g 4, c g 4),

$\begin{array}{l} {\hat{B}}_{g, j}^{1} = (x_{11}, \dots, x_{16}, y_{g 1}, c_{g 1}), \\ {\hat{B}}_{g, j}^{2} = (x_{21}, \dots, x_{26}, y_{g 2}, c_{g 2}), \\ {\hat{B}}_{g, j}^{3} = (x_{31}, \dots, x_{36}, y_{g 3}, c_{g 3}), \\ {\hat{B}}_{g, j}^{4} = (x_{41}, \dots, x_{46}, y_{g 4}, c_{g 4}), \end{array}$

B ˆ 5 g, j = (x 51, \dots, x 56, y g 5, c g 5), B ˆ 6 g, j = (x 61, \dots, x 66, y g 6, c g 6), B ˆ 7 g, j = (x 71, \dots, x 76, y g 7, c g 7), B ˆ 8 g, j = (x 81, \dots, x 86, y g 8, c g 8),

$\begin{array}{l} {\hat{B}}_{g, j}^{5} = (x_{51}, \dots, x_{56}, y_{g 5}, c_{g 5}), \\ {\hat{B}}_{g, j}^{6} = (x_{61}, \dots, x_{66}, y_{g 6}, c_{g 6}), \\ {\hat{B}}_{g, j}^{7} = (x_{71}, \dots, x_{76}, y_{g 7}, c_{g 7}), \\ {\hat{B}}_{g, j}^{8} = (x_{81}, \dots, x_{86}, y_{g 8}, c_{g 8}), \end{array}$

Images

FIGURE 15.5
A secret sharing system with target secret embedding of high capacity and detection authentication: (a) Flowchart of target secret embedding procedures; (b) Recovery of target secret forms the stego-images in our secret sharing systems.

Step 6. Construct Î_j by gaining [m2t] $[\frac{m^{2}}{t}]$ blocks Bˆg,j ${\hat{B}}_{g, j}$ in order, g=1,2,⋯,[m2t] $g = 1, 2, \dots, [\frac{m^{2}}{t}]$ .

Target Secret Image Recovery Algorithm: The TSIRA aims at the recovery of the original secret image.

Input: A set of at least t stego-images and a secret key K.

Output: A target secret image S if all the stego-images are authenticated to be genuine.

Step 1. Renumber t of the inputted stego-images as Î_j, j = 1, 2,⋯, t, in order.

Step 2. Use a secret key K and call the CRC-based detecting authentication procedure in the stego-image Î_j. If the comparison for the authentication code C_g is then correct, proceed to the next step, otherwise, a fake stego-image is detected.

Step 3. For each PV (g)−yj $P V_{- y_{j}}^{(g)}$ and block Bˆg,j ${\hat{B}}_{g, j}$ , apply IPLA to compute the pattern-string (p1,p2,⋯,pm2t) $(p_{1}, p_{2}, \dots, p_{\frac{m^{2}}{t}})$ in the IPLA. Follow the sign of (p1,p2,⋯,pm2t) $(p_{1}, p_{2}, \dots, p_{\frac{m^{2}}{t}})$ to recover the bit-string of (y_g1, y_g2,⋯, y_g8) of in the Bˆg,j ${\hat{B}}_{g, j}$ , for g=1,2,⋯,[m2t] $g = 1, 2, \dots, [\frac{m^{2}}{t}]$ .

Step 4. Pick up f_j and calculate PV (g)−yj $P V_{- y_{j}}^{(g)}$ in Bˆg,j ${\hat{B}}_{g, j}$ , j = 1, 2, ⋯, t. Follow RAHA to recover the polynomial with the t pairs of (fj,PV (g)−yj)′s,j=1,2,…,t ${(f_{j}, P V_{- y_{j}}^{(g)})}^{'} s, j = 1, 2, \dots, t$ .

Step 5. Call RAHA to recover the polynomial with the t pair of (fj,PV (g)−yj)′s,j=1,2,…,t ${(f_{j}, P V_{- y_{j}}^{(g)})}^{'} s, j = 1, 2, \dots, t$ . Obtain secrets S_i,i = (g − 1)t + 1, (g − 1)t + 2, ⋯, (g − 1)t + (t − 1).

Step 6. Combine all S_i in order to reveal the target secret image S.

Wang et al.'s scheme with the proposed algorithms to fulfill the sharing system with the target secret high capacity and detection authentication are sketched as shown in Figure 15.5.

15.5 Experimental Results

Capacity and detecting authentication procedure are presented and discussed in this section via the observations of experiments for benchmark images. Two samples of (2, 4)-threshold and (4, 6)-threshold schemes are taken into consideration, in order to highlight the contributions made by Wang et al.'s proposed method.

15.5.1 Fidelity Analysis

The target secret image is shown as Figure 15.6 (a). The benchmarks of the cover images are Bridge, Butterfly, Toys, and Airplane, respectively, shown in Figures 15.6 (b) − (e). The size of the target secret image is 14 $\frac{1}{4}$ of each cover image mentioned above. The corresponding four stego-images are shown in Figures 15.6 (b′) − (e′) after SEDA, where the cover images still look the same as the stego-images to the human eye. The measurements of peak signal noise ratio (PSNR) to discriminate between cover images in Figures 15.6 (b)−(e) and stego-images in Figures 15.6 (b′) − (e′) were evaluated as 43.42, 43.43, 43.41, and 43.44, respectively. The target secret image, shown in Figure 15.6 (a) could be revealed when the (2, 4)-threshold was applied, via the four stego-images shown in Figures 15.6 (b′) − (e′). The experiments to embed Figure 15.6 (a) and the resulting PSNR are summarized in Table 1. In addition, the revelation of the target secret image was the same as Figure 15.6(a) when the (2, 4)-threshold was applied in the stego-images, as shown in Figure 15.6 (b′) − (e′) and offered in Wang et al.'s scheme. It can be seen that significantly improved fidelity was achieved in Wang et al.'s scheme with the higher PSNRs, when compared to other studies [4, 12].

Now considering another case, the (4, 6)-threshold scheme is used to embed two target secret images, as shown in Figure 15.7 (a) and (b). The six cover images are shown in Figure 15.7 (c) − (h). The size of each target secret image is 14 $\frac{1}{4}$ of each cover image. After SEDA, the corresponding six stego-images can be seen in Figure Figure 15.6 (c′) − (h′). The PSNR measurements for the discriminations between the six cover images in Figure 15.7 (c)-(h) and stego-images in Figure 15.6 (c′) − (h′) were evaluated as 43.39, 43.43, 43.42, 43.39, 42.95 and 43.05, respectively, as shown in Table 2. Accordingly, the quality of the stego-image was visually acceptable, when compared to the corresponding cover images upon the high PSNRs. On the other hand, the target secret images, shown in Figures 15.7 (a) and (b) could also be exactly revealed when the (4, 6)-threshold was applied, via the six stego-images shown in Figures 15.7 (c′) − (h′).

As seen below, colored benchmark images are further considered to the embedding system via SEDA. The target secret image is shown in Figure 15.8 (a). These show the experimental results, using full color cover images. The PSNR measurements were evaluated as 43.39, 43.12, 43.41, and 43.40, respectively, for the discriminations between the cover and stego-images, shown in Figures 15.8 (b)-(e) and (b′)-(e′). The comparisons, between the PSNR measurements in Wang et al.'s and some other studies are presented in Table 15.3. The (2, 4)-threshold scheme was applied, in this case, among the stego-images shown in Figures 15.8 (b′)-(e′). The target secret image can be seen to be totally revealed, and identical to the original, shown in Figure 15.8(a).

Table 15.1 PSNR comparisons for past schemes and our scheme.

	Bridge	Butterfly	Toys	Airplane
Lin-Tsai-scheme (PSNR)	39.11	39.13	39.23	39.16
Yang et al. scheme (PSNR)	41.61	41.46	41.44	41.69
Wang et al. scheme (PSNR)	43.42	43.43	43.41	43.44

15.5.2 Evaluating Authentication

In this section, the detection ability of the Lin-Tsai scheme, Yang et al.'s scheme and Wang et al.'s are discussed. These are then compared, as shown in Figures 15.9-15.11.

Images

FIGURE 420.15
(a) the target secret images; (b)-(e) the four cover-images; (c′)-(h′) the four stego-images.

Images

FIGURE 15.7
(a) and (b) the target secret images; (c)–(h) the four cover-images; (c′)–(h′) the four stego-images.

Table 15.2 PSNR measurements when embedding the two target secret images in Figure 15.5 (a) and (b) comparisons for past schemes and our scheme.

Images

Table 15.3 PSNR comparisons with the Lin-Tsai scheme.

	Milk	Tiffany	Baboon	Airplane
Lin-Tsai-scheme	39.07	39.08	39.08	39.07
Wang et al. scheme	43.39	43.12	43.41	43.40

Images

FIGURE 15.8
(a) the target images; (b)–(e) the four cover images; (b′)–(e′) the four stego-images.

Images

FIGURE 15.9
Minor bit adjustments in the stego-image of " airplane" (a) Lin-Tsai scheme, (b) Yang et al. scheme, and (c) our scheme.

Images

FIGURE 422.15
Partial area adjustments in the stego-images of "sailboat." (a) Lin-Tsai scheme, (b) Yang et al.'s scheme, and (c) our scheme.

Images

FIGURE 15.11
Replacement of "airplane" stego-image with "pepper." (a) original stego-image of "Airplane", (b) replaced by "pepper" Lin-Tsai scheme, (c) replaced by "pepper" in Yang et al.'s scheme, and (c) detected in our scheme.

Case I. Minor bit adjustments in the stego-images, with results compared in Figure 15.9.

Case II. Partial area adjustment of a fake stego-image that can succeed the fake scenarios in [4, 12], but this case is blocked in Wang et al.'s scheme, as shown in Figure 15.10.

Case III. Replacement of a fake stego-image that was visually imperceptible was detected in Wang et al.'s , shown in Figure 15.11. As observed in Figures 15.9–15.11, the three cases not detected by the schemes in [4, 12] were easily made out when Wang et al.'s was applied. The probability of passing a fake stego-image, in the scheme of Yang et al. [12], was (12)m2 ${(\frac{1}{2})}^{m^{2}}$ , where one bit parity-check and hash were applied in a block (4-pixel) and (4m)24=m2 $\frac{{(4 m)}^{2}}{4} = m^{2}$ non-overlapping blocks were set in the stego-image. On the other hand, in Wang et al.'s, a block had an 8-pixel format, such that the probability of this block succeeding was (12)8 ${(\frac{1}{2})}^{8}$ while the probability of a fake stego-image succeeding in Wang et al.'s method-2 was ((12)8)m22=(12)4m2 ${({(\frac{1}{2})}^{8})}^{\frac{m^{2}}{2}} = {(\frac{1}{2})}^{4 m^{2}}$ only, where there were4m28=m22 $\frac{4 m^{2}}{8} = \frac{m^{2}}{2}$ blocks in total in the stego-image.The summary comparisons are shown in Table 15.4.

Table 15.4 PSNR comparisons with the Lin-Tsai scheme.

	High capacity	Techniques used in authentications	Probability of cheating (Numerical analysis)
Thien-Lin scheme [8]	YES	N/A	N/A
Lin-Tsai scheme [4]	N/A	Parity bit check	N/A
Yang et al. scheme [12]	N/A	Hash Function	(1/2)^m2
Wang et al. scheme [10]	YES	CRC and Hash fuction	(1/2)^4m2

15.6 Conclusions

In this chapter, we introduce some polynomial-based image sharing schemes as well as our proposed scheme. These image sharing schemes are based on the (t, n)-threshold scheme to share the secret image to n participants. Sometimes, some authentication approaches and steganographic approaches were applied. Algorithms, such as IPLA, RAHA, SEDA, and TSIRA, were incorporated into our scheme; the RAHA and IPLA were applied [8, 11], aiming to guarantee higher capacity, and SEDA and TSIRA were used to enable the robust authentication requirement, to reveal the original target secret image. Compared to some other studies [4, 8, 12], Wang et al.'s scheme behaved better in the terms of capacity with secret embedding in a stego-image and in detection/authentication to block offers of fake shares.

Bibliography

[1] G. R. Blakley. Safeguarding cryptographic keys. In Proceedings of the National Computer Conference, volume 48, pages 313–317. AFIPS Press, 1979.

[2] C.C., Chang, C.L. Lin, and H. Chou. Perfect hashing schemes for mining traversal patterns. Fundamenta Informaticae, 70:185–202, November 2005.

[3] G. Horng, T.H. Chen, and D.S. Tsai. Cheating in visual cryptography. In Designs, Codes and Cryptography, volume 38, pages 219–236. Kluwer Academic Publishers, 2006.

[4] C.C. Lin and W.H. Tsai. Secret image sharing with steganography authentication. In The Journal of Systems Software, volume 24, pages 405–414, 2004.

[5] S.P. Mohanty and B.K. Bhargava. Invisible watermarking based on creation and robust insertion-extraction of image adaptive watermarks. In Transactions on Multimedia Computing, Communications, and Applications, volume 5 (12), pages 612–613, 1979.

[6] M. Naor and A. Shamir. Visual cryptography. In EUROCRYPT 94, Springer-Verlag Berlin, volume LNCS 950, pages 1–12, 1995.

[7] A. Shamir. How to share a secret. Communication of the ACM, 22:612– 613, November 1979.

[8] C. C. Thien and J. C. Lin. Secret image sharing. In Computers & Graphics, volume 26, pages 765–770, 2002.

[9] R.Z. Wang and S.J. Shyu. Scalable secret image sharing. Image Commun., 22:363–373, April 2007.

[10] S.J. Wang, I.S. Lin, Y.L. Hsieh, and C.Y. Weng. Secret sharing systems with authentication-based steganography. In Proceedings of the 2008 International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IIH-MSP '08, pages 1146–1149, Washington, DC, USA, 2008. IEEE Computer Society.

[11] C.H. Yang. Inverted pattern approach to improve image quality of information hiding by LSB substitution. Pattern Recognition, 41:2674–2683, August 2008.

[12] C.N. Yang, T.S. Chen, K. H. Yu, and C.C. Wang. Improvements of image sharing with steganography and authentication. Journal of Systems and Software, 80:1070–1076, July 2007.

[13] C.N. Yang and S.M. Huang. Constructions and properties of k out of n scalable secret image sharing. Optics Communications, 283((9):1750–1762, 2010.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for
15 Polynomial-Based Image Sharing

15

Polynomial-Based Image Sharing

CONTENTS

15.1 Introduction

15.2 Polynomial-Based Sharing Scheme

15.2.1 Shamir's Secret Sharing Scheme

15.2.2 Lagrange Interpolation Scheme

15.3 Preliminaries and Related Works

15.3.1 Thien-Lin Scheme

15.3.2 Lin-Tsai Scheme

15.3.3 Yang et al.'s Scheme

15.3.4 Inverted Pattern LSB Scheme

15.3.5 Scalable Secret Image Sharing

15.4 Wang et al.'s Scheme

15.4.1 Secret Image Sharing

15.4.2 Set-Up Authentication

15.4.3 Main Algorithms

15.5 Experimental Results

15.5.1 Fidelity Analysis

15.5.2 Evaluating Authentication

15.6 Conclusions

Bibliography

Table of Contents for 15 Polynomial-Based Image Sharing

Create new playlist

Sign In

Sign Up

CONTENTS

Table of Contents for
15 Polynomial-Based Image Sharing