# Efficient Secret Image Sharing Scheme with Authentication and Cheating Prevention

Authors: Lina Zhang; Xuan Dang; Li Feng; Junhan Yang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Due to the widespread adoption and popularity of digital images in distributed storage, Secret Image Sharing (SIS) has attracted much attention. However, preventing the cheating of shares is an important problem that needs to be solved in the traditional SIS scheme. An adversary without image shares may participate in the restoration phase as a share owner. In this phase, the adversary can obtain real shares or prevent recovering real images by submitting fake shadows. Our schemes are based on the original Thien-Lin’s scheme. In the scheme I, we use some XOR operations to get two authentication codes through all secret pixel values to achieve a lightweight and fast-calculated authentication scheme for cheating prevention. This scheme is suitable for small devices with limited resources. In scheme II, we use a hash algorithm to generate the authentication code. This scheme is suitable for environments with larger storage space and higher security levels. Since all pixel values are involved in the authentication in our proposed schemes, it can prevent fake shadow images from cheating. Meanwhile, the shadow size is almost the same as the original Thien-Lin’s scheme. Experimental results and theoretical analysis show that the proposed schemes are feasible and effective.


---

## Body

## 1. Introduction

With the development of computer science and technology, online transactions developed rapidly and improved our daily life. People are increasingly conducting business activities online, and the development prospects of online transactions are very broad [1]. Information security is an important and effective mechanism on the Internet. Information security in transactions has attracted more attention. Some works [2, 3] are all discussing the security of online transactions.Secret sharing is a very important branch in the field of modern cryptography. It provides new ideas for solving the key management of information security. It plays a crucial role in the safe preservation and transmission of secret data. Secret sharing uses an algorithm to divide the secret that needs to be hidden into several shares or subkeys. The shadow image itself is meaningless. However, when the shares reach the thresholdk, the secret can be restored through a certain reconstruction algorithm. On the contrary, if the number of shadows is less than the threshold k, the secret cannot be reconstructed. SIS is an extension of secret sharing technology. When using this technology to share images, the integrity and security of the images can be guaranteed.In practical applications, shadow identity authentication is necessary. The scheme without authentication may have the following deceptions: (1) the dealer cheated. Before the original secret image is restored, the shares of the secret share cannot confirm whether the shadow image they hold can be restored to the original image. Actually, it is assumed that the dealer is trusted. (2) The deception of the secret-sharing members. When a member deliberately sabotages or provides a fake shadow image, other participants will not only be unable to detect it but also regard the wrong secret information as correct. Using this technology to share images can ensure the integrity and security of the images.Currently, there are a variety of SIS schemes. However, they cannot meet the requirements of the users in terms of the quality of reconstructed images, the amount of data in the process of secret distribution, and the security during Internet transmission. Shamir was the first to propose thek,n-threshold secret sharing scheme [4], where n shadow images are generated and distributed to n participants. When there are k shadows or more other shadows, the original secret image can be reconstructed or restored through Lagrange interpolation. Less than k shadows reveal no image information. To obtain better performance, an increasing number of researchers design several polynomial-based SIS schemes [5–7] based on the approach in [4]. In the Thien-Lin k,n secret image sharing scheme [5], the author proposes lossy restoration and lossless restoration. Because the gray value of a pixel is between 0 and 255, and 251 is the greatest prime number not large than 255. In order to apply this scheme, the gray values of the original secret image should be pretreated. Namely, we change all the gray values 251–255 of the original secret image to 250 so that all gray values are in the range 0–250. The work in [7–10] used this lossy processing method. The authors of [10] analyzed the PSNR value between the original secret image and the restored image. This lossy method does not cause visual errors. In lossless restoration, if the pixel value a<250, it is directly processed as a pixel value; otherwise, the pixel value a is divided into 250 and a−250. This lossless method is described in detail in [5]. The processes will slightly increase the size of the shadow image.There are two types of SIS: one is Visual Cryptography (VC) and the other is polynomial-based SIS. The former is directly performed by the human visual system. Some previous studies [11–13] attempt to improve the visual quality and reduce pixel expansion. In addition, some deception problems caused by false shadows with noise have been taken seriously [14, 15]. However, these schemes do not make authentic the shadow image before recovering the secret image, which is very insecure. Progressive VC [16] and multilevel VC [17] can gradually obtain the original secret image through stacking. If the shadow image is not authenticated, the adversary can obtain the relevant secret information through the superposition of less than k shadow images in the front and submit a fake shadow to reconstruct the secret image.The polynomial-based SIS schemes have threshold properties. According to the three modes of multisecret mode, priority mode and progressive mode, a polynomial-based2,n-threshold scalable SIS scheme is constructed [18]. Some studies [19–21] extend 2,n-threshold to the general k,n-threshold scheme based on the approach [18], which is suitable for faster transmission in image distributed systems. Progressive Secret Image Sharing (PSIS) is suitable for multilevel services, which gives different participants different priorities. Nevertheless, the authentication of the shadow image is not considered so that the adversary can tamper or forge shares to participate in the reconstruction of the secret image and steal the secret information. They are applied in the image distribution system due to the threshold characteristics and scalability of the k,n-threshold. Besides, the failure of n−k shadow images in the transmission process will only lose the resolution of the image and will not affect the image reconstruction phase. The work in [22] proposes a novel k,k2 progressive secret image sharing based on modular operations. This method can divide important images stored in the Internet of Things into many parts and then pass them to people in different places. This scheme has fine-grained gradual progress but has certain limitations in threshold setting.In the previous SIS schemes, the thresholdk is determined by the dealer based on the security level. References [7, 9] propose a threshold changeable SIS scheme; each participant only needs to keep one initial shadow. When reconstructing the image, the dealer decides the threshold according to security level. If the threshold is unchanged, any k or more initial shadows can recover the image; else, if the threshold is increased or decreased, the dealer publishes additional information, each participant updates their shadows such that the threshold of updated shadows is changed corresponding. However, this threshold changeable SIS scheme does not consider the authentication of shadow images. If falsified sharing is involved when recovering the secret image, the wrong secret information will be recovered.An increasing number of researchers have proposed SIS schemes with authentication recently. Its purpose is to prevent cheaters from getting real secrets. Many works were proposed to prevent the cheating problem in secret sharing schemes. These schemes can be divided into two categories, cheating detection schemes [8, 10, 23–25] and cheating identification schemes [26, 27]. In the image restoration phase, we need to perform share authentication on the shadow image. A trusted third party calculates the k shadow images used to restore the image block by block, and the calculated value is compared with the authentication code. If they are equal, the authentication is passed and the original image is restored. Otherwise, there is a fake shadow image. The trusted third party stops recovering. The study in [26] proposes an independent shadow authentication scheme based on SIS, which applies visual secret sharing to polynomial-based SIS. In the sharing phase, the users input a binary authentication image and a shared secret image to the dealer. In the restoration phase, participants use stacking or XOR operations for identity authentication by sending the lowest plane of the shadow. The work in [27] proposes two mutual shadow authentication functions with dealer participation and nondealer participation. All participants and dealers can mutually authenticate other participants. Both of these methods have low complexity, and there is no need to separately consider shadow authentication capabilities.In cheating detection schemes, honest users can detect the cheating behaviour but cannot identify cheaters. The work in [10] is based on the Thien-Lin scheme and the intractability of the discrete logarithm. It can identify the cheaters no matter if the original secret image holder or the participants. No security channel exists between the holder and the participants. Reference [23] demonstrates that Shamir scheme is not secure against cheating. The work in [24] is based on [23], which makes relevant theoretical derivations for secret sharing schemes to prevent such attacks. Reference [25] discusses the significance of detecting cheating in linear secret sharing schemes and constructs a new k,n linear secret sharing scheme with the capability of cheating detection. In the phase of cheating detection, only one honest player can detect the cheating from other k−1 cheaters, which achieves a stronger detection effectiveness than the previous linear secret sharing schemes against cheating.Besides, the SIS schemes based on polynomial information hiding are also widely researched. The work in [8] proposes a new scheme to share secret images by constructing two polynomials, using the first two pixels values of the first polynomial to construct two secret authentication codes and embed them into the second polynomial to detect the existence of deception. In the restoration phase, only some pixel values participate in the authentication. In this way, the cheater can tamper with pixel values that are not involved in authentication, and the security level is low. However, the size of the shadow is almost the same as the original k,n secret image sharing scheme.This shows that information security is essential in online transactions. If the identity of the participant is not verified before the transaction, malicious attacks such as secret disclosure may occur. On the one hand, if an adversary without a share can obtain the share of other normal users through deception in online transactions, it is not safe. If there is no reliable third-party identity authentication, all shares can be sent to each other, and the adversary may obtain secret information through forgery and tampering. On the other hand, when the amount of image restoration is huge, if the detection is not performed first, it will cost time, manpower, and material resources.


