(t, n) Threshold secret image sharing scheme with adversary structure

Abstract

Secret image sharing has been researched intensively, and it has emerged as an alternative to data hiding for protecting the security and privacy of important data. In the traditional (t, n) threshold secret image sharing schemes, any t or more shadow images can reconstruct the shared secret image. However, in real applications, (t, n) threshold access structures cannot meet all of the requirements, such as the adversary structure, which means that unauthorized groups of participants cannot reconstruct the shared secret. Thus, in (t, n) threshold secret sharing with adversary structure, t participants who want to reconstruct the secret cannot do so if they happen to belong to the defined adversary structure. This novel characteristic has the potential to work in many applications. However, the existing secret image sharing mechanisms cannot achieve the adversary structure. To solve this problem, we proposed a secret image sharing scheme that can achieve the adversary structure. In addition, our scheme also is a (t, n) threshold secret image sharing scheme. That is, t or more shadow images can be used to reconstruct the secret image, but some subsets that contain at least t shadow images among the adversary structures cannot reconstruct the secret image. The experimental results showed that the validity of our scheme is satisfactory.

1 Introduction

With the development of network technology and cloud storage [19, 25], more and more multimedia data, such as image, video, and others, are outsourced to the cloud server for storage in order to reduce the storage cost. Meanwhile, large amounts of multimedia data have emerged from social networks. Therefore, the security and privacy [9, 15] of these data are becoming more and more important. The secret sharing scheme is an important method to protect the security and integrity of secret data, and it has been applied in many fields. In 1979, both Shamir [20] and Blakley [2] proposed (t, n) threshold secret sharing schemes. In their schemes, the secret is divided into n shadows that are distributed to n participants. Any t or more participants can cooperate to recover the secret by pooling their secret shadows. However, no information about the secret can be obtained using t − 1 or fewer shadows.

Based on the previous work, several secret image sharing schemes have been proposed. First, Naor and Shamir [16] proposed a secret image sharing scheme known as visual secret sharing (VSS). In VSS schemes (Yang [28]; Wang and Su [24]; Lin and Wang [13]), the secret image can be reconstructed by stacking t or greater shadow images without any cryptographic computations. However, the shadow images are random-like in the VSS scheme. So, they will be more likely to attract the attention of malicious attackers when the shadows are delivered over an insecure channel. In order to solve this problem, some secret image sharing schemes have been proposed that utilized the steganography approach to camouflage the shadows into a cover image to generate meaningful shadow images. In 2003, Thien and Lin [23] proposed a user-friendly secret image sharing scheme utilizing the steganography approach in which the shadow images were meaningful. However, the shadow images in their scheme are just reduced versions of the secret image, and they can expose some information about the secret image. Then, Lin and Tsai [12] utilized the least significant bits (LSB) embedding technique to hide shared values into a cover image. Furthermore, an image watermarking technique was used to verify whether the shadow images had been tampered. But, in their scheme, the revealed secret image is distorted slightly. It is well known that revealing the secret image without distortion is of paramount importance in some fields. Thus, even a slight distortion may be intolerable. So, based on Lin and Tsai’s scheme, Yang et al. [29] developed a secret image sharing scheme that can prevent distortion of the shared secret image. However, their scheme reduces the visual quality of the shadow images, which may increase the potential for attacks. In 2009, Lin et al. [11] used the modulus operation to improve the quality of the shadow images. Moreover, both the shared secret image and the cover image can be reconstructed losslessly in their scheme. But the embedding capacity of their scheme is unacceptable to some extent. So, Lin and Chan [10] introduced a novel secret image sharing scheme that increased the maximum embedding capacity. Of course, their scheme also can recover the secret image and the cover image without distortion. However, the camouflaged pixel values in their scheme may exceed the grayscale boundary, which will cause the overflow situation. And most secret image sharing schemes utilize least significant bit (LSB) to embed the secret value. Some steganalysis of LSB matching schemes have been proposed (Xia and Wang et al. [26], Xia and Wang et al. [27]).

