# Secret Image Sharing Scheme with Threshold Changeable Capability

Authors: Lifeng Yuan; Mingchu Li; Cheng Guo; Weitong Hu; Xinjian Luo
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

In secret image sharing schemes, the threshold may have to be adjusted in case of changes in the security policy and the adversary structure before recovering the secret image. For example, if participants leave the group, their stego images are useless to them and may not be kept safely. As a result, these images can be easily stolen and utilized by intruders, which reduces the security of the scheme. To solve this problem, we propose a novel threshold changeable secret image sharing scheme withN potential changeable thresholds t
1
,
t
2
,
…
,
t
N. By preparing advance shares for thresholds t
1
,
t
2
,
…
,
t
N and using the two-variable one-way function to generate the identification value, we can change the threshold when necessary. The experiments show that the quality of the stego images in our scheme is satisfactory and the secret image can be recovered without distortion. Moreover, the security analysis shows that we can change the threshold safely.


---

## Body

## 1. Introduction

The rapid development of Internet has brought much more convenience to people’s daily lives, but it has also brought security risks. In the open communication networks, it is easy to intercept, modify, fabricate, and even destroy data. Modern cryptography provides an effective solution to ensure the security of information. Since the design details of most cryptography algorithms are public, the security of the encrypted information depends on the security of the key. Thus, it is important that the key be kept safely.In order to solve this secret key protecting problem, Shamir [1] and Blakley [2] proposed (
t
,
n
) threshold secret sharing schemes independently. Shamir constructed his scheme based on polynomial interpolation, while Blakley provided a geometric construction. In a (
t
,
n
) threshold secret sharing scheme, a dealer encodes and divides the secret into n shares that are distributed to n participants, and then t or more participants can recover the secret, but less than t participants cannot get any information about the secret. In 1994, Naor and Shamir [3] proposed a visual secret image sharing scheme. Utilizing the (
t
,
n
) threshold secret sharing technique, the secret image is encoded and divided into n random-noise-like images (called share images), and these share images are distributed to the participants, so that any t or more participants can see the secret image by stacking their share images together. However, the random-noise-like images, which are meaningless, can easily attract malicious intruders’ attention. To solve this problem, Lin and Tsai [4] provided a (
t
,
n
) threshold image sharing scheme using steganography. In their scheme, the shares are camouflaged in a cover image to form the stego images, which cannot be distinguished by the human eye, so these shares can be concealed from intruders. At the same time, their scheme embeds watermarks into the stego images for verification.In recent years, various secret image sharing techniques have been developed rapidly. In 2007, Yang et al. [5] proposed an image sharing scheme that can improve the authentication ability, but it degraded the quality of the stego images. In 2009, Lin et al. [6] utilized the modulo operation to camouflage the secret data in the cover image to overcome this drawback. Their scheme guarantees higher quality stego images, and it can reconstruct the secret image and the cover image without distortion. In 2010, Lin and Chan [7] proposed an invertible secret image sharing scheme with satisfactory quality of the stego images. It can recover the secret image and the cover image without distortion, and it allows for a large capacity of secret data embedding. In reality, the single (
t
,
n
) threshold access structure cannot satisfy the demand of complex applications. To solve this problem, Guo et al. [8] first proposed a hierarchical secret image sharing, based on polynomial interpolation in 2012, which divided the secret share images into different hierarchies and set different threshold values. Also in 2012, Guo et al. [9] proposed another novel hierarchical secret image sharing scheme based on monotone span programs (MSPs). In 2013, Ulutas et al. [10] proposed an invertible secret image sharing scheme using modification direction and the modulo operation. Their scheme can improve the quality of the stego images effectively when grey-scale cover image is used, and it can also obtain acceptable quality stego images when dithered cover image is used. In 2014, Pakniat et al. [11] used cellular automata and Birkhoff interpolation to propose a novel secret image sharing scheme with hierarchical threshold access structure. In this scheme, each authorized subset of participants is able to recover the secret image and the cover image without distortion, and they can also check the validity of the secret image.Before recovering the secret image, the security policies and adversary structures may change, so it may be necessary to adjust the threshold. For example, (1) the importance level of the secret image is increased or decreased; (2) some participants join or leave the group; (3) the mutual trust of participants is strengthened or weakened; (4) the adversary might have corrupted more thann
-
t participants. Currently, there is not a secret image sharing scheme that can change the threshold after distributing the stego images and before recovering the secret image. Therefore, it is necessary to set up a changeable threshold secret image sharing scheme.Currently, many researchers are interested in secret sharing schemes, especially threshold changeable secret sharing schemes. In 1991, Laih et al. [12] proposed the first threshold changeable secret sharing scheme. In recent years, some researchers have been developing threshold changeable secret sharing schemes based on various techniques, such as (1) the share redistributing technique in [13–15]; (2) the lattice basis reduction technique in [16–18]; (3) the redundant shares technique in [19, 20]; and (4) the advance shares technique in [21]. In 1997, Desmedt and Jajodia [13] used the share redistributing technique to propose a threshold changeable secret sharing scheme without the dealer’s participation after the initialization phase. Some similar schemes can be found in [14, 15]. In these schemes, if the threshold needs to be adjusted, each original share is split into smaller shares which are then redistributed to all participants in the new access structure. Each participant P
i can combine all received smaller shares into one new share s
i by a suitable linear combination; thus each participant only has to store s
i. Note that all participants must simultaneously keep mutual secure communication channels. However, this may be impractical when the threshold changes, especially in the event of an urgent threshold change, so many schemes based on broadcasting have been proposed. In 1999, Martin et al. [22] provided a general model for threshold changeable secret sharing schemes and also provided two threshold schemes which were based on polynomial interpolation and geometric construction. In 2005, Barwick et al. [23] proposed a novel threshold changeable secret sharing scheme based on broadcasting, which can minimize the storage space required for secret sharing and limit the size of the broadcast information in low-bandwidth environment. In 2007, Steinfeld et al. [18] provided a lattice-based threshold changeable secret sharing scheme in which the threshold can be increased by partial updating of shares. In 2012, Zhang et al. [21] also proposed two threshold changeable secret sharing schemes. In their schemes, the advance shares, which have a one-to-one relationship with all potential thresholds, are prepared in the initialization phase, and then the new threshold can be validated by broadcasting related information.Inspired by Zhang et al.’s work [21], we propose a novel (
{
t
1
,
t
2
,
…
,
t
N
}
,
n
) threshold changeable secret image sharing scheme that can adjust the threshold to t
i (1
≤
i
≤
N) dynamically by broadcasting information. Since the novel characteristic of our scheme is not available in the existing secret image sharing schemes, it has the potential to work in many applications. Our scheme has the following characteristics:(1)
The quality of stego images is satisfactory, and the secret image can be recovered without distortion.
(2)
The problem with Zhang et al.’s scheme, that is, that the encrypted shares are too large to be camouflaged in the cover image to form the stego images, is solved by our scheme.
(3)
The threshold can be adjusted in case of changes in the security policy or the adversary structure, and our scheme remains secure after these changes are made.The rest of this paper is organized as follows. We describe Shamir’s secret sharing scheme and the two-variable one-way function in Section2, and we present our novel (
{
t
1
,
t
2
,
…
,
t
N
}
,
n
) threshold changeable secret image sharing scheme in Section 3. Our experiments, the performance of our scheme, and the security analysis are presented in Section 4. Section 5 presents our conclusions.


## 2. Preliminaries

This section describes the concept of Shamir’s(
t
,
n
) threshold secret sharing scheme [1] and the two-variable one-way function.


### 2.1. Shamir’s(
t
,
n
) Threshold Secret Sharing Scheme

LetS
=
G
F
(
q
) be the secret domain, where q is a big prime number. Secret s
∈
S is shared amongst n participants P
1
,
P
2
,
…
,
P
n and t is the threshold value. Each participant gets a piece of secret called share. Then, t or more participants can cooperate to reconstruct the secret by polynomial interpolation, and less than t participants cannot get any information about the secret. Shamir’s (
t
,
n
) secret sharing scheme [1] can work as follows.Sharing Procedure. The dealer chooses n distinct and nonzero elements x
1
,
x
2
,
…
,
x
n for the unique identifications of the participants, where x
i
∈
G
F
(
q
), 1
≤
i
≤
n. The identification can be known by everyone. Then, the dealer constructs a (t
-
1)-degree polynomial(1)
f
x
=
s
+
a
1
x
1
+
a
2
x
2
+
⋯
+
a
t
-
1
x
t
-
1
mod
⁡
q
,where a
1
,
a
2
,
…
,
a
t
-
1
∈
G
F
(
q
) are randomly chosen. For all 1
≤
i
≤
n, the dealer computes share y
i
=
f
(
x
i
) and then sends it to corresponding participant P
i by secure communication channels. The values of the shares are limited to [
0
,
q
-
1
].Recovery Procedure. Without loss of generality, assume that t participants P
1
,
P
2
,
…
,
P
t provide their shares. With t points x
1
,
y
1
,
x
2
,
y
2
,
…
,
(
x
t
,
y
t
), polynomial f
(
x
) can be reconstructed as follows: (2)
f
x
=
∑
i
=
1
t
y
i
∏
j
=
1
,
j
≠
i
t
x
-
x
j
x
i
-
x
j
mod
⁡
q
.Then, secrets can be recovered as s
=
f
(
0
).


### 2.2. Two-Variable One-Way Function