### 1.1. Our Contribution

In this paper, the shadow authentication of the image sharing is taken into account in the image restoration phase. Our contributions are as follows:(1)
Based on the knowledge of cryptography, we propose two SIS schemes that can cheating prevention. Scheme I processesk−2 pixel values at a time and constructs two authentication codes. This scheme uses XOR operation, so it is suitable for Internet chips or some resource-constrained, embedded devices.(2)
The scheme II has a further improvement in security. It uses related cryptographic algorithms to construct an authentication code through a hash algorithm. Despite its high storage and efficiency, it is suitable for environments and devices with larger storage space and higher security levels. The shadow size of this scheme is similar to that of Thien-Lin’s scheme.(3)
In the authentication process of the shadow images, all pixels of the secret image participate in the authentication. It is obvious that it can prevent the shadow images from being tampered with and greatly improve security.


### 1.2. Organization

The rest of the paper is organized as follows: in Section2, we focus on some preliminary knowledge related to the proposed schemes; in Section 3, we propose two SIS schemes for detecting deception and analyze their performance; in Section 4, experimental results and security analysis are used to show the performance of proposed scheme and comparisons of shadow size; the conclusion part is in Section 5.


## 1.1. Our Contribution

In this paper, the shadow authentication of the image sharing is taken into account in the image restoration phase. Our contributions are as follows:(1)
Based on the knowledge of cryptography, we propose two SIS schemes that can cheating prevention. Scheme I processesk−2 pixel values at a time and constructs two authentication codes. This scheme uses XOR operation, so it is suitable for Internet chips or some resource-constrained, embedded devices.(2)
The scheme II has a further improvement in security. It uses related cryptographic algorithms to construct an authentication code through a hash algorithm. Despite its high storage and efficiency, it is suitable for environments and devices with larger storage space and higher security levels. The shadow size of this scheme is similar to that of Thien-Lin’s scheme.(3)
In the authentication process of the shadow images, all pixels of the secret image participate in the authentication. It is obvious that it can prevent the shadow images from being tampered with and greatly improve security.


## 1.2. Organization

The rest of the paper is organized as follows: in Section2, we focus on some preliminary knowledge related to the proposed schemes; in Section 3, we propose two SIS schemes for detecting deception and analyze their performance; in Section 4, experimental results and security analysis are used to show the performance of proposed scheme and comparisons of shadow size; the conclusion part is in Section 5.


## 2. Preliminaries

The idea of secret sharing was first proposed by Shamir [4]. The main idea is to divide data S into shares in such a way that it is easily reconstructed from any k shares, and complete knowledge of k−1 shares reveals absolutely no information about S. In [4], a Lagrange interpolation polynomial needs to be constructed. Then, let the secret data S be a constant term of the polynomial. From the polynomial, n values can be calculated as n shares, where any k shares can recover S. Later, this idea was followed by many research scholars, such as these schemes [5, 28–30]. The approach in [5] proposes a SIS scheme based on Shamir’s threshold secret sharing method. The difference between [5] and [4] is that Thien-Lin group image pixels, each group of pixels, are used as polynomial coefficients. At present, many works [8, 31] including our proposed scheme, are based on Thien-Lin’s scheme. Next, we introduce the whole process of the two classic schemes and discuss the schemes.


### 2.1. Polynomial-Based SIS

In [5], Thien-Lin proposed k,n–SIS scheme based on interpolated polynomial. This scheme consists of two phases: the Shadow generation phase and the image restoration phase. In the shadow generation phase, a dealer takes a secret image I as input and invokes an algorithm to output n shadows. During the image restoration phase, a set of m shadows k≤m≤n is capable of recover the secret image I.


#### 2.1.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into nonoverlapping t pixel blocks P1,P2,…,Pt. Each pixel block contains k pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−1.Step 3: construct ak−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−1xk−1.Step 4: for each pixel blockPi,i∈1,t, use the formula in step 3 to calculate the subshadow Oi,j=fij,j∈1,n, and distribute it to different participants—the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


#### 2.1.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,⋯,Sk from Sj,j∈1,nStep 2: use the Lagrange interpolation to calculate the secret pixel valuesai,0,ai,1,…,ai,k−1Step 3: the pixel blockPi=ai,0,ai,1,…,ai,k−1 is restored, and the original secret image I=P1‖P2‖⋯‖Pt is further restoredThis scheme clearly illustrates the nature of the thresholdk: k or more shadows can reconstruct or recover the original secret image, and less than k shadows reveal no image information. The shadow size is 1/k of that of the original image.


### 2.2. SIS Scheme with Deception Detection

The work in [8] proposes a k,n-SIS scheme with deception detection by constructing two secret authentication codes to mosaic the second polynomial through the first two pixels values of the first polynomial to detect the existence of deception.


#### 2.2.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains 2k−2 pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−1 and bi,2,bi,3,…,bi,k−1. Then, we construct a k−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−1xk−1mod251Step 3: the dealer randomly selects an integerri and calculates two secret authentication codes bi,0,bi,1 through formulas ri⋅ai,0+bi,0=0mod251 and ri⋅ai,1+bi,1=0mod251 . Then, we constructing another k−1 degree polynomial gix=bi,0+bi,1x+⋯+bi,k−1xk−1mod251 .Step 4: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij,gij using two polynomials and distribute the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n to different participants.


#### 2.2.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,…,Sk from Sj,j∈1,n.Step 2: Lagrange interpolation is used to reconstruct the polynomial for each subshadowOi,j. The calculated values ai,0,ai,1,…,ai,k−1,bi,0,bi,1,…,bi,k−1 are used as the coefficients of the two polynomials.Step 3: if there is an integerri that satisfies ri⋅ai,0+bi,0=0mod251, ri⋅ai,1+bi,1=0mod251 , then the pixel block Pi=ai,0,ai,1,…,ai,k−1,bi,2,bi,3,…,bi,k−1 can be restored. Finally, the original secret image I=P1‖P2‖⋯‖Pt can be further restored. Otherwise, it can be concluded that there exist false shadows participating in the image restoration.It can be observed from this scheme that the authentication for detecting fraud must be performed before the restoration phase. If a false shadow is detected, the restoration of the original secret image should be stopped. The shadow size in this scheme is1/k−1 of that of the original image.


## 2.1. Polynomial-Based SIS

In [5], Thien-Lin proposed k,n–SIS scheme based on interpolated polynomial. This scheme consists of two phases: the Shadow generation phase and the image restoration phase. In the shadow generation phase, a dealer takes a secret image I as input and invokes an algorithm to output n shadows. During the image restoration phase, a set of m shadows k≤m≤n is capable of recover the secret image I.