All of these schemes are (t, n) threshold secret sharing schemes, but they cannot be applied directly to non-threshold configurations. So, general access structure secret sharing schemes (GASSS) were proposed (Ito et al. [8]; Benaloh et al. [1]). In these schemes, the dealer can designate certain authorized groups of participants, and only those participants can recover the shared secret. It is obvious that the (t, n) threshold scheme is a special case of GASSS. Subsequently, secret sharing schemes with a general access structure were proposed (Chang et al. [3]; Tan et al. [22]; Pang et al. [17]). Based on the research of these authors, some secret image sharing schemes have been proposed that achieved various access structures. Shyu and Chen [21] proposed a secret image sharing scheme for a general access structure that also was a multi-secret image sharing scheme. However, their scheme is not secure. In 2012, Guo et al. [4] proposed a secret image scheme that achieved a hierarchical threshold access structure. In their scheme, the participants do not have equivalent roles, and the shadow images are partitioned into several levels, which are determined by a sequence of threshold requirements. The same authors proposed a secret image sharing scheme with a multi-threshold access structure based on monotone span programs (MSP) [5]. Their scheme simultaneously achieves both multi-secret image sharing and generalized access structure. Each shared secret image is associated with an access structure. So, the authorized subset of shadow images can cooperate to reveal the corresponding secret image losslessly. In 2014, Guo et al. proposed a (n, t, n) threshold secret image sharing scheme [6], and, in 2015, they proposed a multi-threshold secret image sharing scheme [7] based on the generalized Chinese Remainder Theorem.

GASSS concerns the authorized groups of participants rather than corrupt participants. In GASSS schemes, only participants in the “qualified subset” can cooperate to recover the shared secret, but participants in the “unqualified subset” cannot. This means that the generalized access structure concerns the “qualified subset,” while the adversary structure focuses on the unqualified subset. In reality, sometimes it is difficult to obtain the access structure according to the security requirements.

In some situations, the adversary can make some subsets of participants corrupt, which means the adversary can get their shared shares to reconstruct the secret. GASSS cannot be used in the above case, because the access structure defines qualified subsets of participants. This problem can be solved by the secret sharing scheme based on adversary structure, which can exclude the corrupt subsets to reveal the secret. Therefore, secret sharing schemes with adversary structure were proposed, and the structure is described in detail in Section 2. Ma and Guo [14] proposed a secret sharing scheme that achieved the adversary structure, but their scheme cannot achieve the (t, n) threshold. In order to widen the applications of this scheme, Qin et al. [18] developed a scheme that achieved both the (t, n) threshold and the adversary structure. Even though t participants are required to reconstruct the secret in their scheme, they cannot recover the secret if they belong to the defined adversary structure. In addition, the scheme can prevent the participants from cheating. Nevertheless, the size of the participants’ shares is somewhat large, while the shared secret is a large, private file. So, based on the properties of the Jordan matrix, Zhao et al. [30] made it possible to have a small share while sharing a large secret.

For example, concerning a (3, 5) threshold and an adversary structure {S ₁, S ₂, S ₄}, there are five shadow images {S ₁, S ₂, S ₃, S ₄, S ₅} to share a secret image (generating five shadow images by embedding a secret image into a cover image), and we can reconstruct the shared secret image from three or more shadow images, with the exception of the subset {S ₁, S ₂, S ₄}. Given such a requirement, the existing secret image sharing schemes cannot solve this problem, but we believe that the applications of secret image sharing with adversary structure have good prospects.

To the best of our knowledge, very few papers have discussed secret image sharing with an adversary structure. So, in this paper, we have proposed for the first time a secret image sharing scheme that can achieve both an adversary structure and a (t, n) threshold. First, we studied the characterization of the adversary structure, and, based on the existing (t, n) threshold schemes and our knowledge of the adversary structure, we proposed a new secret image sharing scheme that can achieve both an adversary structure and the (t, n) threshold. That is, t or more shadow images can cooperate to retrieve the secret image without distortion, but the subsets in the adversary structure cannot reveal it. In our scheme, the shadow images are generated by embedding secret data into the cover image, and, also, an array is computed for each participant according to the adversary structure. Then, the dealer distributes the corresponding shadow image and the array to each participant. The experimental results demonstrated that our scheme achieved the requirements of the adversary structure and the (t, n) threshold. In addition, the quality of the shadow image and the embedding capacity of our scheme also were satisfactory.

The novel characteristic of the proposed scheme is not available in the existing secret image sharing mechanisms, so the proposed scheme has the potential to work in many applications. The key features of our proposed secret image sharing scheme are summarized below:

• (1) The proposed scheme can achieve both the adversary structure and the (t, n) threshold.

