Fake and dishonest participant location scheme in secret image sharing

1.   Introduction

With the rapid development of computer technology, the importance of information security becomes more and more prominent. As an important carrier of information transmission, image protection has been paid more and more attention by the society. And image encryption technology has developed rapidly in recent years. For different image protection needs, various image encryption technology was proposed, including modern cryptographic mechanism ^[1,2] (such as DES, RSA, secret image sharing), digital watermarking technology ^[3,4,5], compressive sensing technology ^[6,7,8], etc. Among them, secret image sharing technology divides the secret into $n$ shadows and only $k$ or more than $k$ shadows can reconstruct the secret. Due to this characteristic, it is widely used in access control, information hiding, key management and so on.

Blakley^[9] and Shamir^[10] firstly proposed the concept of secret sharing independently in 1979. Then more and more secret sharing schemes have been proposed. For example, Gutub et al. proposed a novel counting-based secret sharing scheme ^[11] by replacement operations in 2017. Al-Ghamdi et al. ^[12] enhanced the security of Gutub's scheme in 2018. ^[13] improved the security and efficiency of counting-based secret sharing scheme and ^[14] pursued higher security and lower computation complexity.

In 1995, Naor and Shamir^[15] introduced the threshold control into image field and proposed visual cryptography: visual secret sharing(VSS). The secret image is shared into $n$ transparencies. Any $k$ of them can reveal the secret by stacking $k$ transparencies, but any $k-1$ of them cannot get any information on secret. The essence of VSS is stacking recovery or XOR recovery, which requires little or no cryptographic computations. However, VSS has disadvantages such as pixel expansion and low image quality which needs more research on it.

Based on the Shamir' polynomial-based method, Thien and Lin^[16] expanded the secret sharing into image encryption, also known as secret image sharing (SIS). SIS scheme for $(k, n)$ threshold divides a secret image into $n$ noise-like shadows. One can reconstruct the secret by $k$ or more than $k$ shadows while gain nothing from fewer than $k$ shadows.

In order to divide the secret $a_0$ into $n$ shadows, polynomial-based SIS constructs a $(k-1)$ degree polynomial with the secret $a_0$ and other $(k-1)$ randomly selecting numbers $a_1, a_2, \cdots, a_{k-1}$ to form the coefficients of the polynomial. $n$ shares ($f(i), i = 1, 2, \cdots, n$) are generated by using different variables. And the secret $a_0$ can be rebuilt by using Lagrange interpolation. The polynomial is defined as

where $P$ is a prime number, $a_0$ represents the secret information and $a_1, a_2, \cdots, a_{k-1}$ are selected randomly.

However, Shamir's original polynomial-based SIS is generally lossy recovery with higher computation and auxiliary encryption. Since the modulus P is chosen as 251 instead of 256, the recovery image will be lossy when the pixel value of the secret image exceeds 251. In the secret recovery phase, the computational complexity of Lagrange interpolation is as high as $O(klog^2k)$. And some auxiliary encryption may be applied before sharing.

In comparison with Shamir's original polynomial-based SIS, Chinese remainder theorem-based SIS has advantages of lossless recovery, low recovery computation(the modular only $O(k)$ operations) and no auxiliary encryption. Yan et al. ^[17] proposed a $(k, n)$ threshold secret image sharing scheme based on Chinese remainder theorem(CRTSIS) which is the basic algorithm in ^[18]. Through dividing the grayscale pixel values into two intervals corresponding to two available mapping intervals, the proposed method realizes $(k, n)$ threshold and lossless recovery for grayscale image without auxiliary encryption. We adopt CRTSIS as our sharing algorithm and the specific algorithm implementation is described in section 4.

However, traditional SIS scheme ignores the authenticity of shadows which is fatal in many scenarios such as e-voting, e-auctions and so on. The fake shadow may be forged by a fake participant to defraud the real shadow and then obtain the secret, or be generated by a dishonest participant. As an example, if a dishonest participant wants to monopolize the secret, he$\backslash$she only needs to forge a fake shadow in exchange for another $k-1$ real shadows. If there is no shadow authentication, only the dishonest participant can recover the secret and other $k-1$ participants cannot get any information on the secret. It is possible to find the dishonest participant with the help of other $n-k$ participants, but the execution complexity is high. Therefore, it is necessary to verify the authenticity of the shadows to locate the attacker.