### 2.1.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into nonoverlapping t pixel blocks P1,P2,…,Pt. Each pixel block contains k pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−1.Step 3: construct ak−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−1xk−1.Step 4: for each pixel blockPi,i∈1,t, use the formula in step 3 to calculate the subshadow Oi,j=fij,j∈1,n, and distribute it to different participants—the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


### 2.1.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,⋯,Sk from Sj,j∈1,nStep 2: use the Lagrange interpolation to calculate the secret pixel valuesai,0,ai,1,…,ai,k−1Step 3: the pixel blockPi=ai,0,ai,1,…,ai,k−1 is restored, and the original secret image I=P1‖P2‖⋯‖Pt is further restoredThis scheme clearly illustrates the nature of the thresholdk: k or more shadows can reconstruct or recover the original secret image, and less than k shadows reveal no image information. The shadow size is 1/k of that of the original image.


## 2.1.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into nonoverlapping t pixel blocks P1,P2,…,Pt. Each pixel block contains k pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−1.Step 3: construct ak−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−1xk−1.Step 4: for each pixel blockPi,i∈1,t, use the formula in step 3 to calculate the subshadow Oi,j=fij,j∈1,n, and distribute it to different participants—the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


## 2.1.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,⋯,Sk from Sj,j∈1,nStep 2: use the Lagrange interpolation to calculate the secret pixel valuesai,0,ai,1,…,ai,k−1Step 3: the pixel blockPi=ai,0,ai,1,…,ai,k−1 is restored, and the original secret image I=P1‖P2‖⋯‖Pt is further restoredThis scheme clearly illustrates the nature of the thresholdk: k or more shadows can reconstruct or recover the original secret image, and less than k shadows reveal no image information. The shadow size is 1/k of that of the original image.


## 2.2. SIS Scheme with Deception Detection

The work in [8] proposes a k,n-SIS scheme with deception detection by constructing two secret authentication codes to mosaic the second polynomial through the first two pixels values of the first polynomial to detect the existence of deception.


### 2.2.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains 2k−2 pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−1 and bi,2,bi,3,…,bi,k−1. Then, we construct a k−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−1xk−1mod251Step 3: the dealer randomly selects an integerri and calculates two secret authentication codes bi,0,bi,1 through formulas ri⋅ai,0+bi,0=0mod251 and ri⋅ai,1+bi,1=0mod251 . Then, we constructing another k−1 degree polynomial gix=bi,0+bi,1x+⋯+bi,k−1xk−1mod251 .Step 4: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij,gij using two polynomials and distribute the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n to different participants.


### 2.2.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,…,Sk from Sj,j∈1,n.Step 2: Lagrange interpolation is used to reconstruct the polynomial for each subshadowOi,j. The calculated values ai,0,ai,1,…,ai,k−1,bi,0,bi,1,…,bi,k−1 are used as the coefficients of the two polynomials.Step 3: if there is an integerri that satisfies ri⋅ai,0+bi,0=0mod251, ri⋅ai,1+bi,1=0mod251 , then the pixel block Pi=ai,0,ai,1,…,ai,k−1,bi,2,bi,3,…,bi,k−1 can be restored. Finally, the original secret image I=P1‖P2‖⋯‖Pt can be further restored. Otherwise, it can be concluded that there exist false shadows participating in the image restoration.It can be observed from this scheme that the authentication for detecting fraud must be performed before the restoration phase. If a false shadow is detected, the restoration of the original secret image should be stopped. The shadow size in this scheme is1/k−1 of that of the original image.


## 2.2.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains 2k−2 pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−1 and bi,2,bi,3,…,bi,k−1. Then, we construct a k−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−1xk−1mod251Step 3: the dealer randomly selects an integerri and calculates two secret authentication codes bi,0,bi,1 through formulas ri⋅ai,0+bi,0=0mod251 and ri⋅ai,1+bi,1=0mod251 . Then, we constructing another k−1 degree polynomial gix=bi,0+bi,1x+⋯+bi,k−1xk−1mod251 .Step 4: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij,gij using two polynomials and distribute the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n to different participants.


## 2.2.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,…,Sk from Sj,j∈1,n.Step 2: Lagrange interpolation is used to reconstruct the polynomial for each subshadowOi,j. The calculated values ai,0,ai,1,…,ai,k−1,bi,0,bi,1,…,bi,k−1 are used as the coefficients of the two polynomials.Step 3: if there is an integerri that satisfies ri⋅ai,0+bi,0=0mod251, ri⋅ai,1+bi,1=0mod251 , then the pixel block Pi=ai,0,ai,1,…,ai,k−1,bi,2,bi,3,…,bi,k−1 can be restored. Finally, the original secret image I=P1‖P2‖⋯‖Pt can be further restored. Otherwise, it can be concluded that there exist false shadows participating in the image restoration.It can be observed from this scheme that the authentication for detecting fraud must be performed before the restoration phase. If a false shadow is detected, the restoration of the original secret image should be stopped. The shadow size in this scheme is1/k−1 of that of the original image.


## 3. The Proposed Scheme

SIS technology has matured and increasing researchers are beginning to pay attention to the security of the sharing phase, which is the shadow authentication in the image restoration phase. The approach in [8] is to share the secret image by constructing two polynomials. This method increases the storage space. In the restoration phase, only the first two pixels participate in the authentication. We propose two new schemes based on that, where all pixel values participate in the authentication. Besides, only one polynomial is used to calculate the shadow image, which reduces the storage space. SchemeIis a completely lightweight and fast calculation. SchemeIIuses a cryptographic hash algorithm, although it is slightly lower in efficiency but has a higher level of security. Compared with schemeI, schemeIIhas a further improvement in security. SchemeIIuses related cryptographic algorithms to construct an authentication code for authentication through a hash algorithm. Although it is slightly higher in storage and efficiency, it is suitable for environments and equipment with larger storage space and a higher level of security.


### 3.1. The Proposed SchemeI

Since schemeIonly uses the XOR operation, it is a lightweight and fast operation scheme. SchemeItakesk−2 pixel values as a block and calculates two authentication codes for each block, thereby constructing a k−1 degree polynomial to calculate the shadow image. When the image is restored, by judging whether it conforms to the formula of the exclusive XOR operation to obtain the authentication code, it is further detected whether there is a false shadow. If the authentication is successful, the original secret image can be recovered. Else, there are fake shadows participating in image reconstruction; the cheating prevented.


#### 3.1.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains k−2 pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−3.Step 3: XOR operation in equation (1) is used to generate two authentication codes bi,0,bi,1. Then, we construct a k−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−3xk−3+bi,0xk−2+bi,1xk−1mod251 .(1)bi,0=ai,0⊕ai,1⊕⋯⊕ai,k−4mod251,bi,1=ai,1⊕ai,2⊕⋯⊕ai,k−3mod251.Step 4: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij and distribute it to different participants. The final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


#### 3.1.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,⋯,Sk from Sj,j∈1,n.Step 2: use the Lagrange interpolation formula to calculate the secret pixel valuesai,0′,ai,1′,…,ai,k−2′ and bi,0′,bi,1′.Step 3: detect whether there exist fake shadows. If these valuesai,0′,ai,1′,…,ai,k−3′ and bi,0′,bi,1′ satisfy equation (2), the pixel block Pi'=ai,0′,ai,1′,…,ai,k−3′ can be restored. Finally, the original secret image I′=P1′‖P2′‖⋯‖Pt′ can be further restored.(2)ai,0′⊕ai,1′⊕⋯⊕ai,k−4′mod251=bi,0′,ai,1′⊕ai,2′⊕⋯⊕ai,k−3′mod251=bi,1′.Else, it can be detected that fake shadows participate in the reconstruction of the secret image. Thus, the cheating was prevented.SchemeIonly uses very lightweight operations and is suitable for Internet chips or embedded devices with limited resources. For schemeI, we have the following instructions:(a)
Our scheme processesk−2 pixel values at a time. The first k−3 pixel values and the last k−3 pixel values are used to construct two secret authentication codes bi,1′,bi,2′ participating in the authentication of the shadow image.(b)
In this scheme, the threshold should satisfyk−3≥1, namely k≥4.(c)
The shadow size is1/k−2 of that of the original image.The polynomial constructed in scheme 1 processesk−2 secret pixel values at a time, and the size of the shadow image is 1/k−2 of the original secret image. The authentication code is generated by XOR the first k−3 and the last k−3 secret pixel values for authentication. Obviously, k−3≥1, which means k≥4. This scheme selects two authentication codes, and the number of polynomial coefficients is k, which is limited. More locations must be used to store secret pixel values. If a larger number of authentication codes are selected, the number of secret pixel values processed each time will be reduced, which will cause the shadow image to become larger. In addition, without knowing any secret information, the probability of an adversary guessing one authentication code is 1/28, and the probability of guessing both authentication codes is 1/216.


