( k,n ) scalable secret image sharing with multiple decoding options

Abstract

Traditional (k, n) secret image sharing provides all-or-nothing decoding model and (k, n) scalable secret image sharing provides progress decoding model during image reconstruction. Both these two decoding models are significance in various applications. However, the security level for real applications would change due to the dynamical environment, only one single decoding model cannot satisfy the changeable security requirement. In this work, we construct scalable secret image sharing schemes that provides both all-or-nothing and progress decoding models to satisfy the dynamical secure requirement. Each participant in our schemes only needs to keep one initial-shadow. During image reconstruction, the dealer selects the decoding model according to current security requirement, if progress model is chosen, initial shadows can achieve image reconstruction in progress model without any modification; else if all-or-nothing model is chosen, the dealer does not need to resent new shadows to participants, the initial-shadows can be updated to satisfy all-or-nothing model efficiently.

Keywords

Secret image sharing scalable decoding model all-or-nothing progress

1. Introduction

(k, n) secret image sharing (SIS) [1, 2] consists of encoding phase and decoding phase. During encoding phase, a secret image O is divided into n shadows S₁, S₂, …, S_n; During decoding phase, a group of any k or more shadows is capable to reconstruct the entire image O, less than k shadows get nothing on the image. Such reconstruction model is called all-or-nothing decoding model. There are mainly two approaches in (k, n) SIS that achieving all-or-nothing decoding model, polynomial based SIS [3 –5] and visual cryptography based SIS [6 –9]. Polynomial based SIS can reduce shadow size from secret image and recover lossless image, the image reconstruction is based on interpolation operation. Visual cryptography based SIS can reconstruct image by human visual system without any cryptographic computation, but the shadow size is expanded and the recovered image is distort comparing to original image.

Recently, a new category of SIS: (k, n) Scalable SIS scheme was proposed which provides a different decoding model other than all-or-nothing model. In (k, n) scalable SIS scheme, k to n shadows can progressively reconstruct the secret image and less than k shadows still get nothing on the image, and such model is called progress decoding model. There were many works on (k, n) scalable SIS that achieve progress decoding model. In 2007, Wang and Shyu [10] first constructed a (2, n) scalable SIS based on interpolation polynomial. Later, Yang and Huang [11] proposed a general (k, n) scalable SIS to enhance Wang-Shyu’s work [10]. However, those two schemes [10, 11] did not satisfy the property of smooth reconstruction. The schemes [12, 13] not only satisfy progress decoding model but also the property of smooth reconstruction. In [14], Liu et.al published a general approach to reduce shadow size in scalable secret sharing schemes. The works [15 –17] constructed SIS schemes with essential shadows. In those schemes, all the shadows can be categorized into essential shadows and non-essential shadows, and essential shadows have more contributions in image reconstruction than non-essential shadows. Later, Liu and Yang [18] proposed a (k, n) scalable SIS with essential shadows which provides progress decoding model. All above (k, n) scalable SIS were based on interpolation polynomial. There were also scalable SIS schemes that were based on other approaches, for instance, [19, 20] were based on visual cryptography, [21] was based on Boolean operation, [22] was based on linear congruence equation. Comparing to those schemes, polynomial based scalable SIS schemes have advantaged in shadow size and quality of recovered image.

All previous (k, n) SIS or (k, n) scalable SIS provide single decoding model during image reconstruction (all-or-nothing model or progress model). However the secure environment in current applications is much more complicated than ever before, many factors may have influence on the security level in SIS schemes. For example, (1) an increase or decrease in the importance level of the secret image; (2) a change in participants number (i.e., one or more participants joining or leaving the group); (3) a change in the level of mutual trust between participants; and (4) the leakage of some participants’ shadow. A new category of threshold changeable secret sharing scheme [23 –25] have been introduced to solve the problem of dynamical security level, where the threshold k for secret reconstruction can be increased or decreased. However the problem of dynamical secure environment in SIS has not been considered yet. Any single decoding model (all-or-nothing or progress) has secure problem with changeable security environment. For instance, in all-or-nothing model, k or more shadows can recover the same secret image, this model causes shadow redundance when more than k shadows participant in reconstruction, and the redundance shadows would cause additional secure problems. Progress model needs all n shadows to recover entire image, it has low efficiency to recover entire image in a emergency situation. In this paper, we aim to address the problem of dynamical security environment in the filed of SIS, and construct (k, n) scalable SIS schemes that provide both two decoding models. The similar approach of providing multiple decoding options have been used in Chinese reminder based SIS [26 –29]. During image reconstruction, the dealer can decide the decoding model according to current security level. If progress model is selected, k to n initial-shadows can progressively recover the image; else if all-or-nothing model is selected, each participant update his shadow correspondingly to satisfy all-or-nothing decoding model.

The rest of this paper is organized as follows. In Section 2, we introduce Thien-Lin’s polynomial-based (k, n) SIS and Yang-Chu’s (k, n) scalable SIS. Section 3 describes the motivation of our work and constructs two (k, n) scalable SIS schemes that provide both two decoding models. Examples and experimental results are shown in Section 4, then conclusion is summarized in Section 5.

2. Preliminaries

In this part, we introduce some preliminaries to our work. Our proposed schemes are based on interpolation polynomial and extended from Yang-Chu’s (k, n) scalable SIS [12], therefore the original polynomial based (k, n) SIS [1] and Yang-Chu’s scheme [12] are described in this section.