• (2) The shared secret image can be reconstructed losslessly.

• (3) The scheme can solve the overflow and underflow problems.

• (4) The shadow images are meaningful, and the visual quality of the shadow images is satisfactory.

The rest of the paper is organized as follows. In Section 2, we briefly introduce the correlative definitions about access structure and adversary structure. The proposed secret image sharing scheme is presented in Section 3. Section 4 presents some experimental results and analysis. Our conclusions are given in Section 5.

2 Definitions

Let P = {P ₁, P ₂, …, P _n } be the set of participants. The qualified subset of P means participants in this subset can cooperate to reveal the secret image. The set of all of these qualified subsets is called the access structure on P. On the contrary, the participants in the unqualified subset of P, all of which comprise the adversary structure on P, cannot reveal the secret image. Their concepts are defined as follows:

Definition 1

Access structure: Γ is the access structure on P, and Γ = {A|A is the qualified subset of P}. And the elements in Γ must satisfy this condition: if A ∈ Γ, A ⊆ B ⊆ P, then B ∈ Γ can be deduced.

Definition 2

Adversary structure: Λ is the adversary structure on P, and Λ = {A|A is the unqualified subset of P}. And the elements in Λ must satisfy this condition: if A ∈ Λ, B ⊆ A ⊆ P, then, B ∈ Λ can be deduced.

Obviously, if A ∈ Γ, the supersets of A all belong to Γ, which means the access structure is increased monotonously. In contrast, the adversary is decreased monotonously. So, the minimal access structure and the maximal adversary structure must exist, in which one element does not contain other elements. The concepts of maximal adversary structure in set theory can be defined as follows:

Definition 3

[18] Minimal access structure: if Γ _min ⊆ Γ, and Γ _min = {A|if A ′ ⊆ A ⊆ P, then A ′ ∉ Γ _min}, then Γ _min is the minimal access structure on P.

Definition 4

[18] Maximal adversary structure: if Λ _max ⊆ Λ, and Λ _max = {A|if A ⊆ A′ ⊆ P, then A′ ∉ Λ _max}, then Λ _max is the maximal adversary structure on P.

The above definitions show that, if each subset does not contain another subset in an adversary structure, then the adversary structure is the maximal adversary structure. The maximal adversary structure Λ _max is a subset of the adversary structure Λ. And Λ can be determined by Λ _max, which is more concise than Λ. So, we will use the maximal adversary structure instead of the adversary structure in our scheme. In order to better illustrate the definition of maximal adversary structure, let P = {P ₁, P ₂, P ₃, P ₄} denote the set of participants and let Λ = {{P ₁, P ₂, P ₄}, {P ₁, P ₂}, {P ₁, P ₄}, {P ₂, P ₄}, {P ₂, P ₃}, {p ₁}, {p ₂}, {p ₃}, {p ₄}} be the adversary structure on P. Then, according to the definition of the maximal adversary structure, we can get the corresponding maximal adversary structure Λ _max = {{P ₁, P ₂, P ₄}, {P ₂, P ₃}}. That is, the maximal adversary structure Λ _max = {{P ₁, P ₂, P ₄}, {P ₂, P ₃}} contains all elements of the adversary structure Λ = {{P ₁, P ₂, P ₄}, {P ₁, P ₂}, {P ₁, P ₄}, {P ₂, P ₄}, {P ₂, P ₃}, {P ₁}, {P ₂}, {P ₃}, {P ₄}}.

3 The proposed scheme

3.1 The initialization phase

In this section, we construct a secret image sharing scheme with both an adversary structure and a (t, n) threshold. So, first, we define the maximal adversary structure and initialize some parameters. Let P = {P ₁, P ₂, …, P _n } denote the set of n participants, S = {S ₁, S ₂, …, S _n } denote the corresponding set of shadow images, and Λ _max = {A ₁, A ₂, …, A _m } denote the maximal adversary structure on P. Each shadow image S _i is distributed to the relative participant P _i . Obviously, there are m subsets in Λ _max, and each subset contains at least t shadow images. If |A| denotes the number of participants in subset A of P, the requirements of our secret image sharing scheme are as follows:

• (1) If |A| ≥ t and A ⊄ A _r (r = 1, 2, …, m), then the participants in A can cooperate to reveal the shared secret image.