### 3.2. The Proposed SchemeII

SchemeIItakesk−1 pixel values as a block and uses a cryptographic hash algorithm to generate an authentication code. In the image restoration phase, it is determined whether the authentication codes are equal. If the authentication is successful, the original secret image can be restored. Else, there are fake shadows participating in image reconstruction; the cheating was prevented. Although this scheme is slightly less efficient, it has higher security.


#### 3.2.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains k−1 pixel values.Step 2: the pixel valuesai,0,ai,1,…,ai,k−2 in each pixel block Pi,i∈1,t constitute a message sequence Mi in the following equation:(3)Mi=ai,0ai,1⋯ai,k−2.Step 3: the generation of authentication code. For each message sequenceMi, we use a hash function to generate a message digest with a fixed bit length. In this scheme, we use the MD5 algorithm. For the 128-bit hash value generated by the MD5 algorithm, perform a bit-by-bit XOR on every 16 bit to obtain a value of 1 bit. There is a total of 8-bit value bi as the authentication code.Step 4: construct ak−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−2xk−2+bixk−1mod251Step 5: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij and distribute it to different participants—the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


#### 3.2.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1′,S2′,…,Sk′ from Sj,j∈1,n.Step 2: calculate the multireality coefficientsai,0′,ai,1′,…,ai,k−2′ and bi′ through the Lagrange interpolation polynomial.Step 3: use step 2 and step 3 in the shadow generation phase to calculate and generate the authentication codebi″ for ai,0′,ai,1′,…,ai,k−2′.Step 4: detect whether there exist fake shadows. Ifbi″=bi′, the pixel block Pi′=ai,0′,ai,1′,…,ai,k−2′ can be restored, and the original secret image I′=P1′‖P1′‖⋯‖Pt′ can be further restored. Else, it can be detected that fake shadows participate in the reconstruction of the secret image. Thus, the cheating was prevented.For scheme II, we have the following instructions:(a)
There are several kinds of hash functions, such as MD5, SHA1, SHA256, etc. All of them encrypt messages of any bit length to generate fixed bit length message digests.(b)
The shadow size is1/k−1 of that of the original image.Obviously, the size of the shadow image in scheme I is1/k−2, but the size of the shadow image in schemeIIis 1/k−1. SchemeIuses a simple XOR operation and schemeIIuses a slightly more complicated hash algorithm. It is the lightest operation in cryptography, far smaller than the basic passwords such as modular multiplication and modular exponentiation. Relative to these, it can be ignored. It can be said that schemeIIis a very efficient and lightweight algorithm. Compared with schemeI, scheme II has a further improvement in security. Although it is slightly higher in storage and efficiency, it is suitable for environments and equipment with larger storage space and a higher level of security.


## 3.1. The Proposed SchemeI

Since schemeIonly uses the XOR operation, it is a lightweight and fast operation scheme. SchemeItakesk−2 pixel values as a block and calculates two authentication codes for each block, thereby constructing a k−1 degree polynomial to calculate the shadow image. When the image is restored, by judging whether it conforms to the formula of the exclusive XOR operation to obtain the authentication code, it is further detected whether there is a false shadow. If the authentication is successful, the original secret image can be recovered. Else, there are fake shadows participating in image reconstruction; the cheating prevented.


### 3.1.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains k−2 pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−3.Step 3: XOR operation in equation (1) is used to generate two authentication codes bi,0,bi,1. Then, we construct a k−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−3xk−3+bi,0xk−2+bi,1xk−1mod251 .(1)bi,0=ai,0⊕ai,1⊕⋯⊕ai,k−4mod251,bi,1=ai,1⊕ai,2⊕⋯⊕ai,k−3mod251.Step 4: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij and distribute it to different participants. The final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


### 3.1.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,⋯,Sk from Sj,j∈1,n.Step 2: use the Lagrange interpolation formula to calculate the secret pixel valuesai,0′,ai,1′,…,ai,k−2′ and bi,0′,bi,1′.Step 3: detect whether there exist fake shadows. If these valuesai,0′,ai,1′,…,ai,k−3′ and bi,0′,bi,1′ satisfy equation (2), the pixel block Pi'=ai,0′,ai,1′,…,ai,k−3′ can be restored. Finally, the original secret image I′=P1′‖P2′‖⋯‖Pt′ can be further restored.(2)ai,0′⊕ai,1′⊕⋯⊕ai,k−4′mod251=bi,0′,ai,1′⊕ai,2′⊕⋯⊕ai,k−3′mod251=bi,1′.Else, it can be detected that fake shadows participate in the reconstruction of the secret image. Thus, the cheating was prevented.SchemeIonly uses very lightweight operations and is suitable for Internet chips or embedded devices with limited resources. For schemeI, we have the following instructions:(a)
Our scheme processesk−2 pixel values at a time. The first k−3 pixel values and the last k−3 pixel values are used to construct two secret authentication codes bi,1′,bi,2′ participating in the authentication of the shadow image.(b)
In this scheme, the threshold should satisfyk−3≥1, namely k≥4.(c)
The shadow size is1/k−2 of that of the original image.The polynomial constructed in scheme 1 processesk−2 secret pixel values at a time, and the size of the shadow image is 1/k−2 of the original secret image. The authentication code is generated by XOR the first k−3 and the last k−3 secret pixel values for authentication. Obviously, k−3≥1, which means k≥4. This scheme selects two authentication codes, and the number of polynomial coefficients is k, which is limited. More locations must be used to store secret pixel values. If a larger number of authentication codes are selected, the number of secret pixel values processed each time will be reduced, which will cause the shadow image to become larger. In addition, without knowing any secret information, the probability of an adversary guessing one authentication code is 1/28, and the probability of guessing both authentication codes is 1/216.


## 3.1.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains k−2 pixel values.Step 2: the pixel values in each pixel blockPi,i∈1,t are ai,0,ai,1,…,ai,k−3.Step 3: XOR operation in equation (1) is used to generate two authentication codes bi,0,bi,1. Then, we construct a k−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−3xk−3+bi,0xk−2+bi,1xk−1mod251 .(1)bi,0=ai,0⊕ai,1⊕⋯⊕ai,k−4mod251,bi,1=ai,1⊕ai,2⊕⋯⊕ai,k−3mod251.Step 4: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij and distribute it to different participants. The final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