2.1. Polynomial based (k, n) SIS

Thien and Lin introduced a remarkable (k, n) SIS scheme [1] which consists of two phases: Encoding phase and Decoding phase. In first phase, a dealer takes a secret image O as input and invoke an algorithm ${ShadowEn}_{(k, n)}^{Thien - Lin} (O)$ to output n shadows S₁, S₂, …, S_n; in second phase, an image reconstruction algorithm ${ImageRe}_{m}^{Thien - Lin} (\cdot)$ takes a group of m shadows k ≤ m ≤ n. s inputs and outputs a secret image O. The scheme is shown below.

Scheme 1: Thien-Lin’s scheme

Encoding phase:

On input secret image O, invoke ${ShadowEn}_{(k, n)}^{Thien - Lin} (O)$

The dealer divide O into l-non-overlapping k pixel blocks, B₁, B₂, …, B_l.

For k pixel values a_j,0, a_j,1, …, a_j,k-1 in each block B_j, j ∈ [1, l], the dealer generates a k - 1 degree polynomial: f_j (x) = a_j,0 + a_j,1x + a_j,2x² + … , a_j,k-1x^k-1.

Using f_j (x) to compute n shares: v_j,1 = f_j (1) , v_j,2 = f_j (2) , …, v_j,n = f_j (n) , j ∈ [1, l].

Outputs n shadows: S_i = v_1,i||v_2,i||, …, ||v_l,i, i = 1, 2, …, n.

Decoding phase:

On input m shadows S₁, S₂, …, S_m. (m ≥ k), invoke ${ImageRe}_{m}^{Thien - Lin}$ (S₁, S₂, …, S_m)

Compute all k coefficients in f_j (x) from v_1,j, v_2,j, …, v_m,j, j ∈ [1, l] using lagrange formula to recover the block B_j.

Outputs O = B₁||B₂||, …, ||B_l

It is obvious that Thien-Lin’s scheme satisfies all-or-nothing reconstruction model on threshold k that: k or more shadows can reconstruct entire image; less than k shadows get noting on secret image. The size of each shadow S_i in is $| S_{i} | = \frac{| O |}{k}$ , where | · | denotes the size of image.

2.2. Yang-Chu’s (k, n) scalable SIS

In [12], Yang and Chu introduced a (k, n) scalable SIS which is based on Thien-Lin’ work. In this scheme [12], a secret image O is also encoded into n shadows S₁, S₂, …, S_n, and these n shadows achieve progress decoding model other than all-or-nothing decoding model. We use following Scheme 2 to describe Yang-Chu’ scheme.

Scheme 2: Yang-Chu’s scheme

Encoding phase:

On input secret image O. output n. shadows S₁, S₂, …, S_n

The secret image O is segmented into n - k + 1 disjoint sub-images O₁, O₂, …, O_n-k+1, where O₁ has the size $\frac{k | O |}{n}$ , and each other n - k sub-images O₂ - O_n-k+1 has the size $\frac{| O |}{n}$ .

For each sub-image O_j, j ∈ [1, n - k + 1], generate n sub-shadows s_j,1, s_j,2, …, s_j,n using ${ShadowEn}_{(k + j - 1, n)}^{Thien - Lin} (O_{j})$ .

The shadow S_i for participant P_i is S_i = s_1,i||s_2,i|| … ||s_n-k+1,i. Output n shadows S₁, S₂, …, S_n.

Decoding phase:

On input m shadows S₁, S₂, …, S_m. n ≥ m ≥ k,

The sub-images O_j, j ∈ [1, m - k + 1] can be recov ered by ${ImageRe}_{m}^{Thien - Lin} (s_{j, 1}, s_{j, 2}, \dots, s_{j, m})$ where the sub-shadow s_j,i comes from shadow S_i.

Outputs the reconstructed partial image

O^{Partial} = O_{1} | | O_{2} | | \dots | | O_{m - k + 1} .

We can observe that any groups of m shadows k ≤ m ≤ n in Scheme 2 are able to recover a partial image O^Partial with size $\frac{m | O |}{n}$ , and less than k shadows get no information on the secret image. Therefore the n shadows satisfy the progress decoding model with smooth property. In addition, the size of shadow is: $\begin{matrix} | S_{i} | = \frac{k | O |}{n} \times \frac{1}{k} \times \frac{| O |}{n} \times (\frac{1}{k + 1} + \frac{1}{k + 1} +, \dots, + \frac{1}{n}) \\ = \frac{| O |}{n} (1 + \sum_{t = k + 1}^{n} \frac{1}{t}) \end{matrix}$

3. Proposed scheme

3.1. Motivation

Previous SIS schemes provided single decoding model of all-or-nothing model or progress model. However, in real applications, security scenarios are possibly changeable after that the dealer publicly distributes n shadows of (k, n) SIS scheme to all participants, respectively. In this case, single decoding model of all-or-nothing model or progress model is unable to satisfy the requirement of changeable security scenarios. For instance, in all-or-nothing model, k or more shadows can recover the same secret image, when more than k shadows participant in reconstruction, and the redundance shadows have no contribution in image reconstruction and would leak confidential information to attackers. On the other hand, all-or-nothing model is not fit for a secret image where it includes information with different secure levels in different areas. Since the area with higher importance level would requires higher threshold to reconstruction. Progress decoding model provides a more flexible way in image reconstruction than all-or-nothing model. In this model, the secret image can be segmented into sub-images with different secure levels, the sub-image with higher secure level requires more shadows in reconstruction. However, it needs all n shadows to recover entire secret image, when there is an emergence situation that requires recovering entire image immediately, it has low efficiency to gathering all participants. We use Fig. 1 to show all-or-nothing model and progress model respectively.