• (2) If |A| ≤ t or A ⊆ A _r (r = 1, 2, …, m), then the shadow images in A cannot reveal the shared secret image.

In addition, the dealer also should initialize some other important parameters as follows:

• Step 1. Select a large prime modulus, p.

• Step 2. Choose m different positive integers, d ₁, d ₂, …, d _m , that can satisfy 1 ≤ d ₁ + d ₂ + ⋯ + d _m  ≤ p − 255, and compute d as follows:

$$ d={d}_1+{d}_2+\cdots +{d}_m. $$

(1)

• Step 3. Construct n identical arrays, H _i  = {d ₁, d ₂, …, d _m }, i = 1, 2, …, n.

For example, there is a (3, 4) threshold system in which P = P ₁, P ₂, P ₃, P ₄. Assume the adversary structure on P is Λ _max = {A ₁, A ₂}, where A ₁ = {P ₁, P ₂, P ₃}, A ₂ = {P ₂, P ₃, P ₄}. Then, the dealer will generate the shadow images S = {S ₁, S ₂, S ₃, S ₄}. The dealer initializes prime p = 1021 and the positive integers d ₁ = 121, d ₂ = 589, then d = 121 + 589 = 710, H _i  = {121, 589}, i = 1, 2, 3, 4.

3.2 Secret image sharing phase

In this phase, we describe how to generate the shadow images from the cover image and the shared secret image. The procedure consists of two phases, i.e., (1) the sharing phase and (2) the embedding and distribution phase.

3.2.1 Sharing phase

For convenience, assume that s ₁, s ₂, …, s _t denotes the shared pixels of the secret image SI, which is a grayscale image. And the cover image O = {O _i |i = 1, 2, …, (M × N)} is an M × N grayscale image. Thus, the dealer can perform the following steps:

• Step 1. With the values of s ₁, s ₂, …, s _t and d, c ₁, c ₂, …, c _t can be computed as:

$$ {c}_k={s}_k+d,\left(k=1,2,\dots, t\right). $$

(2)

• Step 2. Construct a (t − 1) degree polynomial, F(x), where p is a large prime number selected in the initialization phase.

$$ F(x)={c}_1+{c}_2x+\dots +{c}_t{x}^{t-1} \mod p. $$

(3)

• Step 3. Compute the corresponding shadow data y _i as y _i  = F(i) for all of the shadow images S _i (i = 1, 2, …, n) by entering the integer i into F(x).

For convenience, assume that there are four secret image pixels, s ₁, s ₂, s ₃, s ₄, which are 156, 183, 127, 83. The dealer computes c ₁, c ₂, c ₃, c ₄ as866, 893, 837, 793, and F(x) can be formulated as F(x) = 866 + 893x + 837x ² + 793x ³ mod 1021. Then, the shadow y _i can be computed by entering the integer i, such as y ₁ = F(1) = 326.

3.2.2 Embedding and distribution phase

As stated earlier, most secret image sharing schemes utilize the modulus operation to embed the shadow data y _i into the corresponding cover image pixels in order to conceal the existence of the embedded secret image and improve the visual quality of the shadow images. In our scheme, we construct the polynomial F(x) in a finite field, GF(p), where p is a large prime number. Therefore, we cannot use those methods directly. However, note that the scheme of Lin and Chan [10] utilizes a quantization operation to embed the secret data, and the quality of the shadow images in their scheme is satisfactory. So, we also use the quantization operation to generate shadow images. In this phase, the dealer will perform the following steps:

• Step 1. Choose the appropriate parameters K and σ, which must ensure that ⌊255/K⌋ × K + σ ≤ 255.

• Step 2. Convert each y _i into the σ -ary notational system and get the secret data y _i1 y _i2 … y _ia , where the value of a is computed as:

$$ a=\left\lceil { \log}_{\sigma }p\right\rceil . $$

(4)

• Step 3. Assume that the corresponding pixels of cover image, O, which are utilized to embed the value y _i1 y _i2 … y _ia , are o _i , o _i + 1, …, o _{i + a − 1}. And, q _i1, q _i2, …, q _ia are the camouflaged pixels. The value of q _i + j can be computed as follows:

$$ {q}_{ij}=\left\lfloor {O}_{i+j-1}/K\right\rfloor \times K+{y}_{ij},1\le j\le a. $$

(5)