If each participant’s share data generated according to the secret image is sent directly, it can easily attract malicious intruders’ attention, because it is meaningless. To solve this problem, in our scheme, each participant’s share data is camouflaged in a cover image to form corresponding stego image. Since each stego image and cover image cannot be distinguished by the human eye, each participant’s share data can be concealed from intruders.In Zhang et al.’s(
{
t
1
,
t
2
,
…
,
t
N
}
,
n
) threshold changeable secret sharing scheme [21], they prepare advance shares for all potential changeable thresholds t
1
,
t
2
,
…
,
t
N and encrypt the advance shares by the symmetric encryption algorithm in the sharing procedure. But their encrypted shares are too large to be camouflaged in the cover image. To solve this problem, we used the two-variable one-way function to generate the identification values, which are fed into the polynomial to generate the shares. The details will be given in Section 3. For the reader’s convenience, we introduce the two-variable one-way function represented by Chien et al. [24] as follows.Functionh
(
r
,
s
) is a two-variable one-way function that can map variables r and s into a value with a fixed length. The features of h
(
r
,
s
) are as follows:(1)
Givenr and s, h
(
r
,
s
) is easy to calculate.
(2)
Givens and h
(
r
,
s
), it is not feasible to calculate r.
(3)
Givenr and h
(
r
,
s
), it is not feasible to calculate s.
(4)
It is not feasible to calculateh
(
r
,
s
) for any r without s.
(5)
It is not feasible to calculateh
(
r
,
s
) for any s without r.
(6)
Givens, it is not feasible for r
1 and r
2 to satisfy h
(
r
1
,
s
)
=
h
(
r
2
,
s
).
(7)
Givenr, it is not feasible for s
1 and s
2 to satisfy h
(
r
,
s
1
)
=
h
(
r
,
s
2
).
(8)
Given any pairs of(
r
i
,
f
(
r
i
,
s
)
), it is not feasible to calculate h
(
r
j
,
s
) when r
i
≠
r
j.


## 2.1. Shamir’s(
t
,
n
) Threshold Secret Sharing Scheme

LetS
=
G
F
(
q
) be the secret domain, where q is a big prime number. Secret s
∈
S is shared amongst n participants P
1
,
P
2
,
…
,
P
n and t is the threshold value. Each participant gets a piece of secret called share. Then, t or more participants can cooperate to reconstruct the secret by polynomial interpolation, and less than t participants cannot get any information about the secret. Shamir’s (
t
,
n
) secret sharing scheme [1] can work as follows.Sharing Procedure. The dealer chooses n distinct and nonzero elements x
1
,
x
2
,
…
,
x
n for the unique identifications of the participants, where x
i
∈
G
F
(
q
), 1
≤
i
≤
n. The identification can be known by everyone. Then, the dealer constructs a (t
-
1)-degree polynomial(1)
f
x
=
s
+
a
1
x
1
+
a
2
x
2
+
⋯
+
a
t
-
1
x
t
-
1
mod
⁡
q
,where a
1
,
a
2
,
…
,
a
t
-
1
∈
G
F
(
q
) are randomly chosen. For all 1
≤
i
≤
n, the dealer computes share y
i
=
f
(
x
i
) and then sends it to corresponding participant P
i by secure communication channels. The values of the shares are limited to [
0
,
q
-
1
].Recovery Procedure. Without loss of generality, assume that t participants P
1
,
P
2
,
…
,
P
t provide their shares. With t points x
1
,
y
1
,
x
2
,
y
2
,
…
,
(
x
t
,
y
t
), polynomial f
(
x
) can be reconstructed as follows: (2)
f
x
=
∑
i
=
1
t
y
i
∏
j
=
1
,
j
≠
i
t
x
-
x
j
x
i
-
x
j
mod
⁡
q
.Then, secrets can be recovered as s
=
f
(
0
).


## 2.2. Two-Variable One-Way Function

If each participant’s share data generated according to the secret image is sent directly, it can easily attract malicious intruders’ attention, because it is meaningless. To solve this problem, in our scheme, each participant’s share data is camouflaged in a cover image to form corresponding stego image. Since each stego image and cover image cannot be distinguished by the human eye, each participant’s share data can be concealed from intruders.In Zhang et al.’s(
{
t
1
,
t
2
,
…
,
t
N
}
,
n
) threshold changeable secret sharing scheme [21], they prepare advance shares for all potential changeable thresholds t
1
,
t
2
,
…
,
t
N and encrypt the advance shares by the symmetric encryption algorithm in the sharing procedure. But their encrypted shares are too large to be camouflaged in the cover image. To solve this problem, we used the two-variable one-way function to generate the identification values, which are fed into the polynomial to generate the shares. The details will be given in Section 3. For the reader’s convenience, we introduce the two-variable one-way function represented by Chien et al. [24] as follows.Functionh
(
r
,
s
) is a two-variable one-way function that can map variables r and s into a value with a fixed length. The features of h
(
r
,
s
) are as follows:(1)
Givenr and s, h
(
r
,
s
) is easy to calculate.
(2)
Givens and h
(
r
,
s
), it is not feasible to calculate r.
(3)
Givenr and h
(
r
,
s
), it is not feasible to calculate s.
(4)
It is not feasible to calculateh
(
r
,
s
) for any r without s.
(5)
It is not feasible to calculateh
(
r
,
s
) for any s without r.
(6)
Givens, it is not feasible for r
1 and r
2 to satisfy h
(
r
1
,
s
)
=
h
(
r
2
,
s
).
(7)
Givenr, it is not feasible for s
1 and s
2 to satisfy h
(
r
,
s
1
)
=
h
(
r
,
s
2
).
(8)
Given any pairs of(
r
i
,
f
(
r
i
,
s
)
), it is not feasible to calculate h
(
r
j
,
s
) when r
i
≠
r
j.


## 3. Proposed Scheme

Given a grey-scale secret imageS
=
{
p
1
,
p
2
,
…
,
p
h
s
×
w
s
} with h
s
×
w
s pixels and a grey-scale cover image C
=
{
c
1
,
c
2
,
…
,
c
h
c
×
w
c
} with h
c
×
w
c pixels, the dealer can derive shares from S and generate n stego images S
1
,
S
2
,
…
,
S
n for n participants P
1
,
P
2
,
…
,
P
n. Before recovering secret image S, if the security policy and adversary structure are changed, the threshold can be adjusted to a suitable threshold t
j
∈
{
t
1
,
t
2
,
…
,
t
N
}, where t
1
,
t
2
,
…
,
t
N are potential thresholds, and the scheme can remain secure after these changes are made. Then, t
j or more participants can recover secret image S without distortion.In our scheme, the pixels ofS and C are read from left to right and from top to bottom. Assume that the dealer knows N potential thresholds t
1
,
t
2
,
…
,
t
N to which the threshold may be changed in the future, and these thresholds satisfy the condition 0
<
t
i
+
1
-
t
i
<
t
1 (1
≤
i
≤
N
-
1). This condition can be achieved easily by adding new potential thresholds to shorten the difference between the two potential thresholds. For a univariate polynomial f
(
x
)
=
∑
i
≥
0
a
i
x
i, the degree operator d
e
g
(
·
) is used to compute the degree of the polynomial, and the coefficient operator [
x
d
] is defined, such that [
x
d
]
f
(
x
)
=
a
d. Our threshold changeable secret image sharing scheme can be divided into two procedures, that is, sharing and recovery. These procedures are described as follows.


### 3.1. Sharing Procedure

In the sharing procedure, the dealer derives shares from secret imageS and generates n stego images S
1
,
S
2
,
…
,
S
n for n participants P
1
,
P
2
,
…
,
P
n. Figure 1 displays the flowchart of this procedure. We describe how to generate the shares in Section 3.1.1 and how to camouflage these shares into the cover image to form the stego images in Section 3.1.2.Figure 1
Diagram of the sharing procedure.


#### 3.1.1. Share Derivation

The dealer selects a prime numberm, n distinct and nonzero random integers x
1
,
x
2
,
…
,
x
n as the real identifications of n participants, and N distinct and nonzero random integers K
1
,
K
2
,
…
,
K
N as the corresponding secret keys of potential thresholds t
1
,
t
2
,
…
,
t
N. To share secret image S, the dealer converts S intom-ary data (called converted data). The size of this converted data is h
s
×
w
s
×
log
m
⁡
255, where · is the ceiling function. For instance, we can assume that the chosen m is equal to 5, and then log
m
⁡
255
=
4. If two pixels in secret image S are 78 and 231, the converted digits become (
0,3
,
0,3
)
5 and (
1,4
,
1,1
)
5.For convenience, assume thatt
N converted digits, which are selected from the converted data, are s
1
,
s
2
,
…
,
s
t
N, and then N polynomials, which are used to hide these converted digits, can be constructed as follows:(3)
f
N
x
=
s
1
+
s
2
x
+
·
·
·
+
s
t
N
x
t
N
-
1
mod
⁡
m
f
N
-
1
x
=
f
N
x
-
x
t
N
-
t
1
g
N
-
1
x
mod
⁡
m
⋮
f
1
x
=
f
2
x
-
x
t
2
-
t
1
g
1
x
mod
⁡
m
,where polynomial g
j
(
x
) is generated by Algorithm 1, d
e
g
(
g
j
(
x
)
)
<
t
1 and d
e
g
(
f
j
(
x
)
)
=
t
j
-
1, for all 1
≤
j
≤
N
-
1. Algorithm 1 is described as follows.Algorithm 1:Polynomial generator (Zhang et al. [21]).
Input: t
j, t
j
+
1, f
j
+
1
(
x
)
Output: g
j
(
x
)
g
j
(
x
)
=
0;
d
=
deg
⁡
f
j
+
1
(
x
)
-
x
t
j
+
1
-
t
1
g
j
(
x
);
Whiled
≥
t
j do
c
=
x
d
f
j
+
1
(
x
);
g
j
(
x
)
=
g
j
(
x
)
+
c
x
d
-
(
t
j
+
1
-
t
1
);
d
=
deg
⁡
f
j
+
1
(
x
)
-
x
t
j
+
1
-
t
1
g
j
(
x
);
end
r
(
x
) is a random polynomial function the order of which is t
1
-
(
t
j
+
1
-
t
j
)
-
1;
g
j
(
x
)
=
g
j
(
x
)
+
r
(
x
);Then, each participant’s advance sharesy
1
i
,
y
2
i
,
…
,
y
N
i (1
≤
i
≤
n) are computed as follows: (4)
y
j
i
=
f
j
h
K
j
,
x
i
j
=
1,2
,
…
,
N
,where y
j
i is the j
t
h advance shares of participant P
i and h
(
K
j
,
x
i
) is the fake identification that is computed by feeding key K
j and real identification x
i into two-variable one-way function h
(
K
,
x
).