Our motivation is to addressing the problem of changeable security environment in the filed of SIS, and the solution is to design SIS schemes that achieve both all-or-nothing model (Fig. 1a) and progress model (Fig. 1b) in image reconstruction. When the security level is high, the dealer chooses progress decoding model in image reconstruction, each participated shadows has contribution in reconstruction, the sub-image with higher secure level requires more shadows in reconstruction; when security level is decreased or the reconstruction situation is emergency, all-or-nothing model is selected, where the entire image can be recovered more efficiently. The proposed schemes satisfy following conditions:

Fig.1

(a) All-or-nothing model (b) progress model.

During Encoding phase, each participant only receives one initial-shadow from dealer.

In Decoding Phase, dealer selects one decoding model from progress model and all-or-nothing model according to current security requirement.

If progress model is selected, k to n partici pants can recover image progressively using their initial-shadows.

Otherwise if all-or-nothing model is selected, participants update their shadows correspondingly, then any group of k or more updated shadows are able to recover entire image.

3.2. Proposed schemes

In this part, we propose two (k, n). scalable SIS schemes that provide both two decoding models. Our proposed schemes are based on Yang-Chu’s (k, n) scalable SIS scheme, which are described in following Scheme 3 and Scheme 4 respectively.

Scheme 3:

Encoding phase:

On input secret image O. output n shadows S₁, S₂, …, S_n

The secret image O is segmented in to n - k + 1. isjoint sub-images O₁, O₂, …, O_n-k+1, where O₁ has the size $\frac{k | O |}{n}$ , and each other n - k sub-images O₂ - O_n-k+1 has the size $\frac{| O |}{n}$ .

For sub-image O₁, generate n. ub-shadows s_1,1, s_1,2, …, s_1,n using ${ShadowEn}_{(k, n)}^{Thien - Lin} (O_{1})$ .

For each sub-images O_j, j ∈ [2, n - k + 1],

Segment O_j into l disjoint k-pixels blocks, such that: $O_{j} = B_{j, 1}^{K} | | B_{j, 2}^{k} | | \dots | | B_{j, l}^{k}$ .

Each k-pixels block $B_{j, t}^{k}$ is expanded into a k + j - 1-pixels block $B_{j, t}^{k + j - 1} = B_{j, t}^{k} | | p_{1} p_{2} \dots p_{j - 1}$ . p₁, p₂, …, p_n-k are n - k pixels that are randomly selected by dealer. Afterwards the sub-image O_j is expanded to, such that $O_{j}^{'} = B_{j, 1}^{k + j - 1} | | B_{j, 2}^{k + j - 1} | | \dots | | B_{j, l}^{k + j - 1}$ .

For each $O_{j}^{'}$ , generate n sub-shadows s_j,1, s_j,2, …, s_j,n using ${ShadowEn}_{(k + j - 1, n)}^{Thien - Lin} (O_{j}^{'})$ .

The shadow S_i for participant P_i is:

S_i = s_1,i||s_2,i|| … ||s_n-k+1,i. Output n shadows S₁, S₂, …, S_n.

Decoding phase:

The dealer chooses all-or-nothing model or progress model according to current security requirement.

If progress model is chosen.

Any group of m shadows (k ≤ m ≤ n) can recover using ${ImageRe}_{m}^{Thien - Lin} (s_{j, 1}, s_{j, 2}, \dots, s_{j, m})$ where the sub-shadow s_j,i comes from shadow S_i.

The sub-shadows O₂ - O_m-k+1 can be extracted from expanded sub-images, then the partial image O^Par = O₁||O₂|| … ||O_m-k+1 is recovered.

If all-or-nothing model is chosen.

The dealer generates and publishes n - k Polynomials: g_j (x) = p₁x^k + p₂x^k+1 + … + p_jx^k+j-1, j = 1, 2, …, n - k.