The rest of the paper is organized as follows. Section 2 introduces related work. Section 3 demonstrates the application scenarios. Section 4 introduces some basic requirements for the proposed scheme. The proposed scheme is presented in detail in section 5. Section 6 shows the experimental results and analysis and section 7 concludes this paper.

2.   Related work

Chor et al. ^[19] firstly proposed "verifiable secret sharing" and achieved verifying through simultaneous broadcast network. Due to the widespread use of SIS, more and more attention is paid to verifiable SIS scheme.

Traditional SIS with shadow authentication capacity usually rely on hash function^[20,21] and information hiding method such as fragile watermark ^{[22,23,24,25,26]}. Li et al. ^[20] enhanced $(k, n)$ threshold SIS scheme with authentication. The size of stego image is reduced to $3.5/k$ times while it is $4$ times in previous scheme. And the authentication capability is guaranteed by hash function. Lin et al. ^[22] proposed a $(k, n)$ threshold SIS scheme with additional capabilities of steganography and authentication. A secret image is firstly shared into $n$ shares and then they are hidden into $n$ meaningful camouflage images to improve security. Furthermore, fragile watermark is embedded into camouflage images for authenticating the fidelity of each processed camouflage image. In general, most SIS schemes with authentication capability embed shares into cover images which leads to high generation and recovery complexity and pixel expansion.

Different from traditional methods, Yan et al. ^[27] proposed a $(k, n)$ threshold SIS scheme with a separate shadow authentication capacity. Yan et al. ^[27] combined polynomial-based SIS and VSS. A binary authentication image is split into two shadows by using the $(2, 2)$ threshold RG-VSS. One is distributed to dealer to verify the identities of participants, another is used to guide the generation of secret shadow images. Their scheme has the advantages of lossless recovery, no pixel expansion and precise detection. However, their scheme is only applicable to dealer-participatory. Another flaw is that their scheme can not resist the malicious behaviour of dishonest participants since they can easily forge a fake shadow passing verifying from the real shadow they hold.

Yang et al. ^[28] proposed a novel compressed SIS with shadow verification capability based on polynomial-based SIS and $(2, 2)$ threshold VSS. By utilizing the randomness of the sharing phase of polynomial-based SIS, one share generated from $(2, 2)$ threshold random-grid VSS is embedded into all shares of polynomial-based SIS as the verification information and another share is distributed to dealer for verification. In order to balance efficiency and safety, Yang et at. ^[28], unlike Thien and Lin^[16], uses coefficients $a_0$ and $a_{k-1}$ in Eq 1.1 to store secret information. However, the sharing process may fail when $k$ is less than $4$ due to small random range. Just like Yan et al.^[27], their scheme is only applicable to dealer-participatory and is invalid for dishonest participants.

Jiang et al. ^[29] proposed a SIS method for a $(k, n)$ threshold with dealer-participatory and non-dealer-participatory mutual shadow authentication capabilities. They combined polynomial-based SIS and $(2, n+1)$ threshold VSS utilized the result of the VSS to screen out the eligible secret shadow images. Due to the rigorous screening criterion and the Lagrange interpolation method, the computation complexity of generation and recovery phase is relatively high. In order to obtain a lossless reconstructed image, the prime $P$ in Eq 1.1 is set as 257. When the value of 256 appears, the screening operation is re-performed, which further increases the complexity of shadow generation. Similarly, Jiang's scheme can not detect the dishonest participants. In fact, we can find a more general approach in ^[30].

Traditional verifiable SIS schemes have disadvantages of pixel expansion, requiring extra information and high computation complexity. Yan et al. ^[27], Yang et al. ^[28] and Jiang et al. ^[29] have low efficiency in shadow generation process, relatively high computation complexity in secret recovery phase and no ability to detect dishonest participants. In addition, Yan et al. ^[27] and Yang et al. ^[28] are only applicable to dealer involved.