#### 3.1.2. Camouflage

In this phase, shares are camouflaged in cover imageC to form stego images S
1
,
S
2
,
…
,
S
n, and then they are distributed to corresponding participants.For convenience, assume thatN pixels, which are selected from cover image C, are c
p
1
,
c
p
2
,
…
,
c
p
N. With y
1
i
,
y
2
i
,
…
,
y
N
i and c
p
1
,
c
p
2
,
…
,
c
p
N, each participant’s camouflaged pixels s
p
1
i
,
s
p
2
i
,
…
,
s
p
N
i (1
≤
i
≤
n) are computed as(5)
s
p
j
i
=
c
p
j
m
×
m
+
y
j
i
j
=
1,2
,
…
,
N
,where s
p
j
i is j
t
h camouflaged pixel of participant P
i and · is the floor function.If all of the converted digits have been camouflaged in cover imageC, the dealer can obtain each participant’s stego image S
i (1
≤
i
≤
n), and then the dealer distributes real identification x
i and stego image S
i to corresponding participant P
i through secure communication channel.


### 3.2. Recovery Procedure

Before recovering secret imageS, if security policy and adversary structure are changed, the threshold can be adjusted to a suitable threshold t
j which is one of potential thresholds t
1
,
t
2
,
…
,
t
N, and the scheme can remain secure after these changes are made. Then, t
j or more participants can use their own stego images to recover secret image S without distortion. In this section, we describe how to change the threshold in Section 3.2.1 and how to recover secret image S without distortion in Section 3.2.2.


#### 3.2.1. Threshold Changing

Assuming that the new threshold must be changed tot
j (1
≤
j
≤
N), the dealer broadcasts keys K
j
,
K
j
+
1
,
…
,
K
N. With keys K
j
,
K
j
+
1
,
…
,
K
N and real identification x
i, each participant P
i (1
≤
i
≤
n) computes her/his fake identifications h
K
j
,
x
i
,
h
K
j
+
1
,
x
i
,
…
,
h
(
K
N
,
x
i
), which are used to reconstruct polynomials f
j
x
,
f
j
+
1
x
,
…
,
f
N
(
x
) in the next phase.


#### 3.2.2. Secret Image Recovery