Without loss of generality, suppose P₁ - P_k participate in image reconstruction. The original shadow of P_i is S_i = s_1,i||s_2,i|| … ||s_n-k+1,i, P_i computes $s_{j, i}^{'} = s_{j, i} - g_{j - 1} (i)$ , j = 2, 3, …, n - k + 1, then the original shadow S_i can be updated to $S_{i}^{update}$ by: $S_{i}^{update} = s_{1, i} | | s_{2, i}^{'} | | \dots | | s_{n - k + 1, i}^{'}$ .

Using these k updated shadows: $S_{1}^{update} - S_{k}^{update}$ , all sub-images O₁ - O_n-k+1 can be recovered using ${ImageRe}_{k}^{Thien - Lin}$ and thus the entire image O = O₁||O₂|| … ||O_n-k+1 is reconstructed.

The following theorem proves that Scheme 3 provides both all-or-nothing model and progress model during image reconstruction.

Theorem 1. The proposed Scheme 3 provides both all-or-nothing model and progress model in image reconstruction.

Proof. In Scheme 3, the secret image O is segmented into n - k + 1 sub-images O₁, O₂, …, O_n-k+1, and each sub-image O_j, j ∈ [1, n - k + 1] is encrypted into n sub-shadows using a (k + j - 1, n) SIS scheme. Since the original shadow S_i is a combination of n - k + 1 sub-shadows where these n - k + 1 sub-shadows come from n - k + 1 different sub-images respectively, k to n original shadows can reconstruct the image O in a progress model. i.e., Any m original shadows (k ≤ m ≤ n). can reconstruct sub-images O₁ - O_m, the proportion of partial image O^Partial = O₁||O₂|| … ||O_m to entire image O is $\frac{m}{n}$ . Thus, Scheme 3 provides progress model with n original shadows. When all-or-nothing model is selected, the dealer publishes n - k polynomials g_j (x) = p₁x^k + p₂x^k+1 + … + p_jx^k+j-1, j = 1, 2, …, n - k. Any k participants can update their original shadows by $S_{i}^{update} = s_{1, i} | | s_{2, i}^{'} | | \dots | | s_{n, - k + 1, i}^{'}$ , where $s_{j, i}^{'} = s_{j, i} - g_{j - 1} (i)$ , j = 2, 3, …, n - k + 1. Since s_j,i is generated from k + j - 1-pixels blocks $B_{j, t}^{k + j - 1}$ , t = 1, 2, …, l using polynomial interpolation, where each k + j - 1-pixels block is expanded from k-pixels block $B_{j, t}^{k}$ by $B_{j, t}^{k + j - 1} = B_{j, t}^{k} | | p_{1} p_{2} \dots p_{j - 1}$ , and g_j-1 (x) = p₁x^k + p₂x^k+1 + … + p_j-1x^k+j-2, it is easy to observe that $s_{j, i}^{'} = s_{j, i} - g_{j - 1} (i)$ is the interpolations on k-pixels blocks $B_{j, 1}^{k} - B_{j, l}^{k}$ , any k sub-shadows $s_{j, i}^{'}$ can reconstruct the sub-image $O_{j} = B_{j, 1}^{k} | | B_{j, 2}^{k} | | \dots | | B_{j, l}^{k}$ . The threshold for reconstructing sub-image O_j, j ∈ [2, n - k + 1] is reduced to k from k + j - 1. Therefore any k updated shadows $S_{i}^{update}$ can reconstruct the entire image O.

In Scheme 3, the initial-shadow for each participant is S_i = s_1,i||s_2,i|| … ||s_n-k+1,i. s_1,i is a sub-shadow of O₁ using ${ShadowEn}_{(k, n)}^{Thien - Lin} (O_{1})$ , thus the size of s_1,i is $| s_{1, i} | = \frac{| O_{1} |}{k}$ . For sub-shadows s_j,i, j = 2, 3, …, n - k + 1, they are generated from ${ShadowEn}_{(k + j - 1, n)}^{Thien - Lin} (O j')$ , the size of s_j,i satisfies $| s_{j, i} | = \frac{| O_{j}^{'} |}{k + j - 1}$ . Since is expanded from sub-image O_j by adding j - 1 pixels in each k-pixels block, the size of $O_{j}^{'}$ is $| {O^{'}}_{j} | = \frac{(k + j - 1) | O_{j} |}{k}$ . Therefore $| s_{j, i} | = \frac{| O_{j} |}{k}, j = 2, 3, \dots, n - k + 1$ and the size of shadow S_i is $| S_{i} | = \sum_{j = 1}^{n - k + 1} | s_{j, i} | = \frac{| O |}{k}$ . We can see that the size of shadow in Scheme 3 is expended from Yang-Chu’s scheme, where the size of shadow is $| S_{i} | = \frac{| O |}{n} (1 + \sum_{t = k + 1}^{n} \frac{1}{t})$ .

In Scheme 3, the dealer needs to publish information of n - k pixels p₁ - p_n-k to achieve all-or nothing model, which increase the cost of communication during reconstruction phase. Although the cost of additional communication is inevitable, we can reduce the cost by publishing less information for achieving all-or-nothing model. Therefore we construct another (k, n) scalable SIS schemes that providing two decoding models in following Scheme 4.

Scheme 4:

Encoding phase:

The dealer generates n shadows S₁, S₂, …, S_n using Yang-Chu’s approach, and sends each shadow S_i to P_i.

For each sub-image O_j, j ∈ [2, n - k + 1]

The dealer selects j - 1 IDs d_(j,1), d_(j,2), …, d_(j,j-1) other than 1, 2, …, n, and computes j - 1 sub-shadows s_{j,d_(j,1)}, s_{j,d_(j,2)}, …, s_{j,d_(j,j-1)} on IDs d_(j,1), d_(j,2), …, d_(j,j-1) respectively.

The dealer randomly selects a group of n - k + 1 participants in {P₁, P₂, …, P_n} and then sends j - 1 subhadows s_{j,d_(j,1)}, s_{j,d_(j,2)}, …, s_{j,d_(j,j-1)} to each of these n - k + 1 participants, but keeps the IDs d_(j,1), d_(j,2), …, d_(j,j-1) secretly.

Decoding phase:

The dealer chooses all-or-nothing model or progress model according to current security level.

If progress model is chosen. Any group of m initial-shadows (k ≤ m ≤ n) in {S₁, S₂, …, S_n} can recover sub-images O₁, O₂, …, O_m-k+1 using Yang-Chu’s approach.