In this paper, we propose a verifiable SIS scheme combining CRT-based SIS and $(2, n+1)$ threshold VSS. A binary authentication image with the same size as the secret image is divided into $n+1(n)$ binary shadows with dealer involved(uninvolved). $N$ binary shadows are used to screen out the secret shadows meeting the criterion. When there exists a dealer, we utilize the uncertainty of the bits used for screening to detect the dishonest participants. When there is no dealer involved, participants verify the authenticity of shadows mutually. In addition, loose screening criterion and efficient encoding and decoding rate of CRT-based SIS guarantee high-efficiency shadows generation and low recovery computation complexity.

3.   Application scenarios

Here, we only consider three kinds of roles, participants, dealer and attacker. Dealer divides secret into shadows and distributes them to participants, participants hold their own shadow. As to attackers, we divide them into dishonest participants and fake participants, and the difference between them is whether they hold real shadows. More precisely, dishonest participants tend to monopolize secrets, while fake participants want to steal them. The proposed scheme is applicable to both dealer involved and dealer uninvolved. When there exists a dealer, he$\backslash$she is trusted by everyone. Dealer calculates and distributes shadows to participants. In the recovery phase, the dealer collects shadows to reconstruct the secret. If the recovery fails, the authenticity of shadows should be verified. The forged shadows may come from dishonest participants or fake participants. Dealer can accurately locate the attacker by the binary authentication shadow $S_1C_{n+1}$. Because of the uncertainty of bits used for screening, even the dishonest participant can not forge a fake shadow passing verification. When there is no dealer involved, all the participants trust each other, which implies that there is no dishonest participant. In this case, bits used for screening are fixed, and each participant can calculate the binary authentication shadow from the secret shadow they hold. Before the recovery phase, to prevent fake participants from impersonating participants, $k$ (or more) participants exchange binary authentication shadows. Only when the verification is successful can they exchange shadows to reconstruct the secret. Both these scenarios are common and meaningful in real life.

Herein, symbol $S$ and $S_1$ respectively represent grayscale secret image and binary authentication image and the notations used in this paper is introduced in Table 1. For the $(k, n)$ threshold, mark $n$ grayscale secret shadows as $SC_1, SC_2, \cdots, SC_n$ held by participants, use $S_1C_{n+1}$ to represent the binary authentication shadow belonging to dealer. $S_2C_1, S_2C_2, \cdots, S_2C_k$ respresent binary authentication shadows calculated from the secret shadows.

When there exists a dealer, as shown in Figure 1, Participant II is the attacker(dishonest participant or fake participant). Dealer collects $k$ shadows and try to reconstruct secret. Since shadow $SC_2$ is fake, recovery phase fails. Dealer then extracts $k$ binary authentication shadows $S_2C_1, S_2C_2, \cdots, S_2C_k$ from $SC_1, SC_2, \cdots, SC_k$ according to the bits used for screening. And dealer verifies the authenticity of shadows by doing XOR operation between $S_1C_{n+1}$ and $S_2C_i(i = 1, 2, \cdots, k)$. Finally, $S_2C_2$ fails the verification and Participant II is identified as the attacker.

When there is no dealer, $k$ participants verify the identities of others mutually. For each one of the $k$ participants, the identities of the remaining $k-1$ participants need to be verified, and on the other hand, each participant receives $k-1$ authentication results. Take $(3, 3)$ threshold as an example, as shown in Figure 2, Participant I, Participant II and Participant III hold secret shadows $SC_1, SC_2, SC_3$ respectively. They obtain their own binary authentication shadows $S_2C_1, S_2C_2, S_2C_3$ respectively calculated from the secret shadows they hold. In the verification phase, Participant I sends $S_2C_1$ to Participant II and Participant III and receives $S_2C_2$ and $S_2C_3$ from them. Participant I verifies the identities of Participant II and Participant III by doing XOR operation and receives two results from them. It is the same for Participant II and Participant III.

4.   Preliminaries

In this section, we introduce some preliminaries for the designed scheme. Herein, symbol $\oplus$ indicates the Boolean XOR. A grayscale secret image $S$ (a binary authentication image $S_1$) with the size of $H\times W$ is divided into $n$ ($n+1$) shadows denoted as $SC_1, SC_2, \cdots, SC_n$ ($S_1C_1, S_1C_2, \cdots, S_1C_{n+1}$). The first $n$ binary authentication shadows are used to guide the generation of secret shadows. The $(n+1)$-th binary authentication shadow is distributed to the dealer to verify the authenticity of shadows.