## 3.1.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1,S2,⋯,Sk from Sj,j∈1,n.Step 2: use the Lagrange interpolation formula to calculate the secret pixel valuesai,0′,ai,1′,…,ai,k−2′ and bi,0′,bi,1′.Step 3: detect whether there exist fake shadows. If these valuesai,0′,ai,1′,…,ai,k−3′ and bi,0′,bi,1′ satisfy equation (2), the pixel block Pi'=ai,0′,ai,1′,…,ai,k−3′ can be restored. Finally, the original secret image I′=P1′‖P2′‖⋯‖Pt′ can be further restored.(2)ai,0′⊕ai,1′⊕⋯⊕ai,k−4′mod251=bi,0′,ai,1′⊕ai,2′⊕⋯⊕ai,k−3′mod251=bi,1′.Else, it can be detected that fake shadows participate in the reconstruction of the secret image. Thus, the cheating was prevented.SchemeIonly uses very lightweight operations and is suitable for Internet chips or embedded devices with limited resources. For schemeI, we have the following instructions:(a)
Our scheme processesk−2 pixel values at a time. The first k−3 pixel values and the last k−3 pixel values are used to construct two secret authentication codes bi,1′,bi,2′ participating in the authentication of the shadow image.(b)
In this scheme, the threshold should satisfyk−3≥1, namely k≥4.(c)
The shadow size is1/k−2 of that of the original image.The polynomial constructed in scheme 1 processesk−2 secret pixel values at a time, and the size of the shadow image is 1/k−2 of the original secret image. The authentication code is generated by XOR the first k−3 and the last k−3 secret pixel values for authentication. Obviously, k−3≥1, which means k≥4. This scheme selects two authentication codes, and the number of polynomial coefficients is k, which is limited. More locations must be used to store secret pixel values. If a larger number of authentication codes are selected, the number of secret pixel values processed each time will be reduced, which will cause the shadow image to become larger. In addition, without knowing any secret information, the probability of an adversary guessing one authentication code is 1/28, and the probability of guessing both authentication codes is 1/216.


## 3.2. The Proposed SchemeII

SchemeIItakesk−1 pixel values as a block and uses a cryptographic hash algorithm to generate an authentication code. In the image restoration phase, it is determined whether the authentication codes are equal. If the authentication is successful, the original secret image can be restored. Else, there are fake shadows participating in image reconstruction; the cheating was prevented. Although this scheme is slightly less efficient, it has higher security.


### 3.2.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains k−1 pixel values.Step 2: the pixel valuesai,0,ai,1,…,ai,k−2 in each pixel block Pi,i∈1,t constitute a message sequence Mi in the following equation:(3)Mi=ai,0ai,1⋯ai,k−2.Step 3: the generation of authentication code. For each message sequenceMi, we use a hash function to generate a message digest with a fixed bit length. In this scheme, we use the MD5 algorithm. For the 128-bit hash value generated by the MD5 algorithm, perform a bit-by-bit XOR on every 16 bit to obtain a value of 1 bit. There is a total of 8-bit value bi as the authentication code.Step 4: construct ak−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−2xk−2+bixk−1mod251Step 5: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij and distribute it to different participants—the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


### 3.2.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1′,S2′,…,Sk′ from Sj,j∈1,n.Step 2: calculate the multireality coefficientsai,0′,ai,1′,…,ai,k−2′ and bi′ through the Lagrange interpolation polynomial.Step 3: use step 2 and step 3 in the shadow generation phase to calculate and generate the authentication codebi″ for ai,0′,ai,1′,…,ai,k−2′.Step 4: detect whether there exist fake shadows. Ifbi″=bi′, the pixel block Pi′=ai,0′,ai,1′,…,ai,k−2′ can be restored, and the original secret image I′=P1′‖P1′‖⋯‖Pt′ can be further restored. Else, it can be detected that fake shadows participate in the reconstruction of the secret image. Thus, the cheating was prevented.For scheme II, we have the following instructions:(a)
There are several kinds of hash functions, such as MD5, SHA1, SHA256, etc. All of them encrypt messages of any bit length to generate fixed bit length message digests.(b)
The shadow size is1/k−1 of that of the original image.Obviously, the size of the shadow image in scheme I is1/k−2, but the size of the shadow image in schemeIIis 1/k−1. SchemeIuses a simple XOR operation and schemeIIuses a slightly more complicated hash algorithm. It is the lightest operation in cryptography, far smaller than the basic passwords such as modular multiplication and modular exponentiation. Relative to these, it can be ignored. It can be said that schemeIIis a very efficient and lightweight algorithm. Compared with schemeI, scheme II has a further improvement in security. Although it is slightly higher in storage and efficiency, it is suitable for environments and equipment with larger storage space and a higher level of security.


## 3.2.1. Shadow Generation Phase

Input a secret imageI, output n shadow image S1,S2,…,Sn.Step 1: the dealer divides the secret imageI into t nonoverlapping pixel blocks P1,P2,…,Pt. Each pixel block contains k−1 pixel values.Step 2: the pixel valuesai,0,ai,1,…,ai,k−2 in each pixel block Pi,i∈1,t constitute a message sequence Mi in the following equation:(3)Mi=ai,0ai,1⋯ai,k−2.Step 3: the generation of authentication code. For each message sequenceMi, we use a hash function to generate a message digest with a fixed bit length. In this scheme, we use the MD5 algorithm. For the 128-bit hash value generated by the MD5 algorithm, perform a bit-by-bit XOR on every 16 bit to obtain a value of 1 bit. There is a total of 8-bit value bi as the authentication code.Step 4: construct ak−1 degree polynomial fix=ai,0+ai,1x+⋯+ai,k−2xk−2+bixk−1mod251Step 5: for each pixel blockPi,i∈1,t, we calculate the subshadow Oi,j=fij and distribute it to different participants—the final shadow Sj=O1,j‖O2,j‖⋯‖Ot,j,j∈1,n.


## 3.2.2. Image Restoration Phase

Inputk shadow images and output the original secret image I.Step 1: selectk shadows S1′,S2′,…,Sk′ from Sj,j∈1,n.Step 2: calculate the multireality coefficientsai,0′,ai,1′,…,ai,k−2′ and bi′ through the Lagrange interpolation polynomial.Step 3: use step 2 and step 3 in the shadow generation phase to calculate and generate the authentication codebi″ for ai,0′,ai,1′,…,ai,k−2′.Step 4: detect whether there exist fake shadows. Ifbi″=bi′, the pixel block Pi′=ai,0′,ai,1′,…,ai,k−2′ can be restored, and the original secret image I′=P1′‖P1′‖⋯‖Pt′ can be further restored. Else, it can be detected that fake shadows participate in the reconstruction of the secret image. Thus, the cheating was prevented.For scheme II, we have the following instructions:(a)
There are several kinds of hash functions, such as MD5, SHA1, SHA256, etc. All of them encrypt messages of any bit length to generate fixed bit length message digests.(b)
The shadow size is1/k−1 of that of the original image.Obviously, the size of the shadow image in scheme I is1/k−2, but the size of the shadow image in schemeIIis 1/k−1. SchemeIuses a simple XOR operation and schemeIIuses a slightly more complicated hash algorithm. It is the lightest operation in cryptography, far smaller than the basic passwords such as modular multiplication and modular exponentiation. Relative to these, it can be ignored. It can be said that schemeIIis a very efficient and lightweight algorithm. Compared with schemeI, scheme II has a further improvement in security. Although it is slightly higher in storage and efficiency, it is suitable for environments and equipment with larger storage space and a higher level of security.


## 4. Experiment Results and Analysis

### 4.1. Experiment Results