In this section, we describe how to recover secret imageS with threshold t
j. The procedure for doing so is shown in Figure 2.Figure 2
Recovery procedure.For convenience, assume thatt
j participants P
1
,
P
2
,
…
,
P
t
j provide their stego images S
1
,
S
2
,
…
,
S
t
j. Let N pixels s
p
1
i
,
s
p
2
i
,
…
,
s
p
N
i be the corresponding pixel value of stego image S
i. To extract the converted data, these participants must reconstruct polynomial f
N
(
x
) from their advance shares. Thus, by utilizing the modulo operation, advance shares y
j
i
,
y
j
+
1
i
,
…
,
y
N
i (1
≤
i
≤
t
j) can be computed as(6)
y
k
i
=
s
p
k
i
mod
⁡
m
k
=
j
,
j
+
1
,
…
,
N
,where y
k
i is the k
t
h advance shares of participant P
i.Ift
j
=
t
N, with shares y
N
1
,
y
N
2
,
…
,
y
N
t
N and fake identification values h
(
K
N
,
x
1
)
,
h
(
K
N
,
x
2
)
,
…
,
h
(
K
N
,
x
t
N
), polynomial f
N
(
x
) can be reconstructed as follows:(7)
f
N
x
=
∑
i
=
1
t
N
y
N
i
∏
k
=
1
,
k
≠
i
t
N
x
-
h
K
N
,
x
k
h
K
N
,
x
i
-
h
K
N
,
x
k
mod
⁡
m
.Then, converted digits s
1
,
s
2
,
…
,
s
t
N can be recovered from t
N coefficients of polynomial f
N
(
x
).Ift
1
≤
t
j
<
t
N, since deg
⁡
(
f
N
(
x
)
)
=
t
N
-
1, t
j participants cannot reconstruct polynomial f
N
(
x
) directly. But, they can reconstruct polynomial f
j
(
x
) and then reconstruct polynomials f
j
+
1
(
x
)
,
f
j
+
2
(
x
)
,
…
,
f
N
(
x
) in turn by computing polynomials g
j
(
x
)
,
g
j
+
1
(
x
)
,
…
,
g
N
-
1
(
x
) where f
k
+
1
(
x
)
=
f
k
(
x
)
+
x
t
k
+
1
-
t
1
g
k
(
x
) and deg
⁡
(
g
k
(
x
)
)
<
t
1 (j
≤
k
≤
N
-
1).Witht
1 points (
h
(
K
j
+
1
,
x
i
)
,
(
y
j
+
1
i
-
f
j
(
h
(
K
j
+
1
,
x
i
)
)
/
(
h
(
K
j
+
1
,
x
i
)
)
t
j
+
1
-
t
1
) (i
=
1,2
,
…
,
t
1), polynomial g
j
(
x
) can be constructed as follows:(8)
g
j
x
=
∑
i
=
1
t
1
y
j
+
1
i
-
f
j
h
K
j
+
1
,
x
i
h
K
j
+
1
,
x
i
t
j
+
1
-
t
1
∏
k
=
1
,
k
≠
i
t
1
x
-
h
K
j
+
1
,
x
k
h
K
j
+
1
,
x
i
-
h
K
j
+
1
,
x
k
mod
⁡
m
.Then, polynomialf
j
+
1
(
x
) can be constructed as f
j
+
1
(
x
)
=
f
j
(
x
)
+
x
t
j
+
1
-
t
1
g
j
(
x
). By repeating above procedures, polynomials f
j
+
2
x
,
f
j
+
3
x
,
…
,
f
N
(
x
) can be recovered in turn, and then converted digits s
1
,
s
2
,
…
,
s
t
N can be obtained from t
N coefficients of polynomial f
N
(
x
).By repeating these processes, all converted digits can be extracted, and then secret imageS can be recovered by transforming these converted digits to decimal representation.


## 3.1. Sharing Procedure

In the sharing procedure, the dealer derives shares from secret imageS and generates n stego images S
1
,
S
2
,
…
,
S
n for n participants P
1
,
P
2
,
…
,
P
n. Figure 1 displays the flowchart of this procedure. We describe how to generate the shares in Section 3.1.1 and how to camouflage these shares into the cover image to form the stego images in Section 3.1.2.Figure 1
Diagram of the sharing procedure.


### 3.1.1. Share Derivation

The dealer selects a prime numberm, n distinct and nonzero random integers x
1
,
x
2
,
…
,
x
n as the real identifications of n participants, and N distinct and nonzero random integers K
1
,
K
2
,
…
,
K
N as the corresponding secret keys of potential thresholds t
1
,
t
2
,
…
,
t
N. To share secret image S, the dealer converts S intom-ary data (called converted data). The size of this converted data is h
s
×
w
s
×
log
m
⁡
255, where · is the ceiling function. For instance, we can assume that the chosen m is equal to 5, and then log
m
⁡
255
=
4. If two pixels in secret image S are 78 and 231, the converted digits become (
0,3
,
0,3
)
5 and (
1,4
,
1,1
)
5.For convenience, assume thatt
N converted digits, which are selected from the converted data, are s
1
,
s
2
,
…
,
s
t
N, and then N polynomials, which are used to hide these converted digits, can be constructed as follows:(3)
f
N
x
=
s
1
+
s
2
x
+
·
·
·
+
s
t
N
x
t
N
-
1
mod
⁡
m
f
N
-
1
x
=
f
N
x
-
x
t
N
-
t
1
g
N
-
1
x
mod
⁡
m
⋮
f
1
x
=
f
2
x
-
x
t
2
-
t
1
g
1
x
mod
⁡
m
,where polynomial g
j
(
x
) is generated by Algorithm 1, d
e
g
(
g
j
(
x
)
)
<
t
1 and d
e
g
(
f
j
(
x
)
)
=
t
j
-
1, for all 1
≤
j
≤
N
-
1. Algorithm 1 is described as follows.Algorithm 1:Polynomial generator (Zhang et al. [21]).
Input: t
j, t
j
+
1, f
j
+
1
(
x
)
Output: g
j
(
x
)
g
j
(
x
)
=
0;
d
=
deg
⁡
f
j
+
1
(
x
)
-
x
t
j
+
1
-
t
1
g
j
(
x
);
Whiled
≥
t
j do
c
=
x
d
f
j
+
1
(
x
);
g
j
(
x
)
=
g
j
(
x
)
+
c
x
d
-
(
t
j
+
1
-
t
1
);
d
=
deg
⁡
f
j
+
1
(
x
)
-
x
t
j
+
1
-
t
1
g
j
(
x
);
end
r
(
x
) is a random polynomial function the order of which is t
1
-
(
t
j
+
1
-
t
j
)
-
1;
g
j
(
x
)
=
g
j
(
x
)
+
r
(
x
);Then, each participant’s advance sharesy
1
i
,
y
2
i
,
…
,
y
N
i (1
≤
i
≤
n) are computed as follows: (4)
y
j
i
=
f
j
h
K
j
,
x
i
j
=
1,2
,
…
,
N
,where y
j
i is the j
t
h advance shares of participant P
i and h
(
K
j
,
x
i
) is the fake identification that is computed by feeding key K
j and real identification x
i into two-variable one-way function h
(
K
,
x
).


### 3.1.2. Camouflage

In this phase, shares are camouflaged in cover imageC to form stego images S
1
,
S
2
,
…
,
S
n, and then they are distributed to corresponding participants.For convenience, assume thatN pixels, which are selected from cover image C, are c
p
1
,
c
p
2
,
…
,
c
p
N. With y
1
i
,
y
2
i
,
…
,
y
N
i and c
p
1
,
c
p
2
,
…
,
c
p
N, each participant’s camouflaged pixels s
p
1
i
,
s
p
2
i
,
…
,
s
p
N
i (1
≤
i
≤
n) are computed as(5)
s
p
j
i
=
c
p
j
m
×
m
+
y
j
i
j
=
1,2
,
…
,
N
,where s
p
j
i is j
t
h camouflaged pixel of participant P
i and · is the floor function.If all of the converted digits have been camouflaged in cover imageC, the dealer can obtain each participant’s stego image S
i (1
≤
i
≤
n), and then the dealer distributes real identification x
i and stego image S
i to corresponding participant P
i through secure communication channel.


## 3.1.1. Share Derivation

The dealer selects a prime numberm, n distinct and nonzero random integers x
1
,
x
2
,
…
,
x
n as the real identifications of n participants, and N distinct and nonzero random integers K
1
,
K
2
,
…
,
K
N as the corresponding secret keys of potential thresholds t
1
,
t
2
,
…
,
t
N. To share secret image S, the dealer converts S intom-ary data (called converted data). The size of this converted data is h
s
×
w
s
×
log
m
⁡
255, where · is the ceiling function. For instance, we can assume that the chosen m is equal to 5, and then log
m
⁡
255
=
4. If two pixels in secret image S are 78 and 231, the converted digits become (
0,3
,
0,3
)
5 and (
1,4
,
1,1
)
5.For convenience, assume thatt
N converted digits, which are selected from the converted data, are s
1
,
s
2
,
…
,
s
t
N, and then N polynomials, which are used to hide these converted digits, can be constructed as follows:(3)
f
N
x
=
s
1
+
s
2
x
+
·
·
·
+
s
t
N
x
t
N
-
1
mod
⁡
m
f
N
-
1
x
=
f
N
x
-
x
t
N
-
t
1
g
N
-
1
x
mod
⁡
m
⋮
f
1
x
=
f
2
x
-
x
t
2
-
t
1
g
1
x
mod
⁡
m
,where polynomial g
j
(
x
) is generated by Algorithm 1, d
e
g
(
g
j
(
x
)
)
<
t
1 and d
e
g
(
f
j
(
x
)
)
=
t
j
-
1, for all 1
≤
j
≤
N
-
1. Algorithm 1 is described as follows.Algorithm 1:Polynomial generator (Zhang et al. [21]).
Input: t
j, t
j
+
1, f
j
+
1
(
x
)
Output: g
j
(
x
)
g
j
(
x
)
=
0;
d
=
deg
⁡
f
j
+
1
(
x
)
-
x
t
j
+
1
-
t
1
g
j
(
x
);
Whiled
≥
t
j do
c
=
x
d
f
j
+
1
(
x
);
g
j
(
x
)
=
g
j
(
x
)
+
c
x
d
-
(
t
j
+
1
-
t
1
);
d
=
deg
⁡
f
j
+
1
(
x
)
-
x
t
j
+
1
-
t
1
g
j
(
x
);
end
r
(
x
) is a random polynomial function the order of which is t
1
-
(
t
j
+
1
-
t
j
)
-
1;
g
j
(
x
)
=
g
j
(
x
)
+
r
(
x
);Then, each participant’s advance sharesy
1
i
,
y
2
i
,
…
,
y
N
i (1
≤
i
≤
n) are computed as follows: (4)
y
j
i
=
f
j
h
K
j
,
x
i
j
=
1,2
,
…
,
N
,where y
j
i is the j
t
h advance shares of participant P
i and h
(
K
j
,
x
i
) is the fake identification that is computed by feeding key K
j and real identification x
i into two-variable one-way function h
(
K
,
x
).


## 3.1.2. Camouflage

In this phase, shares are camouflaged in cover imageC to form stego images S
1
,
S
2
,
…
,
S
n, and then they are distributed to corresponding participants.For convenience, assume thatN pixels, which are selected from cover image C, are c
p
1
,
c
p
2
,
…
,
c
p
N. With y
1
i
,
y
2
i
,
…
,
y
N
i and c
p
1
,
c
p
2
,
…
,
c
p
N, each participant’s camouflaged pixels s
p
1
i
,
s
p
2
i
,
…
,
s
p
N
i (1
≤
i
≤
n) are computed as(5)
s
p
j
i
=
c
p
j
m
×
m
+
y
j
i
j
=
1,2
,
…
,
N
,where s
p
j
i is j
t
h camouflaged pixel of participant P
i and · is the floor function.If all of the converted digits have been camouflaged in cover imageC, the dealer can obtain each participant’s stego image S
i (1
≤
i
≤
n), and then the dealer distributes real identification x
i and stego image S
i to corresponding participant P
i through secure communication channel.


## 3.2. Recovery Procedure

Before recovering secret imageS, if security policy and adversary structure are changed, the threshold can be adjusted to a suitable threshold t
j which is one of potential thresholds t
1
,
t
2
,
…
,
t
N, and the scheme can remain secure after these changes are made. Then, t
j or more participants can use their own stego images to recover secret image S without distortion. In this section, we describe how to change the threshold in Section 3.2.1 and how to recover secret image S without distortion in Section 3.2.2.


### 3.2.1. Threshold Changing

Assuming that the new threshold must be changed tot
j (1
≤
j
≤
N), the dealer broadcasts keys K
j
,
K
j
+
1
,
…
,
K
N. With keys K
j
,
K
j
+
1
,
…
,
K
N and real identification x
i, each participant P
i (1
≤
i
≤
n) computes her/his fake identifications h
K
j
,
x
i
,
h
K
j
+
1
,
x
i
,
…
,
h
(
K
N
,
x
i
), which are used to reconstruct polynomials f
j
x
,
f
j
+
1
x
,
…
,
f
N
(
x
) in the next phase.


### 3.2.2. Secret Image Recovery

In this section, we describe how to recover secret imageS with threshold t
j. The procedure for doing so is shown in Figure 2.Figure 2
Recovery procedure.For convenience, assume thatt
j participants P
1
,
P
2
,
…
,
P
t
j provide their stego images S
1
,
S
2
,
…
,
S
t
j. Let N pixels s
p
1
i
,
s
p
2
i
,
…
,
s
p
N
i be the corresponding pixel value of stego image S
i. To extract the converted data, these participants must reconstruct polynomial f
N
(
x
) from their advance shares. Thus, by utilizing the modulo operation, advance shares y
j
i
,
y
j
+
1
i
,
…
,
y
N
i (1
≤
i
≤
t
j) can be computed as(6)
y
k
i
=
s
p
k
i
mod
⁡
m
k
=
j
,
j
+
1
,
…
,
N
,where y
k
i is the k
t
h advance shares of participant P
i.Ift
j
=
t
N, with shares y
N
1
,
y
N
2
,
…
,
y
N
t
N and fake identification values h
(
K
N
,
x
1
)
,
h
(
K
N
,
x
2
)
,
…
,
h
(
K
N
,
x
t
N
), polynomial f
N
(
x
) can be reconstructed as follows:(7)
f
N
x
=
∑
i
=
1
t
N
y
N
i
∏
k
=
1
,
k
≠
i
t
N
x
-
h
K
N
,
x
k
h
K
N
,
x
i
-
h
K
N
,
x
k
mod
⁡
m
.Then, converted digits s
1
,
s
2
,
…
,
s
t
N can be recovered from t
N coefficients of polynomial f
N
(
x
).Ift
1
≤
t
j
<
t
N, since deg
⁡
(
f
N
(
x
)
)
=
t
N
-
1, t
j participants cannot reconstruct polynomial f
N
(
x
) directly. But, they can reconstruct polynomial f
j
(
x
) and then reconstruct polynomials f
j
+
1
(
x
)
,
f
j
+
2
(
x
)
,
…
,
f
N
(
x
) in turn by computing polynomials g
j
(
x
)
,
g
j
+
1
(
x
)
,
…
,
g
N
-
1
(
x
) where f
k
+
1
(
x
)
=
f
k
(
x
)
+
x
t
k
+
1
-
t
1
g
k
(
x
) and deg
⁡
(
g
k
(
x
)
)
<
t
1 (j
≤
k
≤
N
-
1).Witht
1 points (
h
(
K
j
+
1
,
x
i
)
,
(
y
j
+
1
i
-
f
j
(
h
(
K
j
+
1
,
x
i
)
)
/
(
h
(
K
j
+
1
,
x
i
)
)
t
j
+
1
-
t
1
) (i
=
1,2
,
…
,
t
1), polynomial g
j
(
x
) can be constructed as follows:(8)
g
j
x
=
∑
i
=
1
t
1
y
j
+
1
i
-
f
j
h
K
j
+
1
,
x
i
h
K
j
+
1
,
x
i
t
j
+
1
-
t
1
∏
k
=
1
,
k
≠
i
t
1
x
-
h
K
j
+
1
,
x
k
h
K
j
+
1
,
x
i
-
h
K
j
+
1
,
x
k
mod
⁡
m
.Then, polynomialf
j
+
1
(
x
) can be constructed as f
j
+
1
(
x
)
=
f
j
(
x
)
+
x
t
j
+
1
-
t
1
g
j
(
x
). By repeating above procedures, polynomials f
j
+
2
x
,
f
j
+
3
x
,
…
,
f
N
(
x
) can be recovered in turn, and then converted digits s
1
,
s
2
,
…
,
s
t
N can be obtained from t
N coefficients of polynomial f
N
(
x
).By repeating these processes, all converted digits can be extracted, and then secret imageS can be recovered by transforming these converted digits to decimal representation.


## 3.2.1. Threshold Changing

Assuming that the new threshold must be changed tot
j (1
≤
j
≤
N), the dealer broadcasts keys K
j
,
K
j
+
1
,
…
,
K
N. With keys K
j
,
K
j
+
1
,
…
,
K
N and real identification x
i, each participant P
i (1
≤
i
≤
n) computes her/his fake identifications h
K
j
,
x
i
,
h
K
j
+
1
,
x
i
,
…
,
h
(
K
N
,
x
i
), which are used to reconstruct polynomials f
j
x
,
f
j
+
1
x
,
…
,
f
N
(
x
) in the next phase.


## 3.2.2. Secret Image Recovery

In this section, we describe how to recover secret imageS with threshold t
j. The procedure for doing so is shown in Figure 2.Figure 2
Recovery procedure.For convenience, assume thatt
j participants P
1
,
P
2
,
…
,
P
t
j provide their stego images S
1
,
S
2
,
…
,
S
t
j. Let N pixels s
p
1
i
,
s
p
2
i
,
…
,
s
p
N
i be the corresponding pixel value of stego image S
i. To extract the converted data, these participants must reconstruct polynomial f
N
(
x
) from their advance shares. Thus, by utilizing the modulo operation, advance shares y
j
i
,
y
j
+
1
i
,
…
,
y
N
i (1
≤
i
≤
t
j) can be computed as(6)
y
k
i
=
s
p
k
i
mod
⁡
m
k
=
j
,
j
+
1
,
…
,
N
,where y
k
i is the k
t
h advance shares of participant P
i.Ift
j
=
t
N, with shares y
N
1
,
y
N
2
,
…
,
y
N
t
N and fake identification values h
(
K
N
,
x
1
)
,
h
(
K
N
,
x
2
)
,
…
,
h
(
K
N
,
x
t
N
), polynomial f
N
(
x
) can be reconstructed as follows:(7)
f
N
x
=
∑
i
=
1
t
N
y
N
i
∏
k
=
1
,
k
≠
i
t
N
x
-
h
K
N
,
x
k
h
K
N
,
x
i
-
h
K
N
,
x
k
mod
⁡
m
.Then, converted digits s
1
,
s
2
,
…
,
s
t
N can be recovered from t
N coefficients of polynomial f
N
(
x
).Ift
1
≤
t
j
<
t
N, since deg
⁡
(
f
N
(
x
)
)
=
t
N
-
1, t
j participants cannot reconstruct polynomial f
N
(
x
) directly. But, they can reconstruct polynomial f
j
(
x
) and then reconstruct polynomials f
j
+
1
(
x
)
,
f
j
+
2
(
x
)
,
…
,
f
N
(
x
) in turn by computing polynomials g
j
(
x
)
,
g
j
+
1
(
x
)
,
…
,
g
N
-
1
(
x
) where f
k
+
1
(
x
)
=
f
k
(
x
)
+
x
t
k
+
1
-
t
1
g
k
(
x
) and deg
⁡
(
g
k
(
x
)
)
<
t
1 (j
≤
k
≤
N
-
1).Witht
1 points (
h
(
K
j
+
1
,
x
i
)
,
(
y
j
+
1
i
-
f
j
(
h
(
K
j
+
1
,
x
i
)
)
/
(
h
(
K
j
+
1
,
x
i
)
)
t
j
+
1
-
t
1
) (i
=
1,2
,
…
,
t
1), polynomial g
j
(
x
) can be constructed as follows:(8)
g
j
x
=
∑
i
=
1
t
1
y
j
+
1
i
-
f
j
h
K
j
+
1
,
x
i
h
K
j
+
1
,
x
i
t
j
+
1
-
t
1
∏
k
=
1
,
k
≠
i
t
1
x
-
h
K
j
+
1
,
x
k
h
K
j
+
1
,
x
i
-
h
K
j
+
1
,
x
k
mod
⁡
m
.Then, polynomialf
j
+
1
(
x
) can be constructed as f
j
+
1
(
x
)
=
f
j
(
x
)
+
x
t
j
+
1
-
t
1
g
j
(
x
). By repeating above procedures, polynomials f
j
+
2
x
,
f
j
+
3
x
,
…
,
f
N
(
x
) can be recovered in turn, and then converted digits s
1
,
s
2
,
…
,
s
t
N can be obtained from t
N coefficients of polynomial f
N
(
x
).By repeating these processes, all converted digits can be extracted, and then secret imageS can be recovered by transforming these converted digits to decimal representation.


## 4. Experiment and Analysis

In this section, we describe the tests we conducted to determine the feasibility and performance of our scheme using simulations and experiments, and then we discuss the security of our scheme.To estimate the quality of the stego images, we used peak signal-to-noise ratio (PSNR):(9)
PSNR
=
10
log
10
⁡
25
5
2
MSE
dB
.The mean square error (MSE) of an image with H
×
W pixels is defined as(10)
MSE
=
1
H
×
W
∑
u
=
1
H
∑
v
=
1
W
p
u
v
-
p
u
v
′
2
,where p
u
v is the original pixel value of the cover image and p
u
v
′ is the camouflaged pixel value of the stego image. Therefore, the higher the PSNR value, the smaller the difference between the cover image and the stego image. If the PSNR value is less than 35 dB, some of the important characteristics of the signal may be lost. When the PSNR value is less than 30 dB, the quality is unacceptable. But it is difficult for people to distinguish the original cover image from the stego image when the PSNR value is greater than 35 dB [26].


### 4.1. Simulation Results

The simulation settings of our experimental parameters were as follows:N
=
3, n
=
6, m
=
5, t
1
=
2, t
2
=
3, and t
3
=
4 (i.e., this scheme is a (
{
2,3
,
4
}
,
6
) threshold changeable secret sharing scheme). Let the real identification of six participants be X
=
1,2
,
3,4
,
5,6. We used image Baboon with 256
×
256 pixels as the secret image, as shown in Figure 3. We embedded shares into the original cover pixels, except for those pixels within 255
/
m
×
m
,
255 as Lin and Chan’s scheme [7] does.Figure 3
Secret image Baboon.To compare the quality of the stego images for different cover images, we selected twelve gray-scale test cover images with512
×
512 pixels to conduct the experiment. The twelve cover images are shown in Figure 4.Figure 4
Twelve cover images.
(a)
Airplane
(b)
House
(c)
Bird
(d)
Cameraman
(e)
Couple
(f)
Crowd
(g)
Fruits
(h)
Boat
(i)
Lake
(j)
Lena
(k)
Peppers
(l)
TiffanyTable1 displays the corresponding PSNR values of the stego images for the test cover images by our (
{
2,3
,
4
}
,
6
) threshold changeable secret image sharing scheme.Table 1
PSNR values (dB) of the stego images tested in 12 cover images.
Cover images
PNSR of stego 1
PNSR of stego 2
PNSR of stego 3
PNSR of stego 4
PNSR of stego 5
PNSR of stego 6
Average
Airplane
41.24
39.99
40.44
39.62
38.51
40.46
40.04
Boat
41.24
39.98
40.42
39.59
38.48
40.46
40.02
Bird
41.24
39.98
40.43
39.60
38.47
40.46
40.03
Cameraman
41.19
39.93
40.37
39.55
38.41
40.41
39.98
Couple
41.26
40.01
40.46
39.64
38.52
40.49
39.97
Crowd
41.09
39.85
40.26
39.46
38.26
40.30
40.06
Fruits
41.26
40.01
40.45
39.63
38.48
40.48
40.05
House
41.29
40.17
40.68
39.87
39.53
40.73
40.38
Lake
41.25
39.98
40.43
39.62
38.49
40.48
40.04
Lena
41.23
39.97
40.42
39.60
38.47
40.45
40.02
Peppers
41.23
39.97
40.42
39.60
38.48
40.45
40.02
Tiffany
41.26
40.03
40.47
39.64
38.54
40.49
40.04Table1 indicates that the cover image has little effect on the quality of the stego images. All of the PSNR values of our experiments are about 40 dB, which is greater than 35 dB, indicating that the quality of the stego images is satisfactory.In the recovery procedure of our(
{
2,3
,
4
}
,
6
) scheme, we set t
2
=
3 as the threshold value, and we broadcast the corresponding secret keys K
2
,
K
3. For convenience, we used stego images (a), (b), and (c) to reconstruct the secret image. Figure 5 shows cover image Lena, six stego images, and reconstructed secret image Baboon. The average PSNR value of the six stego images (i.e., images (a), (b), (c), (d), (e), and (f)) is 40.02 dB. We observe that each stego image shown in Figure 5 has a natural appearance and cannot leak any information about the secret image. The secret image recovered by stego images (a), (b), and (c) is displayed as image (g), which is the same as the original secret image.Figure 5
Six stego images, recovered secret image Baboon, and cover image Lena.
(a)
Stego image 1, PSNR=
41.23 dB
(b)
Stego image 2, PSNR=
39.97 dB
(c)
Stego image 3, PSNR=
40.42 dB
(d)
Stego image 4, PSNR=
39.60 dB
(e)
Stego image 5, PSNR=
38.47 dB
(f)
Stego image 6, PSNR=
40.45 dB
(g)
Recovered secret image Baboon
(h)
Cover image Lena


### 4.2. Performance Analysis

Factorsm and N potential thresholds t
1
,
t
2
,
…
,
t
N are important in our scheme’s ability to maximize the secret capacity and preserve the fidelity of the stego images. The influence of these two factors is discussed in this section.Table2 displays the relationship of capacity and distortion for different m values. Image Baboon is used as the secret image in all of those experiments, and Lena is used as the cover image. The parameters are as follows: N
=
3, n
=
6, t
1
=
2, t
2
=
3, and t
3
=
4. Table 2 indicates that (1) the number of influenced bits is increased as the value of factor m increases; (2) the capacity of the embedded converted data is increased as the value of factor m increases; and (3) the value of PSNR is decreased as the value of factor m increases. Since the difference between the original pixel in the cover image and the camouflaged pixel in the stego image is limited to [
0
,
m
-
1
], it becomes smaller as the value of factor m decreases; that is, the quality of the stego images increases as factor m decreases. But a smaller m value can increase the number of converted digits; that is, the capacity of the embedded converted data is decreased. Different from Lin and Chan’s scheme [7] which constructs one polynomial, we construct N polynomials to embed t
N converted digits into N pixels of the cover image in one iteration of polynomial calculation. Assuming that this cover image has H
c
×
W
c pixels, it can embed H
c
×
W
c
×
t
N
/
N converted digits (i.e., H
c
×
W
c
×
t
N
/
N
×
l
o
g
m
255 pixels). Table 2 indicates that the values of the PSNR are greater than 35 dB when the values of m are set as 5 and 7. Since the capacity when m is 7 is greater than that when m is 5, setting m as 7 is more suitable in this situation.Table 2
Relationship of the capacity distortion for differentm values.
m
Distortion
Capacity (pixels)
PSNR (dB)
[
0
,
m
-
1
]
Influenced bits
5
0,4
3
H
×
W
×
t
N
/
N
×
4
40.02
7
0,6
3
H
×
W
×
t
N
/
N
×
3
38.41
11
0,10
4
H
×
W
×
t
N
/
N
×
3
32.61
13
0,12
4
H
×
W
×
t
N
/
N
×
3
30.60
17
0,16
5
H
×
W
×
t
N
/
N
×
2
28.90
19
0,18
5
H
×
W
×
t
N
/
N
×
2
28.22
23
0,22
5
H
×
W
×
t
N
/
N
×
2
26.76The selection ofN potential thresholds t
1
,
t
2
,
…
,
t
N is another critical factor that influences the quality of the stego images. Table 3 shows the performance comparisons of different potential thresholds. In these experiments, we set test potential thresholds as 2,3, 3,4, 4,5, 3,5, and [
4,6
], and we set factor m
=
5. As in the above experiments, image Baboon is used as the secret image, and image Lena is the cover image.Table 3
Performance comparisons of different potential thresholds.
Number
Potential thresholds
Capacity
PSNR (dB)
1
[
2,3
]
H
×
W
×
3
/
8
43.79
2
[
3,4
]
H
×
W
×
4
/
8
45.06
3
[
4,5
]
H
×
W
×
5
/
8
46.08
4
[
3,5
]
H
×
W
×
5
/
8
46.03
5
[
4,6
]
H
×
W
×
6
/
8
46.86In our(
{
t
1
,
t
2
,
…
,
t
N
}
,
n
) threshold changeable secret image sharing scheme, since we camouflage t
N converted digits in (
t
N
-
1
)-degree polynomial f
N
(
x
), the order of polynomial f
N
(
x
) increases as t
N increases, which means that, for the same secret image and factor m, the number of camouflaged pixels decreases as t
N increases (i.e., the value of PSNR increases as t
N increases, and the capacity of embedding converted data in the cover image increases as t
N increases, which were indicated in Table 3). At the same time, we focus on the performance when the potential thresholds were set as [
3,5
] and [
4,5
], and we observed that different potential thresholds had little effect on the quality of the stego images when t
N and N were fixed. In our scheme, we need to construct H
s
×
W
s
×
log
m
⁡
255
/
t
N polynomials and camouflage H
s
×
W
s
×
N
×
log
m
⁡
255
/
t
N pixels of the cover image, where H
s and W
s are the height and width of gray-scale secret image S, respectively. Thus, the difference of potential thresholds cannot influence the quality of the stego images when t
N and N were fixed.Table4 compares our scheme with Chang et al.’s scheme (2008) [25], Lin et al.’s scheme (2009) [6], Lin and Chan’s scheme (2010) [7], and Ulutas et al.’s scheme (2013) [10]. We still use image Baboon as the secret image and image Lena as the cover image, and set m
=
5.Table 4
Comparisons of the related secret image sharing mechanisms.
Functionality
Chang et al. (2008) [25]
Lin et al. (2009) [6]
Lin and Chan (2010) [7]
Ulutas et al. (2013) [10]
Ours
Threshold
(
t
,
n
)
(
t
,
n
)
(
t
,
n
)
(
t
,
n
)
(
t
1
,
t
2
,
…
,
t
N
,
n
)
Threshold changeability
No
No
No
No
Yes
Quality of stego images
40.33 dB
43.02 dB
42.36 dB
46.79 dB
40.02 dB
Lossless secret image
Yes
Yes
Yes
Yes
Yes
Lossless cover image
No
Yes
Yes
Yes
No
Maximum capacity (pixels)
H
×
W
4
(
t
-
3
)
×
H
×
W
3
(
t
-
1
)
×
H
×
W
log
m
⁡
255
(
t
-
2
)
×
H
×
W
4
t
N
×
H
×
W
N
×
log
m
⁡
255Table4 indicates that our scheme has the unique threshold changeable characteristic and can recover the secret image without distortion. Since we camouflaged t
N converted digits in N pixels of the cover image in each iteration, which requires much more modification of the cover image, our scheme has lower quality of stego images and capacity of embedded converted digits. However, the average PSNR value of our scheme is 40 dB, which indicates that the quality of our stego images is acceptable. In addition, in practice, N is usually a small integer (such as N
=
3) corresponding to the “low, middle, and high” level of security in computers while t
N could be linearly related to n, so the capacity of embedded converted digits usually is acceptable.In some situation, we need to share important secret image using sensitive cover images (such as medical, military, or artistic images) and these cover images need to be recovered without distortion. To satisfy this requirement, our scheme can embed the recovery information of the cover image pixels into the polynomials as Lin and Chan’s scheme [7] does. But in this situation, we can only embed t
N
-
N converted digits into N pixels of the cover image in one iteration, which weakens the quality of the stego images and reduces the capacity to H
c
×
W
c
×
(
t
N
-
N
)
/
(
N
×
log
m
⁡
255
), where H
c and W
c are the height and width of gray-scale cover image C, respectively.


### 4.3. Security Analysis

In this section, we analyze the security of our scheme.First, we notice that our scheme can only change the threshold once. After the dealer broadcasts keysK
j
,
K
j
+
1
,
…
,
K
N to validate threshold t
j (1
≤
j
≤
N), then it takes at least t
j cooperating participants to recover the secret image without distortion. If the new threshold must be changed to t
k (1
≤
k
<
j), the dealer broadcasts keys K
k
,
K
k
+
1
,
…
,
K
j
-
1 to achieve this. On the contrary, if j
<
k
≤
N, the shares must be updated. In schemes that have strict security requirements, it is inevitable that shares are updated. For instance, the threshold in schemes [27, 28] can be changed many times, but, when one participant leaves the group, the shares should be updated simultaneously.Theorem 1.
Before broadcasting the keys, no participant can recover secret imageS.Proof.
In the worst situation, there aren participants in set A
′
=
{
P
1
,
P
2
,
…
,
P
n
} who want to recover the secret image. Assume that they want to recover the first t
N converted digits hidden in polynomial f
N
(
x
). Then, the participants in A
′ can obtain(11)
⋃
1
≤
i
≤
n
⋃
1
≤
k
≤
N
y
k
i
∪
⋃
1
≤
i
≤
n
x
i
.
Our scheme is based on polynomial interpolation; that is, givent points (
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
t
,
y
t
) with distinct x
i, there is one and only one (
t
-
1
)-degree polynomial f
(
x
) such that f
(
x
i
)
=
y
i for all 1
≤
i
≤
t. However, the polynomial cannot be reconstructed with less than t points. According to the features of the two-variable one-way function h
(
K
,
x
), without keys K
1
,
K
2
,
…
,
K
N, each participant P
i (1
≤
i
≤
n) cannot compute her/his fake identifications h
K
1
,
x
i
,
h
K
2
,
x
i
,
…
,
h
(
K
N
,
x
i
), which are fed into polynomials f
1
x
,
f
2
x
,
…
,
f
N
(
x
) to generate the shares y
1
i
,
y
2
i
,
…
,
y
N
i in the sharing procedure. Thus, utilizing only ⋃
1
≤
i
≤
n
⋃
1
≤
k
≤
N
y
k
i, no polynomial in f
1
x
,
f
2
x
,
…
,
f
N
(
x
) can be reconstructed by polynomial interpolation, and they cannot obtain the converted digits that are hidden in the coefficients of polynomial f
N
(
x
). Likewise, the participants in A
′ cannot obtain other converted digits, so the secret image cannot be recovered by any participant.Theorem 2.
After obtaining broadcast informationK
j
,
K
j
+
1
,
…
,
K
N, less than t
j participants cannot recover secret image S.Proof.
Without loss of generality, assume that there aret
j
-
1 participants in set A
′
=
{
P
1
,
P
2
,
…
,
P
t
j
-
1
} who want to recover the secret image. Assume that they want to recover the first t
N converted digits that are hidden in polynomial f
N
(
x
). Then, the participants in A
′ can obtain(12)
⋃
1
≤
i
≤
t
j
-
1
⋃
1
≤
k
≤
j
-
1
y
k
i
∪
⋃
1
≤
i
≤
t
j
-
1
x
i
∪
⋃
1
≤
i
≤
t
j
-
1
⋃
j
≤
k
≤
N
h
K
k
,
x
i
,
y
k
i
.
According to the features of the two-variable one-way functionh
(
K
,
x
), we know the following:(1)
Ifx
i and x
j (i
≠
j) are fed into h
(
K
,
x
) with the same key K, h
(
K
,
x
i
)
≠
h
(
K
,
x
j
).
(2)
Ifx
i is fed into h
(
K
,
x
) with different keys K and K
′, h
(
K
,
x
i
)
≠
h
(
K
′
,
x
i
).
Thus, the fake identifications of participants inA
′ are different, and they cannot deduce their own unknown fake identifications ⋃
1
≤
i
≤
t
j
-
1
⋃
1
≤
k
≤
j
-
1
h
(
K
k
,
x
i
) without K
1
,
K
2
,
…
,
K
j
-
1. Utilizing only ⋃
1
≤
i
≤
t
j
-
1
⋃
1
≤
k
≤
j
-
1
y
k
i
∪
⋃
1
≤
i
≤
t
j
-
1
x
i, polynomials f
1
x
,
f
2
x
,
…
,
f
j
-
1
(
x
) cannot be reconstructed by polynomial interpolation.
Utilizing⋃
1
≤
i
≤
t
j
-
1
h
(
K
j
,
x
i
)
,
y
j
i for each candidate point (
h
(
K
j
,
x
′
)
,
y
′
), they can reconstruct one and only one polynomial f
j
′
(
x
) of degree t
j
-
1, such that f
j
′
(
h
(
K
j
,
x
′
)
)
=
y
′ and f
j
′
(
h
(
K
j
,
x
i
)
)
=
y
i
j (1
≤
i
≤
t
j
-
1). Constructed in the same way, these possible polynomials are equally likely; thus, there is absolutely nothing the opponent can deduce about the real polynomial f
j
(
x
). Likewise, utilizing ⋃
1
≤
i
≤
t
j
-
1
⋃
j
+
1
<
k
≤
N
h
(
K
k
,
x
i
)
,
y
k
i, they cannot deduce anything about polynomials f
j
+
1
(
x
)
,
f
j
+
2
x
,
…
,
f
N
(
x
) either, where deg
⁡
f
k
(
x
)
>
d
e
g
f
j
(
x
)
=
t
j
-
1 (k
=
j
,
j
+
1
,
…
,
N).
In summary, the participants inA
′ cannot reconstruct polynomial f
N
(
x
) and obtain t
N hidden converted digits, which are the coefficients of polynomial f
N
(
x
)
. Likewise, they cannot obtain other converted digits. Thus, less than t
j participants cannot recover secret image S, after obtaining broadcast keys K
j
,
K
j
+
1
,
…
,
K
N.Theorem 3.
If thresholdt
j (1
≤
j
≤
N) is validated by broadcasting information, thresholds t
j
+
1
,
t
j
+
2
,
…
,
t
N are validated at the same time.Proof.
In the recovery procedure, assume that thresholdt
j (1
≤
j
≤
N) is validated by broadcasting keys K
j
,
K
j
+
1
,
…
,
K
N; then any t
j or more participants can collaborate to recover the secret image using their stego images. In addition, any t
′ (t
k
≤
t
′
≤
t
k
+
1, j
<
k
<
N) or more participants can also collaborate to recover the secret image with keys K
k
,
K
k
+
1
,
…
,
K
N. In other words, when threshold t
j is validated, thresholds t
j
+
1
,
t
j
+
2
,
…
,
t
N are also validated.


## 4.1. Simulation Results

The simulation settings of our experimental parameters were as follows:N
=
3, n
=
6, m
=
5, t
1
=
2, t
2
=
3, and t
3
=
4 (i.e., this scheme is a (
{
2,3
,
4
}
,
6
) threshold changeable secret sharing scheme). Let the real identification of six participants be X
=
1,2
,
3,4
,
5,6. We used image Baboon with 256
×
256 pixels as the secret image, as shown in Figure 3. We embedded shares into the original cover pixels, except for those pixels within 255
/
m
×
m
,
255 as Lin and Chan’s scheme [7] does.Figure 3
Secret image Baboon.To compare the quality of the stego images for different cover images, we selected twelve gray-scale test cover images with512
×
512 pixels to conduct the experiment. The twelve cover images are shown in Figure 4.Figure 4
Twelve cover images.
(a)
Airplane
(b)
House
(c)
Bird
(d)
Cameraman
(e)
Couple
(f)
Crowd
(g)
Fruits
(h)
Boat
(i)
Lake
(j)
Lena
(k)
Peppers
(l)
TiffanyTable1 displays the corresponding PSNR values of the stego images for the test cover images by our (
{
2,3
,
4
}
,
6
) threshold changeable secret image sharing scheme.Table 1
PSNR values (dB) of the stego images tested in 12 cover images.
Cover images
PNSR of stego 1
PNSR of stego 2
PNSR of stego 3
PNSR of stego 4
PNSR of stego 5
PNSR of stego 6
Average
Airplane
41.24
39.99
40.44
39.62
38.51
40.46
40.04
Boat
41.24
39.98
40.42
39.59
38.48
40.46
40.02
Bird
41.24
39.98
40.43
39.60
38.47
40.46
40.03
Cameraman
41.19
39.93
40.37
39.55
38.41
40.41
39.98
Couple
41.26
40.01
40.46
39.64
38.52
40.49
39.97
Crowd
41.09
39.85
40.26
39.46
38.26
40.30
40.06
Fruits
41.26
40.01
40.45
39.63
38.48
40.48
40.05
House
41.29
40.17
40.68
39.87
39.53
40.73
40.38
Lake
41.25
39.98
40.43
39.62
38.49
40.48
40.04
Lena
41.23
39.97
40.42
39.60
38.47
40.45
40.02
Peppers
41.23
39.97
40.42
39.60
38.48
40.45
40.02
Tiffany
41.26
40.03
40.47
39.64
38.54
40.49
40.04Table1 indicates that the cover image has little effect on the quality of the stego images. All of the PSNR values of our experiments are about 40 dB, which is greater than 35 dB, indicating that the quality of the stego images is satisfactory.In the recovery procedure of our(
{
2,3
,
4
}
,
6
) scheme, we set t
2
=
3 as the threshold value, and we broadcast the corresponding secret keys K
2
,
K
3. For convenience, we used stego images (a), (b), and (c) to reconstruct the secret image. Figure 5 shows cover image Lena, six stego images, and reconstructed secret image Baboon. The average PSNR value of the six stego images (i.e., images (a), (b), (c), (d), (e), and (f)) is 40.02 dB. We observe that each stego image shown in Figure 5 has a natural appearance and cannot leak any information about the secret image. The secret image recovered by stego images (a), (b), and (c) is displayed as image (g), which is the same as the original secret image.Figure 5
Six stego images, recovered secret image Baboon, and cover image Lena.
(a)
Stego image 1, PSNR=
41.23 dB
(b)
Stego image 2, PSNR=
39.97 dB
(c)
Stego image 3, PSNR=
40.42 dB
(d)
Stego image 4, PSNR=
39.60 dB
(e)
Stego image 5, PSNR=
38.47 dB
(f)
Stego image 6, PSNR=
40.45 dB
(g)
Recovered secret image Baboon
(h)
Cover image Lena


## 4.2. Performance Analysis

Factorsm and N potential thresholds t
1
,
t
2
,
…
,
t
N are important in our scheme’s ability to maximize the secret capacity and preserve the fidelity of the stego images. The influence of these two factors is discussed in this section.Table2 displays the relationship of capacity and distortion for different m values. Image Baboon is used as the secret image in all of those experiments, and Lena is used as the cover image. The parameters are as follows: N
=
3, n
=
6, t
1
=
2, t
2
=
3, and t
3
=
4. Table 2 indicates that (1) the number of influenced bits is increased as the value of factor m increases; (2) the capacity of the embedded converted data is increased as the value of factor m increases; and (3) the value of PSNR is decreased as the value of factor m increases. Since the difference between the original pixel in the cover image and the camouflaged pixel in the stego image is limited to [
0
,
m
-
1
], it becomes smaller as the value of factor m decreases; that is, the quality of the stego images increases as factor m decreases. But a smaller m value can increase the number of converted digits; that is, the capacity of the embedded converted data is decreased. Different from Lin and Chan’s scheme [7] which constructs one polynomial, we construct N polynomials to embed t
N converted digits into N pixels of the cover image in one iteration of polynomial calculation. Assuming that this cover image has H
c
×
W
c pixels, it can embed H
c
×
W
c
×
t
N
/
N converted digits (i.e., H
c
×
W
c
×
t
N
/
N
×
l
o
g
m
255 pixels). Table 2 indicates that the values of the PSNR are greater than 35 dB when the values of m are set as 5 and 7. Since the capacity when m is 7 is greater than that when m is 5, setting m as 7 is more suitable in this situation.Table 2
Relationship of the capacity distortion for differentm values.
m
Distortion
Capacity (pixels)
PSNR (dB)
[
0
,
m
-
1
]
Influenced bits
5
0,4
3
H
×
W
×
t
N
/
N
×
4
40.02
7
0,6
3
H
×
W
×
t
N
/
N
×
3
38.41
11
0,10
4
H
×
W
×
t
N
/
N
×
3
32.61
13
0,12
4
H
×
W
×
t
N
/
N
×
3
30.60
17
0,16
5
H
×
W
×
t
N
/
N
×
2
28.90
19
0,18
5
H
×
W
×
t
N
/
N
×
2
28.22
23
0,22
5
H
×
W
×
t
N
/
N
×
2
26.76The selection ofN potential thresholds t
1
,
t
2
,
…
,
t
N is another critical factor that influences the quality of the stego images. Table 3 shows the performance comparisons of different potential thresholds. In these experiments, we set test potential thresholds as 2,3, 3,4, 4,5, 3,5, and [
4,6
], and we set factor m
=
5. As in the above experiments, image Baboon is used as the secret image, and image Lena is the cover image.Table 3
Performance comparisons of different potential thresholds.
Number
Potential thresholds
Capacity
PSNR (dB)
1
[
2,3
]
H
×
W
×
3
/
8
43.79
2
[
3,4
]
H
×
W
×
4
/
8
45.06
3
[
4,5
]
H
×
W
×
5
/
8
46.08
4
[
3,5
]
H
×
W
×
5
/
8
46.03
5
[
4,6
]
H
×
W
×
6
/
8
46.86In our(
{
t
1
,
t
2
,
…
,
t
N
}
,
n
) threshold changeable secret image sharing scheme, since we camouflage t
N converted digits in (
t
N
-
1
)-degree polynomial f
N
(
x
), the order of polynomial f
N
(
x
) increases as t
N increases, which means that, for the same secret image and factor m, the number of camouflaged pixels decreases as t
N increases (i.e., the value of PSNR increases as t
N increases, and the capacity of embedding converted data in the cover image increases as t
N increases, which were indicated in Table 3). At the same time, we focus on the performance when the potential thresholds were set as [
3,5
] and [
4,5
], and we observed that different potential thresholds had little effect on the quality of the stego images when t
N and N were fixed. In our scheme, we need to construct H
s
×
W
s
×
log
m
⁡
255
/
t
N polynomials and camouflage H
s
×
W
s
×
N
×
log
m
⁡
255
/
t
N pixels of the cover image, where H
s and W
s are the height and width of gray-scale secret image S, respectively. Thus, the difference of potential thresholds cannot influence the quality of the stego images when t
N and N were fixed.Table4 compares our scheme with Chang et al.’s scheme (2008) [25], Lin et al.’s scheme (2009) [6], Lin and Chan’s scheme (2010) [7], and Ulutas et al.’s scheme (2013) [10]. We still use image Baboon as the secret image and image Lena as the cover image, and set m
=
5.Table 4
Comparisons of the related secret image sharing mechanisms.
Functionality
Chang et al. (2008) [25]
Lin et al. (2009) [6]
Lin and Chan (2010) [7]
Ulutas et al. (2013) [10]
Ours
Threshold
(
t
,
n
)
(
t
,
n
)
(
t
,
n
)
(
t
,
n
)
(
t
1
,
t
2
,
…
,
t
N
,
n
)
Threshold changeability
No
No
No
No
Yes
Quality of stego images
40.33 dB
43.02 dB
42.36 dB
46.79 dB
40.02 dB
Lossless secret image
Yes
Yes
Yes
Yes
Yes
Lossless cover image
No
Yes
Yes
Yes
No
Maximum capacity (pixels)
H
×
W
4
(
t
-
3
)
×
H
×
W
3
(
t
-
1
)
×
H
×
W
log
m
⁡
255
(
t
-
2
)
×
H
×
W
4
t
N
×
H
×
W
N
×
log
m
⁡
255Table4 indicates that our scheme has the unique threshold changeable characteristic and can recover the secret image without distortion. Since we camouflaged t
N converted digits in N pixels of the cover image in each iteration, which requires much more modification of the cover image, our scheme has lower quality of stego images and capacity of embedded converted digits. However, the average PSNR value of our scheme is 40 dB, which indicates that the quality of our stego images is acceptable. In addition, in practice, N is usually a small integer (such as N
=
3) corresponding to the “low, middle, and high” level of security in computers while t
N could be linearly related to n, so the capacity of embedded converted digits usually is acceptable.In some situation, we need to share important secret image using sensitive cover images (such as medical, military, or artistic images) and these cover images need to be recovered without distortion. To satisfy this requirement, our scheme can embed the recovery information of the cover image pixels into the polynomials as Lin and Chan’s scheme [7] does. But in this situation, we can only embed t
N
-
N converted digits into N pixels of the cover image in one iteration, which weakens the quality of the stego images and reduces the capacity to H
c
×
W
c
×
(
t
N
-
N
)
/
(
N
×
log
m
⁡
255
), where H
c and W
c are the height and width of gray-scale cover image C, respectively.


## 4.3. Security Analysis

In this section, we analyze the security of our scheme.First, we notice that our scheme can only change the threshold once. After the dealer broadcasts keysK
j
,
K
j
+
1
,
…
,
K
N to validate threshold t
j (1
≤
j
≤
N), then it takes at least t
j cooperating participants to recover the secret image without distortion. If the new threshold must be changed to t
k (1
≤
k
<
j), the dealer broadcasts keys K
k
,
K
k
+
1
,
…
,
K
j
-
1 to achieve this. On the contrary, if j
<
k
≤
N, the shares must be updated. In schemes that have strict security requirements, it is inevitable that shares are updated. For instance, the threshold in schemes [27, 28] can be changed many times, but, when one participant leaves the group, the shares should be updated simultaneously.Theorem 1.
Before broadcasting the keys, no participant can recover secret imageS.Proof.
In the worst situation, there aren participants in set A
′
=
{
P
1
,
P
2
,
…
,
P
n
} who want to recover the secret image. Assume that they want to recover the first t
N converted digits hidden in polynomial f
N
(
x
). Then, the participants in A
′ can obtain(11)
⋃
1
≤
i
≤
n
⋃
1
≤
k
≤
N
y
k
i
∪
⋃
1
≤
i
≤
n
x
i
.
Our scheme is based on polynomial interpolation; that is, givent points (
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
t
,
y
t
) with distinct x
i, there is one and only one (
t
-
1
)-degree polynomial f
(
x
) such that f
(
x
i
)
=
y
i for all 1
≤
i
≤
t. However, the polynomial cannot be reconstructed with less than t points. According to the features of the two-variable one-way function h
(
K
,
x
), without keys K
1
,
K
2
,
…
,
K
N, each participant P
i (1
≤
i
≤
n) cannot compute her/his fake identifications h
K
1
,
x
i
,
h
K
2
,
x
i
,
…
,
h
(
K
N
,
x
i
), which are fed into polynomials f
1
x
,
f
2
x
,
…
,
f
N
(
x
) to generate the shares y
1
i
,
y
2
i
,
…
,
y
N
i in the sharing procedure. Thus, utilizing only ⋃
1
≤
i
≤
n
⋃
1
≤
k
≤
N
y
k
i, no polynomial in f
1
x
,
f
2
x
,
…
,
f
N
(
x
) can be reconstructed by polynomial interpolation, and they cannot obtain the converted digits that are hidden in the coefficients of polynomial f
N
(
x
). Likewise, the participants in A
′ cannot obtain other converted digits, so the secret image cannot be recovered by any participant.Theorem 2.
After obtaining broadcast informationK
j
,
K
j
+
1
,
…
,
K
N, less than t
j participants cannot recover secret image S.Proof.
Without loss of generality, assume that there aret
j
-
1 participants in set A
′
=
{
P
1
,
P
2
,
…
,
P
t
j
-
1
} who want to recover the secret image. Assume that they want to recover the first t
N converted digits that are hidden in polynomial f
N
(
x
). Then, the participants in A
′ can obtain(12)
⋃
1
≤
i
≤
t
j
-
1
⋃
1
≤
k
≤
j
-
1
y
k
i
∪
⋃
1
≤
i
≤
t
j
-
1
x
i
∪
⋃
1
≤
i
≤
t
j
-
1
⋃
j
≤
k
≤
N
h
K
k
,
x
i
,
y
k
i
.
According to the features of the two-variable one-way functionh
(
K
,
x
), we know the following:(1)
Ifx
i and x
j (i
≠
j) are fed into h
(
K
,
x
) with the same key K, h
(
K
,
x
i
)
≠
h
(
K
,
x
j
).
(2)
Ifx
i is fed into h
(
K
,
x
) with different keys K and K
′, h
(
K
,
x
i
)
≠
h
(
K
′
,
x
i
).
Thus, the fake identifications of participants inA
′ are different, and they cannot deduce their own unknown fake identifications ⋃
1
≤
i
≤
t
j
-
1
⋃
1
≤
k
≤
j
-
1
h
(
K
k
,
x
i
) without K
1
,
K
2
,
…
,
K
j
-
1. Utilizing only ⋃
1
≤
i
≤
t
j
-
1
⋃
1
≤
k
≤
j
-
1
y
k
i
∪
⋃
1
≤
i
≤
t
j
-
1
x
i, polynomials f
1
x
,
f
2
x
,
…
,
f
j
-
1
(
x
) cannot be reconstructed by polynomial interpolation.
Utilizing⋃
1
≤
i
≤
t
j
-
1
h
(
K
j
,
x
i
)
,
y
j
i for each candidate point (
h
(
K
j
,
x
′
)
,
y
′
), they can reconstruct one and only one polynomial f
j
′
(
x
) of degree t
j
-
1, such that f
j
′
(
h
(
K
j
,
x
′
)
)
=
y
′ and f
j
′
(
h
(
K
j
,
x
i
)
)
=
y
i
j (1
≤
i
≤
t
j
-
1). Constructed in the same way, these possible polynomials are equally likely; thus, there is absolutely nothing the opponent can deduce about the real polynomial f
j
(
x
). Likewise, utilizing ⋃
1
≤
i
≤
t
j
-
1
⋃
j
+
1
<
k
≤
N
h
(
K
k
,
x
i
)
,
y
k
i, they cannot deduce anything about polynomials f
j
+
1
(
x
)
,
f
j
+
2
x
,
…
,
f
N
(
x
) either, where deg
⁡
f
k
(
x
)
>
d
e
g
f
j
(
x
)
=
t
j
-
1 (k
=
j
,
j
+
1
,
…
,
N).
In summary, the participants inA
′ cannot reconstruct polynomial f
N
(
x
) and obtain t
N hidden converted digits, which are the coefficients of polynomial f
N
(
x
)
. Likewise, they cannot obtain other converted digits. Thus, less than t
j participants cannot recover secret image S, after obtaining broadcast keys K
j
,
K
j
+
1
,
…
,
K
N.Theorem 3.
If thresholdt
j (1
≤
j
≤
N) is validated by broadcasting information, thresholds t
j
+
1
,
t
j
+
2
,
…
,
t
N are validated at the same time.Proof.
In the recovery procedure, assume that thresholdt
j (1
≤
j
≤
N) is validated by broadcasting keys K
j
,
K
j
+
1
,
…
,
K
N; then any t
j or more participants can collaborate to recover the secret image using their stego images. In addition, any t
′ (t
k
≤
t
′
≤
t
k
+
1, j
<
k
<
N) or more participants can also collaborate to recover the secret image with keys K
k
,
K
k
+
1
,
…
,
K
N. In other words, when threshold t
j is validated, thresholds t
j
+
1
,
t
j
+
2
,
…
,
t
N are also validated.


## 5. Conclusions

Before recovering the secret image, the threshold may have to be adjusted for the change of the security policy and the adversary’s structure. To solve this problem, we propose a(
{
t
1
,
t
2
,
…
,
t
N
}
,
n
) threshold changeable secret image sharing scheme with N potential thresholds t
1
,
t
2
,
…
,
t
N. Our scheme can validate new threshold t
i (1
≤
i
≤
N) by broadcasting the corresponding keys K
i
,
K
i
+
1
,
…
,
K
N, and then t
i or more participants can recover secret image S without distortion. The experiments and analysis showed that the threshold in our scheme can be changed dynamically and that the security can be maintained after these changes. In addition, the quality of the stego images is satisfactory.However, in order to make the threshold changeable, we embed large amounts of redundant data into the cover image, which requires much more modification of the cover image, so the quality of the stego images is lower than other schemes. At the same time, we do not embed the recovery information ofN pixels of the cover image in order to increase the capacity, so the cover image in our scheme cannot be recovered without distortion. We will address these issues in future work.



---

*Source: 9576074-2016-07-11.xml*