4.1.   (2-n)-VSS

Algorithm 1 describes the sharing phase for $(2, n)$ VSS. It is remarkable that Step 2 and Step 3 ensure that $b_{x_1} \oplus b_{x_2} = b_x$. Step 5 extends the threshold from $(2, 2)$ to $(2, n)$. In our proposal, it should be noted that when the threshold of SIS is $(k, n)$, the threshold of VSS is $(2, n+1)$ for dealer involved and $(2, n)$ for dealer uninvolved.

Recover: Choose any two shadows from the $n$ participants, do XOR operation between the corresponding pixel values and obtain the reconstructed binary image.

4.2.   SIS Based on CRT

4.2.1.   CRT

Chinese remainder theorem is an important theorem in number theory and has been widely used in various fields of information security such as RSA algorithm ^[31,32], secret sharing ^[17] and so on. And a lot of work ^[33,34] has been done to analyze the performance characteristics and security characteristics of the CRT-based cryptosystems. CRT aims to solve a set of linear congruence equations. A set of integers $m_i(i = 1, 2, \cdots, n)$ are chosen to subject to $gcd(m_i, m_j) = 1$ for $i \not = j$. Let $M = \prod^k_{i = 1} m_i, M_i = \frac{M}{m_i}$ and $M_iM^{-1}_i \equiv 1 \pmod {m_i}$. Then there exists only one solution $y \equiv (a_1M_1M^{-1}_1 + a_2M_2M^{-1}_2 + \cdots + a_kM_kM^{-1}_k) \pmod {M}$ in $[0, M-1]$ for the following linear congruence equations

4.2.2.   $(k, n)$ SIS based on CRT

A $(k, n)$ threshold secret image sharing scheme based on Chinese remainder theorem(CRTSIS) was proposed in ^[17]. The original secret image $S$ is divided into $n$ shadow images $SC_1, SC_2, \cdots, SC_n$ with corresponding privacy modular integers $m_1, m_2, \cdots, m_n$. The generation steps are described in Algorithm 2 and the recovery steps are presented in Algorithm 3.

The parameters of $p, m_1, m_2, \cdots, m_n$ for different thresholds we used in experiments are shown in Table 2. In the experiment, the parameters in Table 2 can guarantee the pixel values of secret shadows approximately uniform distribution in range $[0, m_i-1]$, which tells that each shadow gives no clue about the secret image.

5.   The designed scheme

In this section, we introduce the overview of the proposed scheme and try to analyze the preformance of $(2, n+1)$ threshold VSS and $(k, n)$ threshold CRT-based SIS.

5.1.   Overview of the proposed scheme

Figure 3 shows the overall process of proposed scheme. The explicit sharing algorithm is illustrated in Algorithm 4 and its matching authentication and recovery algorithm are in Algorithm 5. The grayscale secret image $S$ is the same size as the binary authentication image $S_1$. Without lossing generality, take a secret pixel $S(h, w)$ as an example. Through the above CRTSIS method, it is split into $n$ secret shadow pixels denoted by $SC_1(h, w), SC_2(h, w), \cdots, SC_n(h, w)$. Meanwhile, the pixel $S_1(h, w)$ in the same position as $S(h, w)$ in the binary authentication image is split into $n+1$ binary shadow pixels by the VSS method of $(2, n+1)$ threshold. Among them, the first $n$ binary shadow pixels are used to guide the generation of secret shadow pixels, and the $(n+1)$-th binary shadow pixel is used to generate binary shadow image $S_1C_{n+1}$ for dealer to verify the authenticity of shadows. When there is no dealer, we use the $(2, n)$ threshold VSS method instead. Briefly speaking, there is no need to generate the binary shadow image $S_1C_{n+1}$ for dealer.