If all-or-nothing model is chosen.

The dealer publishes the j - 1 IDs d_(j,1), d_(j,2), …, d_(j,j-1) for the each sub-image O_j, j ∈ [2, n - k + 1].

For any group of k participants, they can gather k + j - 1 sub-shadows on each sub-image O_j, j = 1, 2, …, n - k + 1 using their initial-shadows S_i and the public information. Since the sub-image O_j is encrypted into sub-shadows using (k + j - 1, n) SIS, then O_j can be reconstructed from these k + j–1 sub-shadows. As a result, the entire image O = O₁||O₂|| … ||O_n-k+1 can be recovered.

We use Theorem 2 to analyze the decoding model of Scheme 4.

Theorem 2. The proposed Scheme 4 provides both all-or-nothing model and progress model in image reconstruction.

Proof. In Scheme 4, the n initial-shadows are generated from secret image O using Yang-Chu’s approach, therefore k to n initial-shadows can reconstruct the image in progress model. When all-or-nothing model is selected, the dealer publishes all the j - 1 IDs d_j,1, d_j,2, …, d_j,j-1 for each sub-image O_j. For any group of at least k participants, they can get additional j - 1 sub-shadows on each sub-image O_j. Since the j - 1 sub-shadows on O_j is sent to randomly n - k + 1 participants, any group of k out of n participants includes at least one participant who receives these j - 1 sub-shadows. Together with the initial-shadows, these k participants can gather k + j - 1 sub-shadows on each sub-image O_j in total. Because the sub-image O_j is encrypted into sub-shadows using (k + j - 1, n) SIS, then any k participants can recover O_j with k + j - 1 sub-shadows. Notice that if the IDs are not published, k participants can not recover O_j using interpolation even they know s_{j,d_j,1}, s_{j,d_j,2}, …, s_{j,d_j,j-1}. As a result, the entire image can be reconstructed by any k participants in Scheme 4, it satisfies all-or-nothing model.

The initial-shadow S_i in Scheme 4 is generated using Yang-Chu’s approach, and the size of shadow is $| S_{i} | = \frac{| O |}{n} (1 + \sum_{t = k + 1}^{n} \frac{1}{t})$ . The additional sub-shadow on each sub-image O_j has the size of $\frac{| O |}{(k + j - 1) n}$ , therefore the size of total additional sub-shadows on O_j is $\frac{(j - 1) (n - k + 1) | O |}{(k + j - 1) n}$ , the size of all sub-shadows in Scheme 4 is $| S_{add} | = \frac{n - k + 1}{n} \sum_{j = 2}^{n - k + 1} \frac{(j - 1) | O |}{(k + j - 1)}$ . Thus the average shadow size in Scheme 4 is $| S_{i} | + \frac{| S_{add} |}{n}$ . The following theorem proves that the average shadow size in Scheme 4 is more than shadow size in Scheme 3.

Theorem 3. The average shadow size in Scheme 4 is more than shadow size in Scheme 3.

Proof. The total shadow size in Scheme 4 is; the total shadow size in Scheme 3 is $| S^{3} | = \frac{n | O |}{k}$ .

It is easy to prove that $| S_{4} | - | S_{3} | = | O | \sum_{i = k + 1}^{n} (\frac{(n - k + 1) (i - k)}{ni} - \frac{i - k}{ki}) = (\frac{n - k + 1}{n} - \frac{1}{k}) | O | \sum_{i = k + 1}^{n} (\frac{i - k}{i})$ . Since $\frac{n - k + 1}{n} - \frac{1}{k} = \frac{(n - k) (k - 1)}{nk} > 0$ and $\frac{i - k}{i} > 0$ , we can get the conclusion that |S₄| > |S₃|. Therefore the average shadow size in Scheme 4 is more than shadow size in Scheme 3.

As a trade off for the shadow size expansion, the published information for all-or-nothing model in Scheme 4 is less than Scheme 3. In Scheme 3, the published information are n - k pixels p₁, p₂, …, p_n-k; in Scheme 4, the dealer needs to publish j - 1 IDs for the additional sub-shadows on each sub-shadow O_j. Since the size of ID is much smaller than pixel, the amount of published information in Scheme 4 is less than the published information in Scheme 3. The computational complexity for image reconstruction in Scheme 3 is a little better than Scheme 4. In Scheme 3, the reconstruction under all-or-nothing model is based on Lagrange interpolation with degree k - 1 for all sub-images, the computational complexity is O (k · log k); in Scheme 4, the reconstruction under all-or-nothing model is based on Lagrange interpolation with degree k + j - 2 for each sub-images O_j, j = 1, 2, …, n - k + 1, the computational complexity is O ((k + j - 1) · log(k + j - 1)).

4. Examples and experiments

In this section, we use examples to illustrate the process of shadow generation and image reconstruction in proposed schemes. Thus three examples are listed respectively, Example 1 shows the process in Yang-Chu’s scheme which provides only progress model during image reconstruction; Examples 2 and 3 describe the processes of proposed Scheme 3 and Scheme 4 respectively.

In all examples, we use scalable (k = 3, n = 5) threshold to encode secret image O into n = 5 shadows. According to Yang-Chu’s approach and proposed schemes, the secret image O is first segmented into n - k + 1 =3 sub-images O₁, O₂, O₃, where the sizes of each sub-image are $| O_{1} | = \frac{3 | O |}{5}, | O_{2} | = \frac{| O |}{5}, | O_{3} | = \frac{| O |}{5}$ respectively.