In this section, we use two experiments to illustrate the proposed schemes in this paper.For schemeI, we let the thresholdk,n=5,6, then each pixel block contains three pixels values. Supposing the first pixel blocks P1=57,121,90, the dealer calculates the secret authentication codes b0=57⊕121=64,b1=121⊕90=35. Then, we construct k−1=4 degree polynomial fx=57+121x+90x2+64x3+35x4mod251. Finally, we calculate the six shadows:S1=f1=116,S2=f2=225S3=f3=20S4=f4=228,S5=f5=157S6=f6=206. In the restoration phase, we choose five shadows, namely S1,S2, S3,S4,S5 to reconstruct the secret image. Suppose we forge a false shadow S1′=110 and then select S2′,S3′,S4′,S5′. Next, we generate the polynomial fx′=27+34x+135x2+193x3+223x4 through the Lagrange interpolation function. Here, b0′=193,b1′=223. Since 27⊕34=57≠b0′,34⊕135=165≠b1′, so we can successfully detect there exists fake shadow and the cheating prevented. We take 5,6-threshold scheme to test the proposed schemeI, the test image is the well-known image “Lena.” The goal is that any five out of six shadow images can be used for image reconstruction. The corresponding experimental results are shown in Figure 1.Figure 1
Experiment 1 results: (a) an original secret image; (b) the reconstructed image; (c–h) the six shadow images.
(a)(b)(c)(d)(e)(f)(g)(h)In Figure1, (a) shows the original secret image, its size is 256×256; (b) is the reconstructed image by using the Lagrange interpolating polynomial and the five shadow images chosen randomly (we choose the first five shadow images to reconstruct the original secret image); (c–h) are the shadow images, and the sizes of the six shadow images are 256×256/k−2.For scheme II, we let the thresholdk,n=4,6, then each pixel block contains three pixels values. Supposing that the first pixel block P1=57,121,90, we generate a 128-bit message digest M1 through the Md5 algorithm. Next, perform a bit-by-bit XOR on every 16 bit to obtain a value of 1 bit. There is a total of 8-bit value as the secret authentication code b=10100001=161. Next, we construct a k−1=3 degree polynomial fx=57+68x+90x2+161x3mod251. Finally, we calculate the six shadows: S1=f1=178S2=f2=190S3=f3=55S4=f4=237S5=f5=196S6=f6=145. In the restoration phase, we choose four shadows to reconstruct the secret image. Suppose that we forge a fake shadow S1′=177 and then select S2′,S3′,S4′. Next, we calculate the polynomial fx′=53+209x+214x2+203x3 through the Lagrange interpolation function. Here, b′=203. We use the same MD5 algorithm to calculate the authentication message digest b″=30 for P1′=53,209,214. Since b″≠b′, so we can successfully detect the presence of deception and cheating prevention. We take 4,6-threshold scheme to test the proposed scheme II. The goal is that any four out of six shadow images can be used for image reconstruction. The corresponding experimental results are shown in Figure 2.Figure 2
Experiment 2 results: (a) the original secret image; (b) the reconstructed image; (c–h) the six shadow images.
(a)(b)(c)(d)(e)(f)(g)(h)In Figure2, (a) shows the original secret image, its size is 256×256; (b) is the reconstructed image by using the Lagrange interpolating polynomial and the four shadow images chosen randomly (we choose the first four shadow images to reconstruct the original secret image); (c–h) are the shadow images, and the sizes of the six shadow images are 256×256/k−1 (here k=4).Figure3 shows the experimental results of the other two typical pictures. Through the histogram, we can clearly find that the pixel values in image “Rice” are all less than 250, and the restored image is lossless. In image “Landscape,” there are pixel values greater than 250, so the restored image is lossy. Visually, there is not much difference.Figure 3
The experiment for other images: (a) the secret image of Rice; (b) the histogram of Rice; (c) the reconstructed image of Rice; (d) the secret image of Landscape; (e) the histogram of Landscape; (f) the reconstructed image of Landscape.
(a)(b)(c)(d)(e)(f)


### 4.2. Performance Analysis

Normally, the shadow size is an important factor in evaluating the performance of an SIS scheme, since a smaller size has lower storage and transmission costs. Table1 shows the comparisons between our scheme and other related schemes.Table 1
Comparisons with the related scheme.
The schemeTechnologyThe shadow sizeEvery pixel value participates in certificationPrevent cheatingScheme in [26]SISIYesYesScheme in [27]SISIYesYesScheme in [8]Information hiding1/k−1INoNoOur proposed scheme IInformation hiding1/k−2IYesYesOur proposed scheme IIInformation hiding1/k−1IYesYesThe scheme in [26] is based on the SIS. The visual secret sharing is applied to the polynomial-based SIS, and the shadows can be mutually authenticated by exchanging the lowest plane. This scheme has low complexity of shadow generation and authentication. However, the shadow image is larger, which is the same as the original image. The scheme in [8] is based on polynomial information hiding, and the shadow size is small.In the restoration phase, only part of the pixel values participated in the authentication. In fact, the values of pixels that do not participate in authentication may be tampered, and the security level is low. The shadow size in schemeIand schemeIIis almost the same as the original scheme, and all pixel values are involved in the authentication. Therefore, malicious tampering by forgers can be prevented during the authentication phase.Figure4 shows the shadow image size comparison between our scheme and other schemes. As the threshold k increases, the ratio of the shadow image to the original image changes.Figure 4
Comparisons with the size of shadow images.In addition, there are shadows in the application system in the image distribution, there are shadows and each shadow is stored in any distributed storage node. Due to thek,n-threshold characteristic of the SIS scheme, when the threshold k is reached, the original secret image can be recovered. The failed transmission of the remaining n−k shadows will not affect the entire reconstruction phase.The Peak Signal to Noise RatioPSNR is an objective criterion for evaluating images. Usually, the output image will be different from the original image to some extent after encryption and decryption. To measure the processed image, the PSNR value is usually used to measure whether the processing method is satisfactory. The formula is as follows: PSNR=10×log102n−12/MSE, where is the mean square error between the original image and the processed image, expressed as MSE=1/m×n∑im∑jnxi,j−xi,j′2 where m×n is the size of the image, and xi,j,xi,j′ is the pixel value of the original image and the reconstructed image at the point i,j. Therefore, the smaller the difference between the two images, the greater the PSNR value. In general, if PSNR≥30dB, the difference between the reconstructed image and the original secret image is difficult to detect by the human eye. Table 2 is the comparison of PSNR values between the four classic images processed by digital image processing shown in Experiment 1 and Experiment 2.Table 2
ThePSNR value of the experimental image.
Experimental imageLenaLandscapePeopleRicePSNR71.7887.2369.86∞Since the pixel value in the rice grain image is not greater than 250, thenPSNR=∞. On the other hand, all the PSNR of Lena, Landscape and People image are greater than 30dB. Therefore, it is very difficult to detect the difference between the original secret image and the reconstructed image with human eyes.


### 4.3. Security Analysis