Now, we have $n$ grayscale secret shadow pixels ranging from $0$ to $255$ and $n$ binary shadow pixels between $0$ and $1$. Different from using the lowest plane of $n$ secret shadow pixels for screening in Jiang et al. ^[29], for each secret shadow pixel $SC_i(h, w)(i = 1, 2, \cdots, n)$, we transform it as eight bits in binary form. When there exists a dealer, we randomly choose four bits out of eight and get a binary value denoted by $S_2C_i(h, w)$ by doing XOR operation between them. When there is no dealer, all eight bits are used for screening. For convenience, We mark this operation as multi-bit-XOR and denote it by function $ETO$. So we have two binary sequences of n elements, $S_1C_i(h, w)(i = 1, 2, \cdots, n)$ and $S_2C_i(h, w)(i = 1, 2, \cdots, n)$. Here, we use Seq-1 to represent sequence $S_1C_i(h, w)(i = 1, 2, \cdots, n)$ and Seq-2 to represent sequence $S_2C_i(h, w)(i = 1, 2, \cdots, n)$. Finally, in the screening phase, when the amount of 1 in Seq-2 is equal to the amount of 1 in Seq-1, pass screening and $n$ secret shadow pixels $SC_1(h, w), SC_2(h, w), \cdots, SC_n(h, w)$ are assigned to the corresponding positions of $n$ secret shadow images; otherwise, pixel $S(h, w)$ is re-shared with CRTSIS method to obtain new Seq-2 until it passes screening. The sharing phase ends when all pixels of the secret image have been shared.

To be brief, a binary authentication image $S_1$ with the same size as the secret image was divided into $(n+1)$ binary shadows $S_1C_i(i = 1, 2, \cdots, n+1)$ through $(2, n+1)$ VSS. The secret image $S$ was divided into $n$ shadows $SC_i(i = 1, 2, \cdots, n)$ through CRT-based SIS. The first $n$ binary shadows were used to screen out the secret shadows meeting the criteria and the $(n+1)$-th binary shadow was distributed to the dealer to verify the authenticity of secret shadows. When there is no dealer involved, participants verify identities of others mutually.

Regarding Figure 3, we remark that:

$\bullet$ The function $ETO$ converts the grayscale pixel value $SC_i(h, w)$ into the eight-bit binary form, and then gets a binary value $S_2C_i(h, w)$ by doing XOR operation between multiple bits.

$\bullet$ The function $COL$ counts the amount of 1 in the sequence Seq.

Algorithm 4 describes the sharing phase of the proposed scheme for dealer involved. When there is no dealer, take the $(2, n)$-VSS instead and all the eight bits are used for screening.

Algorithm 5 describes the authentication and recovery phase of the proposed scheme. There are two cases here, dealer involved and dealer uninvolved. When there exists a dealer, participants do not know which four bits are used for screening, so they can not forge a fake shadow to pass verification. Dealer collects $k$ (or more) shadows. To save time, dealer carries out restoration phase directly. If the recovery fails, dealer extracts binary authentication shadow $S_2C_1, S_2C_2, \cdots, S_2C_k$ and verifies the authenticity of shadows. Finally the fake shadow is detected and the attacker is located. When there is no dealer, participants trust each other. Since bits used for screening are fixed, participants can calculate binary authentication shadows from the secret shadows they hold. In order to prevent fake participant from stealing secret, participants firstly exchange binary authentication shadows. When the verification passes, participants exchange secret shadows to reconstruct secret, otherwise the fake participant is located and notified.

5.2.   Image quality analysis and security analysis

5.2.1.   Analysis for the quality of recovery image using $(2, n)$ VSS algorithm

According to Algorithm 1, we can theoretically derive the expected quality of recovery image. In order to show the derivation process more clearly and verify the correctness of the derivation, we take $(2, 5)$ threshold as an example. Divide into two cases to discuss when the origin pixel is $0$ or $1$.

When the origin pixel is $0$:

As described in Figure 4, when the origin pixel is $0$, according to Algorithm 1, we have $50 \%$ chance to get the sequence $(0, 0, 0, 0, 0)$, similarly, we have $50 \%$ chance to get another sequence $(1, 1, 1, 1, 1)$. In the recovery phase, we need choose two values from sequence $(0, 0, 0, 0, 0)$ or $(1, 1, 1, 1, 1)$ randomly and do XOR operation between them. Since these two sequences are made of the same elements, we must get the result $0$ in the recovery phase. That is to say the origin pixel $0$ can always be restored losslessly.

When the origin pixel is $1$ :