Example 1. Yang-Chu’s scheme

Assume that O₁ consists of three 3 pixels blocks B_1,1 = (67, 98, 157), B_1,2 = (51, 215, 175), B_1,3 = (243, 41, 91), O₂ consists of one 4-pixels block B_2,1 = (77, 23, 103, 213) and O₃ consists of one 5-pixels block B_3,1 = (89, 151, 123, 65, 180).

•Encoding Phase:

For sub-image O₁, generate three k - 1 degree polynomials: $\begin{matrix} f_{1, 1} (x) = 67 + 98 x + 157 x^{2}, \\ f_{1, 2} (x) = 51 + 215 x + 175 x^{2}, \\ f_{1, 3} (x) = 243 + 41 x + 91 x^{2} \end{matrix}$ for each block B_1,1, B_1,2, B_1,3 respectively, and then compute the values f_1,i (j), i = 1, 2, 3, j = 1, 2, 3, 4, 5. Thus the sub-shadow s_1,j, j ∈ [1, 5]. for each participant P_j is s_1,j = {f_1,1 (j) , f_1,2 (j) , f_1,3 (j)}.

For sub-images O₂, O₃, generate f₂ (x) =77 + 23x + 103x² + 213x³ and f₃ (x) =89 + 151x + 123x² + 65x³ + 180x⁴ respectively. The sub-shadow s_2,j, s_3,j, j ∈ [1, 5] for each participant P_j is s_2,j = f₂ (j) , s_3,j = f₃ (j).

The 5 shadows S_j, j ∈ [1, 5] are: $\begin{matrix} S_{1} = (s_{1, 1}, s_{2, 1}, s_{3, 1}) = ({71, 190, 124}, 165, 106) \\ S_{2} = (s_{1, 2}, s_{2, 2}, s_{3, 2}) = ({138, 177, 187}, 231, 16) \\ S_{3} = (s_{1, 3}, s_{2, 3}, s_{3, 3}) = ({17, 12, 101}, 47, 163) \end{matrix}$ $\begin{matrix} S_{4} = (s_{1, 4}, s_{2, 4}, s_{3, 4}) = ({210, 197, 106}, 138, 191) \\ S_{5} = (s_{1, 5}, s_{2, 5}, s_{3, 5}) = ({215, 230, 213}, 25, 48) \end{matrix}$

•Decoding phase:

The image O can be reconstructed from 3 to 5 shadows under progress model. Any 3 shadows can reconstruct sub-image O₁, any 4 shadows can reconstruct O₁ and O₂, all 5 shadows can reconstruct the entire image O = O₁||O₂||O₃.

Example 2. Proposed Scheme 3

Assume that O₁ consists of three 3 pixels blocks B_1,1 = (67, 98, 157), B_1,2 = (51, 215, 175), B_1,3 = (243, 41, 91), O₂ consists of one 3-pixels block B_2,1 = (77, 23, 103) and O₃ consists of one 3-pixels block B_3,1 = (89, 151, 123).

•Encoding Phase:

For sub-image O₁, generate three k - 1 degree polynomials: f_1,1 (x) =67 + 98x + 157x², f_1,2 (x) =51 + 215x + 175x², f_1,3 (x) =243 + 41x + 91x²

For each block B_1,1, B_1,2, B_1,3 respectively, and then compute the values f_1,i (j), i = 1, 2, 3, j = 1, 2, 3, 4, 5. Thus the sub-shadow s_1,j, j ∈ [1, 5] for each participant P_j is s_1,j = {f_1,1 (j) , f_1,2 (j) , f_1,3 (j)}.

For sub-image O₂, the 3-pixels block B_2,1 is first expanded to a 4-pixels block $B_{2, 1}^{4} = (77, 23, 103, 40)$ where p₁ = 40 is a random pixel selected by dealer. Then generate f₂ (x) =77 + 23x + 103x² + 40x³, the sub-shadow on O₂ is s_2,j = f₂ (j) , j ∈ [1, 5] for each participant P_j.

For sub-image O₃, the 3-pixels block B_3,1 is first expanded to a 5-pixels block $B_{3, 1}^{5} = (89, 151, 123, 78, 39)$ where p₂ = 78, p₃ = 39 is two random pixels selected by dealer. Then generate f₃ (x) =89 + 151x + 123x² + 78x³ + 39x⁴, the sub-shadow on O₃ is s_3,j = f₃ (j) , j ∈ [1, 5] for each participant P_j

The 5 shadows S_j, j ∈ [1, 5] are: $\begin{matrix} S_{1} = (s_{1, 1}, s_{2, 1}, s_{3, 1}) = ({71, 190, 124}, 243, 229) \\ S_{2} = (s_{1, 2}, s_{2, 2}, s_{3, 2}) = ({138, 177, 187}, 102, 123) \\ S_{3} = (s_{1, 3}, s_{2, 3}, s_{3, 3}) = ({17, 12, 101}, 145, 137) \\ S_{4} = (s_{1, 4}, s_{2, 4}, s_{3, 4}) = ({210, 197, 106}, 110, 67) \\ S_{5} = (s_{1, 5}, s_{2, 5}, s_{3, 5}) = ({215, 230, 213}, 237, 143) \end{matrix}$

