1 Introduction
(
k,
n) threshold secret sharing scheme was first proposed by Shamir [
1] in 1979 for safeguarding secret information among a group of participants. In [
1], a secret
s is encrypted into
n shares
v1,
v2,...,
v
n
using a
k − 1-th degree polynomial in such a way that less than
k shares get no information on the secret
s; any
k or more shares can recover the secret
s efficiently. Secret sharing scheme is a fundamental tool for other cryptographic protocols [
2]. In 2002, Thien and Lin extended Shamir’s secret sharing and proposed a (
k,
n) threshold secret image sharing scheme [
3] by regarding an image as secret information. The (
k,
n) secret image sharing schemes can be mainly divided into two categories: polynomial-based schemes [
4‐
6] and visual cryptography schemes [
7‐
9]. Polynomial-based secret image sharing schemes can reconstruct a lossless image with reduced shadow size; the image reconstruction in visual cryptography schemes can be simply accomplished by human visual system without any computation. However, a reconstructed image is lossy and the size of shadow is greatly expanded from the original image.
The cheating scenario in secret sharing scheme was first proposed in 1989 by Tompa and Woll [
7]. They considered the scenario that some dishonest participants (cheaters) pool fake shares when reconstructing the secret. In this way, the cheaters could recover a secret exclusively, and the honest participants can only recover a forged secret. Many works have focused on solving the cheating problem in secret sharing schemes. Some [
10‐
12] were interested in detecting the cheating behavior, and some works [
13‐
15] focused on not only detecting the cheating behavior, but also identifying the cheaters. The cheating identifiable schemes have stronger capability to resist cheating; it results that the shares are larger and the schemes are more complicated than those cheating detectable schemes. Polynomial-based secret image sharing scheme was extended from Shamir’s scheme [
1]. As a result, the problem of cheating is also an important topic in polynomial-based secret image sharing. However, this issue has not been discussed sufficiently so far. In [
16‐
19], some secret image sharing schemes with authentication and steganography were capable of detecting the cheating. However, these secret image sharing schemes were not extensions of Shamir’s scheme and the capabilities of cheating detection were not strong enough to prevent cheating.
In this work, we consider the problem of cheating in the fundamental polynomial-based secret image sharing scheme [
3]. Since cheating identifiable scheme requires large size expansion on shadows and much more complicated identification algorithm, we consider the cheating detection to prevent cheating behavior in this work. A (
k,
n) threshold secret image sharing scheme capable of detecting
k − 1 cheaters is constructed. In addition, the size of image-shadow in our scheme is almost same as the shadow size in the scheme [
3]. The computational complexity of cheating detection is efficient. The rest of this paper is organized as follows: Some preliminaries which include Shamir’s (
k,
n) secret sharing scheme, polynomial-based secret image sharing scheme, and the model of cheating detection in secret sharing scheme are introduced in Section
2. In the next section, a (
k,
n) threshold secret image sharing scheme with cheating detection is proposed. The properties of proposed scheme and experimental results will be shown in Section
4, and we make a conclusion in Section
5.
3 (k,n) secret image sharing with cheating detection
The problem of cheating in secret image sharing is considered in this part, such that some cheaters submit forged image-shadows during image reconstruction phase. It results that these cheaters are able to recover secret image exclusively, and the honest participants recover only a fake image. In order to solve this problem, we construct a (
k,
n) threshold secret image sharing scheme capable of detect cheating under the model in Section
2.2. Our scheme is extended from Thien-Lin’s fundamental scheme which can be adopted in other polynomial-based secret image sharing schemes. Our scheme is shown in
Scheme 3.
Scheme 3: (
k,
n) secret image sharing scheme capable of detect cheating
-
Shadow Generation Phase: Input a secret image
I, output
n image-shadows
S1,
S2,…,
S
n
-
The dealer divides I into t-non-overlapping 2k−2-pixel blocks, B1,B2,...,B
t
.
-
For each block B
i
,i∈ [ 1,t], there are 2k − 2 secret pixels ai,0,ai,1,…,ai,k−1 and bi,2,bi,3,…,bi,k−1∈GF(251). The dealer generates a k−1-th degree polynomial f
i
(x) = ai,0 + ai,1x+,…,+ai,k − 1xk − 1∈GF(251)[ X].
-
The dealer chooses a random integer r
i
, and computes two pixels bi,0,bi,1 which satisfy that: r
i
ai,0 + bi,0 = 0,r
i
ai,1 + bi,1 = 0 over GF(251). Then the dealer generates another k − 1-th degree polynomial g
i
(x) = bi,0 + bi,1x+…,+bi,k − 1xk−1.
-
For each block B
i
,i∈ [ 1,t], the dealer computes sub-shadow vi,j = {mi,j,di,j},mi,j = f
i
(j),di,j = g
i
(j),j=1,2,…,n for each participant P
j
. The shadow S
j
for P
j
is S
j
= v1,j∥v2,j∥,…,∥vt,j.
-
Image Reconstruction Phase: Input
k shadows, without loss of generality (
S1,
S2,…,
S
k
)
-
Extract vi,j = (mi,j,di,j),i=1,2,…,t,j = 1,2,…,k from S1,S2,…,S
k
.
-
For each group of vi,1,vi,2,…,vi,k,i∈ [ 1,t], reconstruct f
i
(x) and g
i
(x) from mi,1,mi,2,…,mi,k and di,1,di,2,…,di,k using Lagrange interpolation respectively.
-
Let
ai,0,
ai,1,
bi,0 and
bi,1 be the coefficients of
x0 and
x in
f
i
(
x) and
g
i
(
x) respectively.
-
If there exist a common integer r
i
which satisfies that r
i
ai,0 + bi,0 = 0 and r
i
ai,1+bi,1 = 0, recover the 2k − 2–pixel block \( B_{i}\! =\!\left \{a_{i,0},a_{i,1},\ldots,\right. \left. a_{i,k-1},b_{i,2},_{i,3} \!,\ldots,\!b_{i,k\,-\,1}\right \}\), the secret image I is I = B1∥B2∥,…,∥B
t
.
-
Else, there are fake shadows participating in image reconstruction; the cheating is detected, output ⊥.
Notice that in Thien-Lin’s scheme, the size on image-shadow is \(\frac {1}{k}\) times of the image. In our scheme, the share vi,j = (mi,j,di,j) are generated from each 2k−2-pixel block; therefore, the size on image-shadow in our scheme is \(\frac {2}{2k-2}=\frac {1}{k-1}\) times of image I.
The features of our scheme will be described in following theorems. Theorem 1 proves that our scheme satisfies the property of (k,n) threshold, such that less than k image shadows get no information on secret image; k or more image-shadows are able to recover secret image. In Scheme 3, the secret image I is cut into 2k−2-pixels blocks B1,B2,…,B
t
. Each block is encrypted by the same approach; we only need to prove that the n shares v1,j,j=1,2,…,n on block B1 satisfy the (k,n) threshold property. The property of detect cheating will be analyzed in Theorem 2.
It seems that the relationship between a0,a1,b0,b1 would leak some information on the secret. However, the following Theorem 1 will prove that a0,a1,b0,b1 leak no information about the secret at all, and the proposed scheme is a perfect (k,n) threshold secret image sharing scheme that satisfies the threshold property. The capability of cheating detection of proposed scheme is discussed in Theorem 2.
In the following, we will prove that
k−1 participants are unable to get any information of the 2
k−2 pixels. Since in the proposed scheme,
ai,0,
ai,1,
bi,0,
bi,1 have the relationships that
r
i
ai,0+
bi,0=0 and
r
i
ai,1+
bi,1=0, it seems that the method of exhaustion could resolve the 2
k−2 pixels. We describe the method of exhaustion below.
-
all k−1 participants use all possible shares on the k-th participant and generates p=251 corresponding interpolation polynomials \(f^{u}_{i}(x),u=1,2,\ldots,251\) and \(g^{u}_{j}(x),u=1,2,\ldots,251\).
-
If \(f^{u^{*}}_{i}(x)\) and \(g^{v^{*}}_{i}(x)\) satisfy \(r_{i}a^{'}_{0}+b^{'}_{0}=0\) and \(r_{i}a^{'}_{1}+b^{'}_{1}=0\) where \(a^{'}_{0},b^{'}_{0},a^{'}_{1},b^{'}_{1}\) are coefficients of x0,x in \(f^{u^{*}}_{i}(x)\) and \(g^{v^{*}}_{j}(x)\). Then \(f^{u^{*}}_{i}(x)\) and \(g^{v^{*}}_{i}(x)\) would be the original polynomials selected by dealer, and all the 2k−2 pixels can be gotten from \(f^{u^{*}}_{i}(x)\) and \(g^{v^{*}}_{i}(x)\).
Assume that m∗(k) is the share of k-th participant that is randomly selected, then the k−1 participants generates a k−1-th degree polynomial f
i
(x) from \((1,m_{1}),(2,m_{2}),\ldots,(k-1,m_{k-1}),\left (k,m^{*}_{k}\right)\). Let \(a^{'}_{0},a^{'}_{1}\) be the corresponding coefficients in f
i
(x). According to the method of exhaustion described previously, if there exists a k−1-th degree polynomial \(g_{j}(x)=b^{'}_{0}+b^{'}_{1}x+,\ldots,+b^{'}_{k-1}x^{k-1}\) which is interpolated by \((1,d_{1}),(2,d_{2}),\ldots,(k-1,d_{k-1}),\left (k,d^{*}_{k}\right)\), satisfies that \(r^{'}a^{'}_{0}+b^{'}_{0}=0, r^{'}a^{'}_{1}+b^{'}_{1}=0\) (\(\phantom {\dot {i}\!}r^{'}\) could be any value in GF(251)), then f
i
(x) and g
i
(x) are the two polynomials selected by the dealer. \(b^{'}_{0},b^{'}_{1},\ldots,b^{'}_{k-1}\) and \(\phantom {\dot {i}\!}r^{'}\) can be regarded as k+1 unknowns, then k+1 linear equations on these unknowns can be established: \(g^{'}(i)=d_{i},i=1,2,\ldots,k-1, r^{'}a^{'}_{0}+b^{'}_{0}=0, r^{'}a^{'}_{1}+b^{'}_{1}=0\). (Here \(a^{'}_{0},a^{'}_{1}\) are known to the k−1 participants.) Therefore, all the unknowns \(b^{'}_{0},b^{'}_{1},\ldots,b^{'}_{k-1}\) can be obtained from these equations; we can also get the polynomial g
i
(x). It means that the k−1 participants will find that each possible share could be the valid share of the kth participant. This proves that the approach of exhaustion cannot work in the proposed scheme.
An example is used to show the approach of exhaustion in proposed scheme. Assume k=4 and two polynomials f(x)=1+3x+4x2+5x3 and g(x)=4+5x+x2+3x3 over GF(7) are chosen by the dealer. It is obvious that 3a0+b0=0,3a1+b1=0. Let P1.P2,P3,P4 be the four participants; the shares of them are P1: (m1=6,d1=6), P2: (m2=0,d2=0), P3: (m3=6,d3=4), and P4: (m4=5,d4=1). Suppose P1,P2,P3 try to recover secret using approach of exhaustion. As described previously, they can randomly assume the sub-share of P4: \(m^{*}_{4}=0\) and generate an interpolation polynomial \(\phantom {\dot {i}\!}f^{'}(x)=6+2x+2x^{2}+3x^{3}\) correspondingly. Then they try each possible sub-share \(d^{*}_{4}\) of P4 and verify whether it is fit. For instance, when they use \(d^{*}_{4}=2\), the interpolating polynomial is \(\phantom {\dot {i}\!}g^{'}(x)=3+x+2x^{3}\). The coefficients \(a^{'}_{0},a^{'}_{1},b_{0}^{'},b_{1}^{'}\) satisfy that \(3a^{'}_{0}+b^{'}_{0}=0,3a^{'}_{1}+b^{'}_{1}=0\). Then they get the conclusion that \(\phantom {\dot {i}\!}f^{'}(x),g^{'}(x)\) would be the valid polynomials and \(\phantom {\dot {i}\!}s^{'}=f^{'}(0)=6\) is the secret. In fact, they recover a wrong secret. End of proof.
The capability of cheating detection in our scheme is analyzed in Theorem 2.
Proof
Suppose P1,P2,...,P
k
participate in secret reconstruction phase and P1,P2,...,Pk−1 are cheaters. Since cheating detection algorithm is used in each block B
i
,i∈[ 1,t], we only analyze the cheating detection in decoding B1 in this theorem. Suppose the fake shares from cheaters are \(v^{*}_{i}=\left (m_{i}+m^{*}_{i},d_{i}+d^{*}_{i}\right),i=1,2,\ldots,k-1\). They can get two polynomials f∗∗(x)=f(x)+f∗(x),g∗∗(x)=g(x)+g∗(x) in image reconstruction phase, where \(f^{*}(x)=a^{*}_{0}+a^{*}_{1}x+\cdots +a^{*}_{k-1}x^{k-1}\) and \(g^{*}(x)=b^{*}_{0}+b^{*}_{1}x+\cdots +b^{*}_{k-1}x^{k-1}\) are interpolated polynomials on the k points \((1,m^{*}_{1}),\left (2,m^{*}_{2}\right),\ldots, \left (k\,-\,1,m^{*}_{k-1}\right),(k,0)\) and \(\left (1,d^{*}_{1}\right),\left (2,d^{*}_{2}\right),\ldots,\left (k-1,d^{*}_{k-1}\right), (k,0)\) respectively. Since f∗(x) and g∗(x) can be decided by cheaters exclusively, they can select a random number r∗, and satisfy that \(r^{*}a^{*}_{0}+b^{*}_{0}=0, r^{*}a^{*}_{1}+b^{*}_{1}=0\). According to our algorithm, if there exists a common number \(\phantom {\dot {i}\!}r^{'}\), satisfying \(r^{'}\left (a_{0}+a^{*}_{0}\right)+b_{0}+b^{*}_{0}=0, r^{'}\left (a_{1}+a^{*}_{1}\right)+b_{1}+b^{*}_{1}=0\), the cheating avoids detection. We can easily observe that the cheating succeeds only when r∗=r. As analyzed in Theorem 1, these k−1 cheaters have no information on r; the possibility of r∗=r is \(\frac {1}{251}\). As a result, the successful cheating probability is \(\epsilon =\frac {1}{251}\). Since all the pixels are in GF(251), the successful cheating possibility \(\epsilon =\frac {1}{251}\) means that our scheme is effective to detect the cheating. End of proof. □
4 Results and discussion
In this part, we use an example to describe the cheating detection using our scheme. Let (k,n)=(4,7) and the secret image I is divided into t blocks where each block includes 2k−2=6 secret pixels. Assume the first block B1 consists of the following 6 pixels: (57,68,90,231,42,89), the dealer selects an integer r1=9, and generates two k−1=3-th degree polynomials: f1(x)=57+68x+90x2+231x3 and g1(x)=161+104x+42x2+89x3, where 57+9∗161=0(mod251),68+9∗104=0(mod251). The n=7 shares from B1 are v1,1=(195,145),v1,2=(142,245),v1,3=(29,242),v1,4=(238,168),v1,5=147,55,v1,6=(138,186),v1,7=(91,91).
Suppose P1,P2,P3, and P4 participate in image reconstruction and P1,P2,P3 are k−1=3 cheaters. They submit forged shares \(v^{*}_{1,1}=(105,87),v^{*}_{1,2}=(162,31),v^{*}_{1,3}=(23,98)\) in image reconstruction. As a result are two polynomials \(f^{*}_{1}(x)=55+188x+105x^{2}+8x^{3}\) and g∗(x)=135+167x+56x2+231x3. Since there is no common integer r1 satisfying that 55r1+135=0(mod251) and 188r1+167=0(mod251), the cheating is successfully detected.
The cheating detection approach in our scheme is also efficient with other cheating detectable secret sharing schemes. Table
1 shows the comparisons between our scheme and other schemes in cheating detection. When comparing to those cheating detectable secret image sharing schemes [
16‐
19], our scheme achieves much stronger capability. It can detect cheating from up to
k−1 cheaters, while other schemes work only when there are less than
\(\frac {k}{2}\) cheaters.
Table 1
Comparisons between cheating detectable secret sharing schemes
| |V|=|S| | Fail | |
| |V|=|S| | 1 |
\(\epsilon =\frac {1}{p}\)
|
|
\(|V|=2\frac {|S|}{\epsilon }\)
| k−1 |
\(\epsilon =\frac {2}{p}\)
|
Proposed scheme |
\(|V|=\frac {|S|}{\epsilon }\)
| k−1 |
\(\epsilon =\frac {1}{p}\)
|