As shown in Figure 5, when the origin pixel is $1$, according to Algorithm 1, we have $50 \%$ chance to get the sequence $(0, 1, 0, 1, 0)$, similarly, we have $50 \%$ chance to get another sequence $(1, 0, 1, 0, 1)$. For the sequence ($0, 1, 0, 1, 0$), we choose two values randomly and do XOR operation in the recovery phase. If we want to get result $1$, the two values must be different and we can calculate the probability as $\frac{C(3, 1) \times C(2, 1)}{C(5, 2)} = \frac{3}{5}$. On the contrary, the probability we get the result $0$ is $\frac{2}{5}$. And it is the same for the sequence ($1, 0, 1, 0, 1$).

In conclusion, for the $(2, 5)$ threshold, theoretically, we can recover pixel $0$ losslessly and recover pixel $1$ with the probability of $60 \%$.

To verify the conclusion, we did an experiment based on the Algorithm 1 and took the threshold as $(2, 5)$. As demonstrated in the Figure 6, $S_1$ represents the original image and $S^*$ represents the reconstructed image by doing XOR operation between any two of the five shadows. $S_1$ has the size of $128 \times 128$ and consists of $14195$ white pixels and $2189$ black pixels. We use $0$ to represent black pixels and $1$ to represent white pixels. According to the conclusion, the white pixels should be $14195 \times 0.6 = 8517$, and the black pixels should be $2189+14195 \times 0.4 = 7867$ in $S^*$. In the experimental results, the amount of white pixels is $8580$ and for black pixels is $7804$. Considering the uncertainty of random events, the experimental results are consistent with the derived conclusion.

In conclusion, for the origin pixel $0$, we can always recover it losslessly. For the origin pixel $1$, if $n$ is even, let $n = 2t$, then we can get the probability recovering the value correctly as $\frac{C(t, 1) \times C(t, 1)}{C(2t, 2)} = \frac{t}{2t-1}$. Similarly, when $n$ is odd, let $n = 2t+1$, we have the probability as $\frac{C(t, 1) \times C(t+1, 1)}{C(2t+1, 2)} = \frac{t+1}{2t+1}$.

In the proposed scheme, we use $0$ to represent black pixels and $1$ to represent white pixels. The reasons are as follows:

$\bullet$ In general, for a binary image, the secret information is denoted by black, so it is in line with human senses to recover the secret information losslessly.

$\bullet$ The screening times for pixel $0$ are more than those for pixel $1$ in our scheme. And the black pixels of the binary authentication image "hit" are much less than the white pixels in our experiment. Therefore, the use of $0$ to represent black pixel can reduce the times of screening operation to improve generation efficiency. On the contrary, if the authentication image contains more black pixels, we can use $0$ to represent white pixels to improve generation efficiency.

5.2.2.   Security analysis of $(2, n+1)$ threshold VSS and $(k, n)$ threshold CRT-based SIS

In ^[35], we can find the security analysis for $(k, n)$ threshold VSS. And in our scheme, the value of $k$ is fixed at $2$ which is one of the cases in ^[35] and the analysis process is consistent. As for $(k, n)$ threshold CRT-based SIS, we adopt the method CRTSIS proposed in ^[17] which contains the security analysis. However, Okeya et al. ^[34] mention a side channel attack(SCA) which is valid to CRT-based cryptosystems. Since the principle of CRT is the same, our scheme is not resistant to this type of attack. And the security analysis and enhancements will be future work.

6.   Experimental results and analysis

6.1.   Experimental illustration

In the experiment, we select $p = 131$ and $2 \le k \le n \le 5$. Secret image $S$ has the same size of $128 \times 128$ as the binary authentication image $S_1$. Here we introduce the experimental results of $(2, 2)$ threshold and $(3, 4)$ threshold with dealer involved and dealer uninvolved. Figure 7 exhibits the results of $(2, 2)$ threshold. $S$ and $S_1$ represent the grayscale secret image and binary authentication image respectively. $SC_1, SC_2$ denote the secret shadow images calculated by Algorithm 4. $S_1C_3$ represents the binary authentication shadow image for dealer and $S_2C_1, S_2C_2$ denote the binary authentication shadow images calculated from $SC_1, SC_2$ by multi-bit-XOR operation. When there exists a dealer, he$\backslash$she can verify the authenticity of shadows $SC_1, SC_2$. Figure 7 (h), (i) shows the authentication results. When there is no dealer, two participants verify identities mutually. Figure 7 (j) exhibits the authentication result. According to section 5.2.1, it is lossless recovery for pixel $0$ (black area) regardless of the value of $n$. For the pixel $1$ (white area), when there is dealer involved, $n = 3, t = 1$, the probability recovering the pixel $1$ correctly is $\frac{1+1}{2\times1+1} = \frac{2}{3}$; when there is no dealer involved, $n = 2, t = 1$, the probability recovering the pixel $1$ correctly is $\frac{1}{2\times1-1} = 1$. Fig 7 (k) represents the recovered image calculated from $SC_1$ and $SC_2$.