•Decoding phase:

– If progress model is selected:

The image O can be reconstructed from 3 to 5 shadows under progress model. Any 3 shadows can reconstruct sub-image O₁, any 4 shadows can reconstruct the 4-pixels block $B_{2, 1}^{4} = (77, 23, 103, 40)$ , then sub-image O₂ = (77, 23, 103) can be extracted together with O₁; all 5 shadows can reconstruct the 5-pixels $B_{3, 1}^{5} = (89, 151, 123, 78, 39)$ , then the sub-image O₃ can be extracted together with O₁, O₂.

– If all-or-nothing model is selected.

The dealer publishes p₁ = 40, p₂ = 78, p₃ = 39, then any k = 3 participants can generate g₁ (x) = p₁x³ and g₂ (x) = p₂x³ + p₃x⁴. The participants update their sub-shadows by: $s_{i, j}^{update} = s_{i, j} - g_{i} (j)$ for i = 1, 2, j = 1, 2, …, 5. The upted shadow for P_j is $S_{j}^{update} = (s_{i, j}, s_{2, j}^{update}, s_{3 . j}^{update})$ . Afterwards, any k = 3 or more updated shadows can reconstruct the entire image O.

Example 3. Proposed Scheme 4

•Encoding Phase:

The shadows in Scheme 4 are same as in Example 1. $\begin{matrix} S_{1} = (s_{1, 1}, s_{2, 1}, s_{3, 1}) = ({71, 190, 124}, 165, 106) \\ S_{2} = (s_{1, 2}, s_{2, 2}, s_{3, 2}) = ({138, 177, 187}, 231, 16) \\ S_{3} = (s_{1, 3}, s_{2, 3}, s_{3, 3}) = ({17, 12, 101}, 47, 163) \\ S_{4} = (s_{1, 4}, s_{2, 4}, s_{3, 4}) = ({210, 197, 106}, 138, 191) \\ S_{5} = (s_{1, 5}, s_{2, 5}, s_{3, 5}) = ({215, 230, 213}, 25, 48) \end{matrix}$

The dealer selects one additional ID 6 for O₂ and two additional IDs 7,8 for O₃, and computes one sub-shadow s_2,6 = 233 on O₂, two sub-shadows s_3,7 = 59, s_3,8 = 123 on O₃ using the approach in Yang-Chu’s approach.

Afterwards the sub-shadows s_2,6 is sent to randomly n - k + 1 =3 participants, and the sub-shadows s_3,7, s_3,8 are sent to randomly n - k + 1 =3 participants. The IDs {6,7,8} are kept secretly.

•Decoding phase:

– If progress model is selected:

The image O can be reconstructed from 3 to 5 original shadows under progress model as in Example 1

– If all-or-nothing model is selected.

The dealer publishes the IDs 6,7,8. Any k = 3 participants can gather enough sub-shadows on each O₁, O₂, O₃. Then the entire image O can be recovered by interpolation.

Next we use an experiment to show the results of proposed Scheme 3 and Scheme 4 in (k = 3, n = 5) threshold. The secret image O which is shown in Fig. 2 is a car. This image O is segmented into 3 sub-images O₁, O₂, O₃, where O₂ contains the logo of car and O₃ contains the information of licence plate. The size of O₁, O₂, O₃ are $\frac{3}{5}, \frac{1}{5}, \frac{1}{5}$ on image O respectively, and the importance of these three sub-images is O₃ > O₂ > O₁. Figure 3 shows the initial-shadows S₁ - S₅ of Scheme 3 and Scheme 4 respectively. The size of shadow using Scheme 3 is $\frac{| O |}{3}$ , and the average size of shadow using Scheme 4 is $\frac{46 | O |}{125}$ . In both Scheme 3 and Scheme 4, 3 to 5 initial-shadows can recover image in progress model; on the other hand, any 3 or more updated shadows can recover image in all-or-nothing model.

Fig.2

Secret image and sub-images.

Fig.3

(a) Shadows using Scheme 3 (b) shadows using Scheme 4.

5. Conclusion

Single all-or-nothing model or progress model cannot satisfy the changeable security requirement in threshold secret image sharing scheme for real applications.

In this paper, we first consider the problem of dynamical security environment in the field of image secret sharing, and propose two (k, n) scalable secret image sharing schemes that provide both progress model and all-or-nothing model in image reconstruction. Our schemes are based on interpolation polynomial and extended from Yang-Chu’s (k, n) scalable SIS scheme. Each participant only keeps one initial-shadow for progress model. When all-or-nothing model is selected, initial-shadows can be updated efficiently to satisfy all-or-nothing model.

Footnotes

Acknowledgments

This work was supported by National Natural Science Foundation of China under Grant No. 61502384, 61571360; and the Shaanxi Provincial Natural Science Basic Research Program (No.2019JQ-736). This research was supported in part by Ministry of Science and Technology (MOST), under Grant 105-2221-E-259-007-MY2.

References

C.C.

Thien and

J.C.

Lin , Secret image sharing, Computers and Graphics 26(5) (2002), 765–770.

Naor and

Shamir , Visual cryptography, Proc of EUROCRYPT1994, LNCS 950, 1995, pp. 1–12.

R.Z.

Wang and

C.H.

Su , Secret image sharing with smaller shadow images, Pattern Recognition Letters 27 (2006), 551–555.