• Step 4. Repeat the above processes until the shadow images are generated completely. Finally, the shadow images are sent to the corresponding participants.

The dealer also performs the following steps to achieve the adversary structure.

• Step 1. For all of the shadow images S _i (i = 1, 2, …, n) in S, if S _i  ∈ A _j (j = 1, 2, …, m), then delete d _j from H _i  = {d ₁, d ₂, …, d _m }.

• Step 2. Send the reminding elements of H _i over a secure channel, which is important for the security of our scheme.

Considering the above example, assume that the dealer chooses K = 8, σ = 7 and that the cover image pixels o ₀ = 234, o ₁ = 157, o ₂ = 183, o ₃ = 89 are utilized to embed the shadow values. The dealer will convert y ₁ into a 7-ary notational system as y ₁ = 326 = (0, 6, 4, 4)₇. Then, the stego pixels are q ₁₁ = ⌊234/8⌋ ⋅ 8 + 0 = 232, q ₁₂ = ⌊157/8⌋ ⋅ 8 + 6 = 158, q ₁₃ = ⌊183/8⌋ ⋅ 8 + 4 = 180, and q ₁₄ = ⌊89/8⌋ ⋅ 8 + 4 = 92. All stego pixels can be obtained by repeating the above steps. Figure 1 shows the flowchart of our secret image sharing scheme. The array of each participant can be generated as H ₁ = {589}, H ₂ = {}, H ₃ = {}, H ₄ = {121}.

Fig. 1

Diagram of the secret image sharing scheme

3.3 Secret image retrieving phase

For the collection of participants A, the participants can share their shadow images and cooperate to reconstruct the shared secret image SI if, and only if, |A| ≥ t and A ⊄ A _r (r = 1, 2, …, m). Otherwise, they can get no information about the secret image. So, assume that the set A contains t participants and A ⊄ A _r (r = 1, 2, …, m). Thus, the participants in A can cooperate to reveal the secret image. For convenience, assume that q _i1′, q _i2′, …, q _ia ′ are a pixels of P _i ′s shadow image S _i , where P _i  ∈ A, 1 ≤ i ≤ n. Then, the participants in A can complete the following steps to reveal the corresponding secret image pixels s ₁′, s ₂′, …, s _t ′:

• Step 1. Each participant P _i in A sends her or his shadow image S _i and array H _i to the designated combiner (DC), who may be a reliable participant in A or someone else.

• Step 2. According to the shadow image from each participant P _i in A, the DC can utilize the modulo operation to obtain the corresponding y _ij ′(1 ≤ j ≤ a) as:

$$ {y_{ij}}^{\prime }={q_{ij}}^{\prime } \mod K $$

(6)

• Step 3. The DC concatenates y _iz ′(1 ≤ z ≤ a), which are obtained in Step 1, to get y _i ′. The DC transforms y _i ′ into decimal representation.

• Step 4. With t pairs of (i, y _i ′), the polynomial F(x) can be reconstructed by Lagrange’s interpolation formula:

$$ F(x)={c}_1+{c}_2x+\cdots +{c}_t{x}^{t-1} \mod p. $$

(7)

And, thereby, the DC can obtain c ₁, c ₂, …, c _t by extracting the coefficients of F(x).

• Step 5. With all H _i from the participants in A, the DC deletes the redundant d _l , for l = 1, 2, …, m and just keeps one for each different d _l . Then, the value of d can be computed as:

$$ d={d}_1+{d}_2+\cdots +{d}_m. $$

(8)

• Step 6. With c ₁, c ₂, …, c _t and d, the DC can get the corresponding secret image pixels s ₁′, s ₂′, …, s _t ′ as follows:

$$ \begin{array}{l}{s_1}^{\prime }={c}_1-d\\ {}{s_2}^{\prime }={c}_2-d\\ {}\vdots \\ {}{s_t}^{\prime }={c}_t-d.\end{array} $$

(9)

By repeating these processes, the secret image SI can be reconstructed without distortion.