Figure 8 exhibits the results for $(3, 4)$ threshold. Figure 8 (i)-(j) show the authentication results when there exists a dealer. Figure 8 (k) show the authentication result when there is no dealer. Similarly, for the pixel $0$, it can be recovered losslessly. For the pixel $1$, when there is dealer involved, $n = 5, t = 2$, the probability recovering the pixel $1$ correctly is $\frac{2+1}{2\times2+1} = \frac{3}{5}$; when there is no dealer involved, $n = 4, t = 2$, the probability recovering the pixel $1$ correctly is $\frac{2}{2\times2-1} = \frac{2}{3}$. Figure 8 (l) represents the recovered image calculated from $SC_1, SC_2$ and $SC_3$.

6.2.   Analysis for Multi-Bit-XOR for screening

6.2.1.   Efficiency

In the experiment, $p = 131$ and $2 \le k \le n \le 5$, for each set of parameter pairs $(k, n)$, we recorded the screening times and formed Figure 9. As shown in Figure 9, the X-axis represents the amount of bits used for the screening operation. We use symbol $s$ to denote it. In Jiang et al. ^[29], $s = 1$ and in our scheme, $s = 4$ for dealer involved and $s = 8$ for dealer uninvolved. The Y-axis represents the times of screening operation. When $n$ is determined, the times of screening do not change significantly with the increase of $k$. And when $n$ increases, the times of screening increase. More importantly, when the parameter pairs $(k, n)$ is determined, the times of screening do not change significantly with the increase of $s$, that is to say that the efficiency of screening is almost independent of parameter $s$. To be brief, whether $s$ is $1$ or $4$ or $8$ has little impact on the screening efficiency.

6.2.2.   Security

In the experiment, when $k$ is fixed at $2$ and use the lowest bit for screening operation (i.e. $s = 1$), no matter which value $n$ is taken in interval ^[2,5], we find that the secret shadow images reveal the information of binary authentication image $S_1$. More seriously, when the threshold is $(2, 2)$, we can even see the secret information from the secret shadow images. However, when we use the multi-bit-XOR operation for screening(e.g. $s = 8$), secret shadow images do not reveal any information of authentication image or even secret image. As demonstrated in Figure 10, for $s = 1$ and $s = 8$, we enumerate the thresholds $(2, 2)$ and $(2, 3)$ respectively. Figure 10 (c) and Figure 10 (d) reveal both the information of secret image $S$ and authentication image $S_1$ for $(2, 2)$ threshold, $s = 1$. In contrast, while $s = 8$, we cannot derive useful information from Figure 10 (e) and Figure 10 (f). For the threshold $(2, 3)$, it is the same except that the secret shadow images do not reveal secret information. The reason why the information of authentication image is disclosed in the secret shadow images for $k = 2$ can be future work.

On the other hand, if bits used for screening are certain, such as $s = 8$, the participants can extract the binary authentication shadows embedded in secret shadows. However, if the participant is dishonest, he$\backslash$she can easily forge a fake shadow which can pass verification. Therefore, when we can not determine whether all the participants are honest, we need a credible third-party dealer. In this case, the amount of bits used for screening is fixed at 4, but there are $C(8, 4) = 70$ choices, which means that dishonest participant can hardly forge a fake shadow passing verification.

In conclusion, considering both efficiency and security, we adopt multi-bit-XOR operation for screening.

6.3.   Comparison with related works