C.C.

Wu ,

S.J.

Kao and

M.S.

Hwang , A high quality image sharing with steganography and adaptive authentication scheme, Journal of Systems and Software 84 (2011), 2196–2207.

Liu

Y.X.

, Yang

C.N.

, Wu

C.M.

, Sun

Q.D.

and Bi

, Threshold changeable secret image sharing scheme based on interpolation polynomial, Multimedia Tools and Applications 78 (2019), 18653–18667.

S.J.

Shyu and

H.W.

Jiang , General constructions for threshold multiple-secret visual cryptography Schemes, IEEE Transactions on Information Forensics and Security 8 (2013), 733–743.

C.N.

Yang and

Y.Y.

Yang , New extended visual cryptography schemes with clearer shadow images, Information Sciences 271 (2014), 246–263.

Lal and Prof.

Sharma , Load balancing and its challenges in cloud computing: A review paper, International Journal of Innovative Research in Computer and Communication Engineering (IJIRCCE) 5(12) (2017).

T.H.N.

Le ,

C.C.

Lin ,

C.C.

Chang and

H.B.

Le , A high quality and small shadow size visual secret sharing scheme based on hybrid strategy for grayscale images, Digital Signal Processing 21 (2011), 734–745.

10.

J.S.

Lee ,

C.C.

Chang ,

N.T.

Huynh and

H.Y.

Tsai , Preserving user-friendly shadow and high-contrast quality for multiple visual secret sharing technique, Digital Signal Processing 40 (2015), 131–139.

11.

R.Z.

Wang and

S.J.

Shyu , Scalable secret image sharing, Signal Processing: Image Communication 22(4) (2007), 363–373.

12.

C.N.

Yang and

S.M.

Huang , Constructions and properties of k out of n scalable secret image sharing, Optics Communications 283(9) (2010), 1750–1762.

13.

C.N.

Yang and

Y.Y.

Chu , A general (k,n) scalable secret image sharing scheme with the smooth scalability, Journal of Systems and Software 84(10) (2011), 1726–1733.

14.

Y.Y.

Lin and

R.Z.

Wang , Scalable secret image shaing with smaller shadow images, IEEE Signal Processing Letters 17(3) (2010), 316–319.

15.

Y.X.

Liu ,

C.N.

Yang and

P.H.

Yeh , Reducing shadow size in smooth scalable secret image sharing, Security and Communication Networks 7(12) (2014), 2237–2244.

16.

Li ,

Liu and

C.N.A.

Yang , Construction Method of (t,k,n)-essential secret image sharing scheme, Signal Processing: Image Communication 65 (2018), 210–220.

17.

Lakhanpal and Prof.

Agrawal , Enhanced secure mechanism for ARP poisoning and MITM attack, International Journal of Innovative Research in Computer and Communication Engineering (IJIRCCE) 6(1) (2018).

18.

Li ,

C.N.

Yang and

Zhou , Essential secret image sharing scheme with the same size of shadows, Digital Signal Processing 50 (2016), 51–60.

19.

C.N.

Yang ,

Li ,

C.C.

Wu and

S.R.

Cai , Reducing shadow size in sssential secret image sharing by conjunctive herarchical approach, Signal Processing: Image Communication 31 (2015), 1–9.

20.

Y.X.

Liu and

C.N.

Yang , Scalable secret image sharing scheme with essential shadows, Signal Processing: Image Communication 58 (2017), 49–55.

21.

C.N.

Yang ,

H.W.

Shih ,

C.C.

Wu and

Harn , K out of n region incrementing scheme in visual cryptography, IEEE Transactions on Circuits and Systems for Video Technology 22(5) (2012), 799–809.

22.

Maheswari and

Chitra , A novel approach for software defect prediction using learning algorithms, International Journal of Innovative Research in Computer and Communication Engineering (IJIRCCE) 5(11) (2017).

23.

C.N.

Yang ,

Y.C.

Lin and

C.C.

Wu , Region in region incrementing visual cryptography scheme, Proc IWDW 2012, LNCS 7809 (2013), 449–463.

24.

Y.X.

Liu ,

C.N.

Yang ,

S.Y.

Wu and

Y.S.

Chou , Progressive (k,n) secret image sharing schemes based on Boolean operations and covering codes, Signal Processing: Image Communication 66 (2018), 77–86.

25.

L.T.

Liu ,

Y.L.

Lu ,

X.H.

Yan and

H.X.

Wan , Greyscale-images-oriented progressive secret sharing based on the linear congruence equation, Multimedia Tools and Applications 2 (2017), 1–28.

26.

Zhang ,

Y.M.

Chee ,

Ling ,

Liu and

Wang , Threshold changeable secret sharing schemes revisited, Theoretical Computer Science 418 (2012), 106–115.

27.

Harn and

C.F.

Hsu , Dynamic threshold secret reconstruction and its application to the threshold cryptography, Information Processing Letters 115(11) (2015), 851–857.

28.

Yuan ,

Li ,

Guo ,

K.-K.R.

Choo and

Ren , Novel threshold changeable secret sharing schemes based on polynomial interpolation, PloS One 11(10) (2016), 1–19.

29.

Yan ,

Lu ,

Liu ,

Liu and

Yang , Chinese remainder theorem-based two-in-one image secret sharing with three decoding options, Digital Signal Processing 82 (2018), 80–90.