Assume the participants P ₁, P ₃, P ₄ want to cooperate to reconstruct the secret image. We will describe how they get the secret pixels s ₁, s ₂, s ₃, s ₄ in the above example. The coefficients c ₁ = 866, c ₂ = 893, c ₃ = 837, c ₄ = 793 can be obtained by using Lagrange’s interpolation formula, because the threshold requirement is satisfied. With all H ₁, H ₃, H ₄ of participants P ₁, P ₃, P ₄, the value of d can be computed as d = 121 + 589 = 710. With c ₁, c ₂, c ₃, c ₄ and d, s ₁, s ₂, s ₃, s ₄ can be computed as s ₁ = 866 − 710 = 156, s ₂ = 893 − 710 = 183, s ₃ = 837 − 710 = 127, s ₄ = 793 − 710 = 83. If the participants P ₁, P ₃, P ₄ want to reveal the secret image, they can get c ₁, c ₂, c ₃, c ₄. However, they cannot get d for the lock of d ₂ = 589. So P ₁, P ₃, P ₄ cannot reveal s ₁, s ₂, s ₃, s ₄.

4 Experimental results and analysis

In this section, we demonstrate the characteristics of our proposed scheme by conducting simulations and analyzing their results.

To estimate the quality of the shadow images, we use the peak signal-to-noise ratio (PSNR) to measure the distortion of the shadow images, which is defined as:

$$ PSNR=10{ \log}_{10}\left(\frac{255^2}{MSE}\right)\ \mathrm{dB}. $$

(10)

And, the mean square error (MSE) of an image with M × N pixels is defined as:

$$ MSE=\frac{1}{M\times N}{\displaystyle \sum_{j=1}^{M\times N}{\left({p}_j-{p}_j^{\prime}\right)}^2}, $$

(11)

where p _j is the original pixel value and p ^′ _j is the pixel value of the shadow image.

4.1 Simulation results

We performed experiments for n = 8 and t = 4. For the set of all participants P = {P ₁, P ₂, …, P ₈}, we designed the specific maximal adversary structure Λ _max = {A ₁, A ₂, A ₃}, where A ₁ = {P ₁, P ₃, P ₅, P ₇}, A ₂ = {P ₁, P ₂, P ₄, P ₅} and A ₃ = {P ₂, P ₅, P ₇, P ₈}. So, the secret image can be reconstructed without distortion if, and only if, the set A, which is the subset of P, contains at least four participants and A ⊄ A _r (r = 1, 2, 3).

In these experiments, we used 15 grayscale images with sizes of 512 × 512 pixels as the test images, as shown in Fig. 2, and the secret image ‘Airplane’ was set to 256 × 256 pixels, as shown in Fig. 3.

Fig. 2

The test images

Fig. 3

The secret image

We chose p = 1021, d ₁ = 219, d ₂ = 352 and d ₃ = 127 in the initialization phase in our experiments. And, as stated earlier, we used the quantization operation to embed the secret data in the embedding and distribution phases. So, we must select the appropriate K and σ to guarantee both the quality of the shadow image and the embedding capacity. We performed our experiments for K = 8 and σ = 7, and Table 1 shows the PSNR of the shadow images with various test images.

Table 1 PSNR of shadow images (dB)

Generally speaking, it is difficult for people to distinguish the original image from the shadow image if the PSNR of the shadow image is more than 35 dB. Table 1 shows that the PSNR values of the shadow images in our experiments were about 44–45. So, the quality of the shadow images is satisfactory in our scheme. In addition, we used Lena as the cover image and Airplane as the secret image to demonstrate the visual perception of the shadow images in our scheme. And the shared secret image can be reconstructed losslessly by any eligible subset of shadow images. Figure 4a and b show the cover image and the reconstructed secret image, respectively.

Fig. 4

Cover image and the extracted secret image

Figure 5 shows the corresponding eight shadow images for the cover image, Lena. So, judging from the visual perception of these shadow images, our scheme can successfully camouflage shadow images from intruders.

Fig. 5

Shadow images

An array H _i is distributed to each participant P _i (i = 1, 2, …, 8) in order to develop the adversary structure, and H _i is constructed according to the maximum adversary structure Λ _max = {A ₁, A ₂, A ₃}. Table 2 shows H _i , which is distributed to P _i in the experiments. So, if the subsets of participants are in the adversary structure, they cannot get all d ₁, d ₂, d ₃ at the same time. Thus, neither can they cooperate to reconstruct the secret image.

Table 2 Array H of participants

4.2 Security and correctness analysis

To prove the validity of our scheme, the concept of reconstruction property and confidentiality property are introduced.

Definition 5

Reconstruction property: if all qualified subsets of participants can reveal the secret image, then the secret image scheme satisfies the reconstruction property.