Yan et al. ^[27], Yang et al. ^[28] and Jiang et al. ^[29] aim to detect fake participants in SIS. Their works are all based on polynomial, and the screening criterion is bitwise comparison. Our scheme is much more efficient in the shadow generation process and the computation complexity of recovery phase is relatively low. We make quantitative comparison with Jiang's work in Figure 11. More detailed comparison can be seen in Table 3.

Jiang et al. ^[29] proposed a SIS method for a $(k, n)$ threshold with dealer-participatory and non-dealer-participatory mutual shadow authentication capabilities which integrates polynomial-based SIS and visual secret sharing through using the result of VSS to guide the polynomial-based SIS by a screening operation. The scheme proposed in ^[29] has no pixel expansion, lossless recovery and a $100\%$ detection rate. However, the execution time of the scheme algorithm is mainly consumed on the screening operation. Figure 11 exhibits the comparison of screening efficiency between Jiang et al. ^[29] and our scheme.

As shown in Figure 11, we can find that the screening efficiency of Jiang et al. ^[29] is much lower than ours. Furthermore, with the increase of $n$, the gap of screening efficiency between the two schemes also increases. Regarding the difference in efficiency between these two schemes, some reasons are listed as below:

$\bullet$ Differences in secret image sharing algorithms. Our scheme is based on Chinese remainder theorem while Jiang et al. ^[29] is based on polynomial.

$\bullet$ Differences in the representation of black and while pixels. In our scheme, we use $0$ to denote black pixel and $1$ to denote while pixel. But it is opposite in Jiang et al. ^[29]. In the experiment, the binary authentication image we use consists of more white pixels than black pixels. However, the fact is that the screening times of pixel $0$ is more than that of pixel $1$ in our scheme.

$\bullet$ Differences in screening criterion. In Jiang et al. ^[29], for one binary authentication sharing shadow sequence $S_1C_1(h, w), S_1C_2(h, w), \cdots, S_1C_n(h, w)$, it requires each element for the corresponding position in the binary secret sharing shadow sequence $S_2C_1(h, w), S_2C_2(h, w), \cdots, S_2C_n(h, w)$ to be equal to it. In other words, screening bit by bit. In contrast, we only need the amount of $1$ in the binary secret sharing shadow sequence be equal to that in binary authentication sharing shadow sequence in our scheme. Take the sequence $(0, 1, 0, 1)$ as an example, in Jiang et al. ^[29] the binary secret sharing shadow sequence must be the same. However, in our scheme, there are $6$ kinds of sequences that meet the screening criterion denoted as $(0, 0, 1, 1), (0, 1, 0, 1), (1, 0, 0, 1), (1, 0, 1, 0), (1, 1, 0, 0)$ and $(0, 1, 1, 0)$. In addition, the two screening criterion are consistent in terms of authentication effectiveness and security.

7.   Conclusions

In this paper, we proposed a verifiable SIS scheme combining $(k, n)$ threshold CRT-based SIS and $(2, n+1)$ threshold VSS. In our scheme, a binary authentication image with the same size as the secret image was divided into $n+1$ binary shadows through $(2, n+1)$ threshold VSS. The first $n$ binary shadows were used to guide the CRT-based SIS and the $(n+1)$-th binary shadow was distributed to dealer to verify the authenticity of secret shadows. When there is no dealer involved, participants verify identities of others mutually. The main contributions of this paper can be summarized as two points. First, compared with the schemes proposed by Yan et al, our scheme utilizes the uncertainty of the bits used for screening to realize not only the detection of fake participants, but also the location of dishonest participants when there is a dealer involved. Sencond, loose screening criterion and efficient encoding and decoding rate of CRT-based SIS guarantee high-efficiency shadows generation and low recovery computation complexity. In addition, our scheme has the advantages of lossless recovery, no pixel expansion and $100\%$ detection rate. We will pay attention to future work as following. First, the theoretical analysis of the leakage of the binary authentication image in secret shadows for $k = 2$. Second, the security analysis of the CRT-based SIS to resist to the side channel attack(SCA) mentioned in ^[34].

Acknowledgements

This work is funded by the Program of the National University of Defense Technology and the National Natural Science Foundation of China (Number: 61602491).

Conflict of interest

The authors declared that they have no conflicts of interest to this work. We declare that we do not have any commercial or associative interest that represents a conflict of interest in connection with the work submitted.