In this section, we will analyze the security of the proposed scheme from two aspects: the security of the secret sharing mechanism and the security of our proposed scheme. In the proposed scheme, it is mainly necessary to prove that thek,n-threshold must be met in the two phases of shadow image generation and secret image restoration and whether the presence of a fraudster can be detected when the participant reaches the threshold k.Theorem 1.
The proposed scheme satisfies the property ofk,n-threshold.The scheme proposed in this paper satisfies the security of the secret sharing mechanism. A trusted third party distributes the shadow images to different participants evenly and randomly, and any two participants are completely independent. We discuss the case of less thank shadows in image reconstruction and select rr<k shadows S1′,S2′,…,Sr′ from n shadow images Sj′,j∈1,n for the reconstruction. Since there are k coefficients for the k−1 degree Lagrange interpolation polynomial, according to the nature of the polynomial, it can be obtained that the coefficients of the polynomial cannot be solved by using Lagrange interpolation for k−1 sub-shadows. Therefore, no image information can be generated. We can clearly see that k coefficients cannot be generated from r equations in the following equation:(4)f′1=a0+a1+⋯+ak−1,f′2=a0+2a1+⋯+2k−1ak−1,⋮f′r=a0+ra1+⋯+rk−1ak−1.In addition, we scramble the secret image before generating the shadow image. Thus, the shadow image in this scheme is disordered (Figures1(c)–1(h)) and will not reveal any information related to the original secret image. Considering that the number of shadow images reaches the threshold k during the image restoration process, the k shadow images participating in the reconstruction must be authenticated before the image reconstruction and restoration. According to the nature of the Lagrange interpolation polynomial, the secret pixel value and the authentication code can be solved. Prevent fraud by judging whether the authentication code is correct. When the authentication is successful, the secret pixel value is used to restore the original secret image.On the contrary, when the authentication fails, the presence of deception shadows can be detected, the reconstruction and restoration of the secret image can be terminated. Therefore, when there is no shadow image with deception, anyk or more shadow images can be reconstructed to recover the original secret image.Theorem 2.
Our scheme I can successfully detect the presence of cheaters.SupposeS1,S2,…,Sk participate in secret reconstruction phase and S1,S2,…,Sk−1 are cheaters. Since cheating prevention algorithm is used in each block Pi,i∈1,t, we only analyze the cheating prevention in decoding P1 in this theorem. Suppose the fake shares from cheaters are Oi′=Oi+Oi∗,i=1,2,...,k−1. They can get a polynomial f∗∗x=fx+f∗x in the image reconstruction phase, where f∗x=a0∗+a1∗x+⋯+b0∗xk−2+b1∗xk−1. Since f∗x can be decided by cheaters exclusively, they can select two values b0∗,b1∗, and satisfy that b0∗=a0∗⊕a1∗⊕⋯⊕ak−4∗,b1∗=a1∗⊕a2∗⊕⋯⊕ak−3∗. According to our algorithm, if there exist two values b0′,b1′, satisfying b0′=a0+a0∗⊕a1+a1∗⊕⋯⊕ak−4+ak−4∗b1′=a1+a1∗⊕a2+a2∗⊕⋯⊕ak−3+ak−3∗, the cheating avoids detection. We can easily observe that cheating succeeds only b0∗,=b0′,b1∗=b1′. As analyzed in Theorem 1, these k−1 cheaters have no information on authentication codes; the possibility of b0∗,=b0′,b1∗=b1′ is 1/216. As a result, the successful cheating probability δ=1/216 means that schemeIis effective in detecting the cheating.Theorem 3.
Scheme II can successfully detect the presence of cheaters.Compared with scheme I, there is only one authentication code in scheme II. They can get a polynomialf∗∗x=fx+f∗x in the image reconstruction phase, where f∗x=a0∗+a1∗x+⋯+ak−2∗xk−2+b0∗xk−1. Since f∗x can be decided by cheaters exclusively, they can select one value b0∗ and satisfy step 2 and step 3 in the shadow generation phase in schemeII—the sequence M∗=a0∗‖a1∗‖⋯‖ak−2∗ at this time. If there exists one value b0′, satisfying M′=a0+a0∗‖a1+a1∗‖⋯‖ak−2+ak−2∗, the cheating avoids detection. We can easily observe that cheating succeeds only when b0∗=b0′. As analyzed in Theorem 1, these k−1 cheaters have no information on authentication codes; the possibility of b0∗=b0′ is 1/251. As a result, the successful cheating probability δ=1/251 means that schemeIIis effective in detecting the cheating.


## 4.1. Experiment Results

In this section, we use two experiments to illustrate the proposed schemes in this paper.For schemeI, we let the thresholdk,n=5,6, then each pixel block contains three pixels values. Supposing the first pixel blocks P1=57,121,90, the dealer calculates the secret authentication codes b0=57⊕121=64,b1=121⊕90=35. Then, we construct k−1=4 degree polynomial fx=57+121x+90x2+64x3+35x4mod251. Finally, we calculate the six shadows:S1=f1=116,S2=f2=225S3=f3=20S4=f4=228,S5=f5=157S6=f6=206. In the restoration phase, we choose five shadows, namely S1,S2, S3,S4,S5 to reconstruct the secret image. Suppose we forge a false shadow S1′=110 and then select S2′,S3′,S4′,S5′. Next, we generate the polynomial fx′=27+34x+135x2+193x3+223x4 through the Lagrange interpolation function. Here, b0′=193,b1′=223. Since 27⊕34=57≠b0′,34⊕135=165≠b1′, so we can successfully detect there exists fake shadow and the cheating prevented. We take 5,6-threshold scheme to test the proposed schemeI, the test image is the well-known image “Lena.” The goal is that any five out of six shadow images can be used for image reconstruction. The corresponding experimental results are shown in Figure 1.Figure 1
Experiment 1 results: (a) an original secret image; (b) the reconstructed image; (c–h) the six shadow images.
(a)(b)(c)(d)(e)(f)(g)(h)In Figure1, (a) shows the original secret image, its size is 256×256; (b) is the reconstructed image by using the Lagrange interpolating polynomial and the five shadow images chosen randomly (we choose the first five shadow images to reconstruct the original secret image); (c–h) are the shadow images, and the sizes of the six shadow images are 256×256/k−2.For scheme II, we let the thresholdk,n=4,6, then each pixel block contains three pixels values. Supposing that the first pixel block P1=57,121,90, we generate a 128-bit message digest M1 through the Md5 algorithm. Next, perform a bit-by-bit XOR on every 16 bit to obtain a value of 1 bit. There is a total of 8-bit value as the secret authentication code b=10100001=161. Next, we construct a k−1=3 degree polynomial fx=57+68x+90x2+161x3mod251. Finally, we calculate the six shadows: S1=f1=178S2=f2=190S3=f3=55S4=f4=237S5=f5=196S6=f6=145. In the restoration phase, we choose four shadows to reconstruct the secret image. Suppose that we forge a fake shadow S1′=177 and then select S2′,S3′,S4′. Next, we calculate the polynomial fx′=53+209x+214x2+203x3 through the Lagrange interpolation function. Here, b′=203. We use the same MD5 algorithm to calculate the authentication message digest b″=30 for P1′=53,209,214. Since b″≠b′, so we can successfully detect the presence of deception and cheating prevention. We take 4,6-threshold scheme to test the proposed scheme II. The goal is that any four out of six shadow images can be used for image reconstruction. The corresponding experimental results are shown in Figure 2.Figure 2
Experiment 2 results: (a) the original secret image; (b) the reconstructed image; (c–h) the six shadow images.
(a)(b)(c)(d)(e)(f)(g)(h)In Figure2, (a) shows the original secret image, its size is 256×256; (b) is the reconstructed image by using the Lagrange interpolating polynomial and the four shadow images chosen randomly (we choose the first four shadow images to reconstruct the original secret image); (c–h) are the shadow images, and the sizes of the six shadow images are 256×256/k−1 (here k=4).Figure3 shows the experimental results of the other two typical pictures. Through the histogram, we can clearly find that the pixel values in image “Rice” are all less than 250, and the restored image is lossless. In image “Landscape,” there are pixel values greater than 250, so the restored image is lossy. Visually, there is not much difference.Figure 3
The experiment for other images: (a) the secret image of Rice; (b) the histogram of Rice; (c) the reconstructed image of Rice; (d) the secret image of Landscape; (e) the histogram of Landscape; (f) the reconstructed image of Landscape.
(a)(b)(c)(d)(e)(f)


## 4.2. Performance Analysis