Definition 6

Confidentiality property: if all unqualified subsets of participants cannot reveal the secret image, then the secret image scheme satisfies the confidentiality property.

If, and only if, a secret image scheme satisfies both the reconstruction property and the confidentiality property, can it be called a valid secret image scheme. So, we will prove that our scheme has both the reconstruction property and the confidentiality property. For convenience, let us assume that subset A of the participants is composed of at least t participants and A ⊄ A _r (A _r  ∈ Λ _max, r = 1, 2, …, m), where Λ _max is the maximal adversary structure. We will prove our scheme is valid as follows:

• (1) Our scheme satisfies the reconstruction property.

Proof. If the subset A is a qualified subset of participants, it must satisfy A ⊄ A _r and |A| ≥ t. Because A ⊄ A _r , the participants in A can get d ₁, d ₂, …, d _m , and they can compute d by using Eq. (8). Also, c ₁, c ₂, …, c _t can be extracted from the coefficients of F(x) because |A| ≥ t. Then, the participants can get the corresponding pixels of the secret image according to Eq. (9). By repeating this process, the secret image can be reconstructed. Figure 4b shows that the secret image was reconstructed without distortion.

• (2) Our scheme satisfies the confidentiality property.

Proof. If subset A is an unqualified subset of participants, it must satisfy |A| < t or A ∈ Λ _max. If |A| < t, the participants in A cannot reconstruct the (t-1) degree polynomial, F(x), through Lagrange interpolation, so they cannot get c ₁, c ₂, …, c _t and cannot reconstruct the secret image. If A ∈ Λ _max, let us assume that A ⊆ A _r (r = 1, 2, …, m). Because all of the participants in A do not possess d _r in their own array H _r , they cannot get the true value of d according to Eq. (1). So, even though they can get c ₁, c ₂, …, c _t , they cannot reveal the secret image.

4.3 Discussion

Since our scheme is a secret image sharing scheme, the embedding capacity and the quality of shadow images are the two main measurements. We will discuss them as follows. In our scheme, t secret image pixels are to be embedded into ⌈ log _σ P⌉ cover image pixels. If the cover image has H × W pixels, the maximum embedding capacity of our scheme would be t × H × W/⌈ log _σ p⌉. From the value of the maximum embedding capacity, we can see that the larger the value σ is, the higher the maximum embedding capacity is. However, the value of σ also affects the quality of the shadow images. Concerning the two different values of σ, the smaller σ can make the quality of the shadow images better if the values of ⌈ log _σ p⌉ are the same. However, the smaller σ may reduce the quality of the shadow images since the values of ⌈ log _σ p⌉ are different. Thus, we must select an appropriate value of σ to make a tradeoff between the embedding capacity and the quality of the shadow images. Table 3 shows the embedding capacity and distortion for different values of σ. As Table 3 shows, we can choose a smaller σ to guarantee better quality of the shadow image when the capacities are the same.

Table 3 Relationship of the capacity-distortion for different values of σ

In Table 4, we compared our scheme with other related schemes (Yang et al. [29]; Lin et al. [11]; Lin and Chan [10]; Guo et al. [4]). Table 4 indicates that our scheme can reconstruct the secret image losslessly and that the PSNRs of the shadow images are the maximum among all of these schemes for the same embedding capacity, which was 256 × 256 pixels. This means that the quality of the shadow images in our scheme is satisfactory. At the same time, if we choose appropriate values for K and σ, the maximum capacity of our scheme also is satisfactory. In addition, even though all of the schemes are (t, n) threshold secret image sharing schemes, only our scheme achieves the adversary structure. So, the proposed scheme can be used in applications that require both the adversary structure and the (t, n) threshold.

Table 4 Comparisons of the related secret image sharing schemes

5 Conclusions

In this paper, we proposed for the first time a secret image sharing scheme that can achieve both an adversary structure and a (t, n) threshold. In our scheme, we calculated the shadow images in a finite field of size p, which is a large prime number, in order to achieve the adversary structure. And we used the quantization operation to embed the secret data into the cover image’s pixels based on the scheme of Lin and Chan [10]. The secret image can be revealed without any distortion if, and only if, the participants involved satisfy the threshold requirement and the subsets of participants are not in the adversary structure. The experimental results indicated that our scheme can achieve both high-quality shadow images and high embedding capacity.