Normally, the shadow size is an important factor in evaluating the performance of an SIS scheme, since a smaller size has lower storage and transmission costs. Table1 shows the comparisons between our scheme and other related schemes.Table 1
Comparisons with the related scheme.
The schemeTechnologyThe shadow sizeEvery pixel value participates in certificationPrevent cheatingScheme in [26]SISIYesYesScheme in [27]SISIYesYesScheme in [8]Information hiding1/k−1INoNoOur proposed scheme IInformation hiding1/k−2IYesYesOur proposed scheme IIInformation hiding1/k−1IYesYesThe scheme in [26] is based on the SIS. The visual secret sharing is applied to the polynomial-based SIS, and the shadows can be mutually authenticated by exchanging the lowest plane. This scheme has low complexity of shadow generation and authentication. However, the shadow image is larger, which is the same as the original image. The scheme in [8] is based on polynomial information hiding, and the shadow size is small.In the restoration phase, only part of the pixel values participated in the authentication. In fact, the values of pixels that do not participate in authentication may be tampered, and the security level is low. The shadow size in schemeIand schemeIIis almost the same as the original scheme, and all pixel values are involved in the authentication. Therefore, malicious tampering by forgers can be prevented during the authentication phase.Figure4 shows the shadow image size comparison between our scheme and other schemes. As the threshold k increases, the ratio of the shadow image to the original image changes.Figure 4
Comparisons with the size of shadow images.In addition, there are shadows in the application system in the image distribution, there are shadows and each shadow is stored in any distributed storage node. Due to thek,n-threshold characteristic of the SIS scheme, when the threshold k is reached, the original secret image can be recovered. The failed transmission of the remaining n−k shadows will not affect the entire reconstruction phase.The Peak Signal to Noise RatioPSNR is an objective criterion for evaluating images. Usually, the output image will be different from the original image to some extent after encryption and decryption. To measure the processed image, the PSNR value is usually used to measure whether the processing method is satisfactory. The formula is as follows: PSNR=10×log102n−12/MSE, where is the mean square error between the original image and the processed image, expressed as MSE=1/m×n∑im∑jnxi,j−xi,j′2 where m×n is the size of the image, and xi,j,xi,j′ is the pixel value of the original image and the reconstructed image at the point i,j. Therefore, the smaller the difference between the two images, the greater the PSNR value. In general, if PSNR≥30dB, the difference between the reconstructed image and the original secret image is difficult to detect by the human eye. Table 2 is the comparison of PSNR values between the four classic images processed by digital image processing shown in Experiment 1 and Experiment 2.Table 2
ThePSNR value of the experimental image.
Experimental imageLenaLandscapePeopleRicePSNR71.7887.2369.86∞Since the pixel value in the rice grain image is not greater than 250, thenPSNR=∞. On the other hand, all the PSNR of Lena, Landscape and People image are greater than 30dB. Therefore, it is very difficult to detect the difference between the original secret image and the reconstructed image with human eyes.


## 4.3. Security Analysis

In this section, we will analyze the security of the proposed scheme from two aspects: the security of the secret sharing mechanism and the security of our proposed scheme. In the proposed scheme, it is mainly necessary to prove that thek,n-threshold must be met in the two phases of shadow image generation and secret image restoration and whether the presence of a fraudster can be detected when the participant reaches the threshold k.Theorem 1.
The proposed scheme satisfies the property ofk,n-threshold.The scheme proposed in this paper satisfies the security of the secret sharing mechanism. A trusted third party distributes the shadow images to different participants evenly and randomly, and any two participants are completely independent. We discuss the case of less thank shadows in image reconstruction and select rr<k shadows S1′,S2′,…,Sr′ from n shadow images Sj′,j∈1,n for the reconstruction. Since there are k coefficients for the k−1 degree Lagrange interpolation polynomial, according to the nature of the polynomial, it can be obtained that the coefficients of the polynomial cannot be solved by using Lagrange interpolation for k−1 sub-shadows. Therefore, no image information can be generated. We can clearly see that k coefficients cannot be generated from r equations in the following equation:(4)f′1=a0+a1+⋯+ak−1,f′2=a0+2a1+⋯+2k−1ak−1,⋮f′r=a0+ra1+⋯+rk−1ak−1.In addition, we scramble the secret image before generating the shadow image. Thus, the shadow image in this scheme is disordered (Figures1(c)–1(h)) and will not reveal any information related to the original secret image. Considering that the number of shadow images reaches the threshold k during the image restoration process, the k shadow images participating in the reconstruction must be authenticated before the image reconstruction and restoration. According to the nature of the Lagrange interpolation polynomial, the secret pixel value and the authentication code can be solved. Prevent fraud by judging whether the authentication code is correct. When the authentication is successful, the secret pixel value is used to restore the original secret image.On the contrary, when the authentication fails, the presence of deception shadows can be detected, the reconstruction and restoration of the secret image can be terminated. Therefore, when there is no shadow image with deception, anyk or more shadow images can be reconstructed to recover the original secret image.Theorem 2.
Our scheme I can successfully detect the presence of cheaters.SupposeS1,S2,…,Sk participate in secret reconstruction phase and S1,S2,…,Sk−1 are cheaters. Since cheating prevention algorithm is used in each block Pi,i∈1,t, we only analyze the cheating prevention in decoding P1 in this theorem. Suppose the fake shares from cheaters are Oi′=Oi+Oi∗,i=1,2,...,k−1. They can get a polynomial f∗∗x=fx+f∗x in the image reconstruction phase, where f∗x=a0∗+a1∗x+⋯+b0∗xk−2+b1∗xk−1. Since f∗x can be decided by cheaters exclusively, they can select two values b0∗,b1∗, and satisfy that b0∗=a0∗⊕a1∗⊕⋯⊕ak−4∗,b1∗=a1∗⊕a2∗⊕⋯⊕ak−3∗. According to our algorithm, if there exist two values b0′,b1′, satisfying b0′=a0+a0∗⊕a1+a1∗⊕⋯⊕ak−4+ak−4∗b1′=a1+a1∗⊕a2+a2∗⊕⋯⊕ak−3+ak−3∗, the cheating avoids detection. We can easily observe that cheating succeeds only b0∗,=b0′,b1∗=b1′. As analyzed in Theorem 1, these k−1 cheaters have no information on authentication codes; the possibility of b0∗,=b0′,b1∗=b1′ is 1/216. As a result, the successful cheating probability δ=1/216 means that schemeIis effective in detecting the cheating.Theorem 3.
Scheme II can successfully detect the presence of cheaters.Compared with scheme I, there is only one authentication code in scheme II. They can get a polynomialf∗∗x=fx+f∗x in the image reconstruction phase, where f∗x=a0∗+a1∗x+⋯+ak−2∗xk−2+b0∗xk−1. Since f∗x can be decided by cheaters exclusively, they can select one value b0∗ and satisfy step 2 and step 3 in the shadow generation phase in schemeII—the sequence M∗=a0∗‖a1∗‖⋯‖ak−2∗ at this time. If there exists one value b0′, satisfying M′=a0+a0∗‖a1+a1∗‖⋯‖ak−2+ak−2∗, the cheating avoids detection. We can easily observe that cheating succeeds only when b0∗=b0′. As analyzed in Theorem 1, these k−1 cheaters have no information on authentication codes; the possibility of b0∗=b0′ is 1/251. As a result, the successful cheating probability δ=1/251 means that schemeIIis effective in detecting the cheating.


## 5. Conclusions

Many security fields such as online transactions, digital image storage, and transmission require high security. There may be tampered with and forged secret sharing to participate in the reconstruction of secret information. Therefore, a secret scheme that can detect deception and prevent tampering has a wide range of practical applications.We are considering the problem of cheating based on SIS itself, which can prevent the presence of cheaters among participants. In the process of polynomial-based design, the value processed by the polynomial each time is fixedk coefficients. Too many authentication codes will cause the shadow image to increase, which is not conducive to storage. When performing antispoofing share authentication, how to balance between complexity and storage is very critical. In the first scheme proposed in this paper, two authentication codes are generated for authentication through a simple XOR operation. The size of the shadow image is 1/k−2. This lightweight solution with less complexity is suitable for Internet of Things chips or some resource-constrained, embedded devices. In contrast, the second scheme is to generate an authentication code for authentication based on a hash algorithm, and the size of the shadow image is the same as the original Thien-Lin scheme. This kind of solution with higher complexity, although the storage efficiency is slightly increased, which is suitable for environments and devices with larger storage space and higher security levels. Another interesting work is the ability to accurately detect which one is a deceiver. This is the focus of our next research.



---

*Source: 9274415-2021-08-23.xml*