Public key based bidirectional shadow image authentication without pixel expansion in image secret sharing*

Xuehu YAN,Longlong LI,Jia CHEN,Lei SUN

National University of Defense Technology,Hefei 230037,China

Abstract:Image secret sharing(ISS)is gaining popularity due to the importance of digital images and its wide application to cloud-based distributed storage and multiparty secure computing.Shadow image authentication generally includes shadow image detection and identification,and plays an important role in ISS.However,traditional dealer-participatory methods,which suffer from significant pixel expansion or storing auxiliary information,authenticate the shadow image mainly during the decoding phase,also known as unidirectional authentication.The authentication of the shadow image in the distributing(encoding)phase is also important for the participant.In this study,we introduce a public key based bidirectional shadow image authentication method in ISS without pixel expansion for a(k,n)threshold.When the dealer distributes each shadow image to a corresponding participant,the participant can authenticate the received shadow image with his/her private key.In the decoding phase,the dealer can authenticate each received shadow image with a secret key;in addition,the dealer can losslessly decode the secret image with any k or more shadow images.The proposed method is validated using theoretical analyses,illustrations,and comparisons.

Key words:Image secret sharing;Shadow image authentication;Public key;Pixel expansion;Lossless decoding

1 Introduction

Using image secret sharing(ISS)for a(k,n)threshold,the dealer encodes a secret image to outputnshadow images,also known as shadows or shares,which are then distributed to the correspondingnparticipants.The dealer can decode the secret image with anykor more shadow images(i.e.,at mostn-kshadow images are lost),which is known as the loss-tolerant property of ISS.Hence,ISS is currently used in several applications,such as access control(Yan et al.,2017;Beugnon et al.,2019),key management(Cheng et al.,2018),blockchain(Fukumitsu et al.,2017;Shen J et al.,2019),password transmission(Wang W et al.,2017),digital watermarking(El-Latif et al.,2018),identity authentication(Chavan et al.,2014;Li YN and Guo,2018),and distributive storage in a cloud(Komargodski et al.,2017).The value of each binary pixel can be represented by 1 bit,and the value of each grayscale pixel can be represented by 1 byte;therefore,ISS is easily extended to secret sharing.Among many sharing principles of traditional ISS technologies(Wang GY et al.,2016;Shivani and Agarwal,2018;Yan et al.,2018,2020b;Meng et al.,2021;Harn et al.,2022),the use of polynomials(Pilaram and Eghlidos,2017)is widely studied.

Shamir(1979)designed the first polynomialbased secret sharing for a(k,n)threshold by randomly building a(k-1)-degree polynomial.Inspired by Shamir’s work,some follow-up works(Thien and Lin,2002;Liu YX and Yang,2017;Liu YX et al.,2018a,2019;Yan et al.,2021)investigated several improved polynomial-based ISS schemes to obtain significant properties.Polynomial-based ISS is advantageous because the decoded secret image has high quality and does not exhibit pixel expansion.The dealer can encode a secret image tonshadow images using polynomial-based ISS.The dealer normally distributes the shadow images toncorresponding participants(Fig.1).When anykor more shadow images are collected during the normal dealer-participatory decoding phase,the secret is decoded with high quality using the Lagrange interpolation(Fig.1).

Fig.1 Normal dealer-participatory shadow image distributing(a)and secret image decoding(b)

However,the above-mentioned polynomialbased ISS schemes cannot authenticate shadow images.The authentication plays an important role in ISS(Fig.2).If a watch dog tampers with the shadow image during abnormal dealer participatory shadow image distribution,a participant cannot authenticate the received shadow image without authentication.Here,a watch dog represents an eavesdropper in cryptography or a third party on the network in communication security.In an abnormal secret image decoding phase,the dealer cannot successfully decode the original secret image or even distinguish the fake one if there is a fake shadow image among thekcollected ones.

Fig.2 Distribution of an abnormal shadow image(a)and decoding of a secret image without authentication(b)

In contrast,in the distribution of an abnormal shadow image and the decoding of a secret image as shown in Fig.3,authentication allows a participant to judge whether the received shadow image is fake or tampered with when receiving each shadow image from the corresponding participant;the dealer can also judge it based on the result of shadow image authentication,stop the decoding phase if a fake shadow image is detected and identified,and broadcast the fake one to all the other participants to avoid further deception.

Fig.3 Distribution of an abnormal shadow image(a)and decoding of a secret image with authentication(b),illustrating the motivation of this paper

Shadow image authentication is critical and ISS with shadow image authentication ability is gaining popularity.Most existing ISS schemes that support shadow image authentication can be classified into two categories.The first category uses information hiding(or fragile watermark)(Lin and Tsai,2004;Chang et al.,2008;Liu YJ and Chang,2018;Liao et al.,2022).A typical work is Liu YJ and Chang(2018),in which the authors realized shadow image authentication using turtle shell based information hiding.This type of scheme embeds the shadow images in the cover images using existing information hiding techniques,resulting in a possible high pixel expansion(Fig.4a).The other category uses auxiliary information(Li P et al.,2010;Ulutas et al.,2013;Du et al.,2020),such as hash.This type of scheme uses the auxiliary information to achieve authentication,which also results in possible pixel expansion or increase in the required storage space(Fig.4b).

Fig.4 Analyses of traditional image secret sharing schemes with shadow authentication ability:(a)using information hiding;(b)using auxiliary information

Liu YX et al.(2018b)proposed polynomialbased ISS for a(k,n)threshold with shadow image authentication based on improved polynomialbased ISS.They embed an authentication value into a polynomial coefficient.However,this scheme can authenticate the shadow image only in the decoding phase,also known as unidirectional authentication,and it cannot authenticate the shadow image during the shadow image distribution phase.It also has flaws in fake participant identification,auxiliary encryption,and lossy decoding.

Yan et al.(2020a)proposed a separate shadow authentication method using a fusing(2,2)-threshold visual cryptographic scheme(VCS)(Shen G et al.,2017)and polynomial-based ISS.In the encoding phase,the shadow image bit generated using VCS is embedded in the most significant bit(MSB)of each shadow image pixel.However,their method is used only for shadow image authentication during the secret image decoding phase.Following Yan et al.(2020a),Jiang et al.(2020)developed an authentication using a(2,n+1)-threshold VCS and the least significant bit instead of the MSB.However,it cannot authenticate a shadow image during the distribution phase.

This study introduces a bidirectional shadow image authentication method without pixel expansion in ISS for a(k,n)threshold based on ISS rather than on information hiding(Fig.3).Here“bidirectional shadow image authentication”shows that shadow image authentication in the shadow image distributing and secret image decoding(sending)phases(Fig.3)achieves stronger authentication than“unidirectional shadow image authentication.”

The following is the key challenge.The encoding and decoding methods usually entail the use of mathematical functions in ISS,such as polynomial and interpolation,which are sensitive to slight changes;thus,achieving bidirectional shadow image authentication is a key challenge.

In this study,we introduce a public key based bidirectional shadow image authentication method without pixel expansion in ISS for a(k,n)threshold.

In the encoding phase,the dealer first uses a random number generator with his/her secret key to generate two coordinates for each participant.Second,a hash of the pixels between the two coordinates is generated for the authentication of each shadow image.Third,the two coordinates are encrypted with the public key of each participant to obtain two encrypted coordinates.Finally,the encrypted coordinates and the hash value are fused into each shadow image to avoid any pixel expansion using a screening operation in the process of polynomial-based ISS.Here,a“screening operation”denotes an operation that can screen the polynomial coefficients to satisfy some requirements.When the dealer distributes each shadow image to a corresponding participant,the participant can authenticate the received shadow image with his/her private key.

In the decoding phase,the dealer can authenticate each received shadow image with a secret key,i.e.,achieving a separate shadow image authentication ability;in addition,the dealer can losslessly decode the secret image with anykor more shadow images.The proposed scheme has no pixel expansion with a separate shadow image authentication ability.In addition,it achieves lossless decoding without auxiliary encryption.The proposed method is validated using theoretical analyses,illustrations,and comparisons.

2 Preliminaries

We describe some preliminaries for our introduced method in this section,including the principle of polynomial-based ISS,public key encryption,and hash function.We use bidirectional authentication in polynomial-based ISS,public key encryption,and a hash function to authenticate a separate shadow image.

First,notations used in this study are presented in Table 1.

Table 1 Chief notations in the paper

2.1 Polynomial-based ISS scheme

To encode a grayscale secret image,Shamir’s original polynomial-based ISS scheme splits any secret pixel valuesintonvalues,which are then assigned toncorresponding pixels in shadow images.We present Shamir’s original polynomial-based scheme in Algorithm 1.

In the decoding phase,given anykpairs of thenpairs{(i,SCi)}ni=1,we can obtain the coefficients off(i)using Lagrange interpolation and obtains=f(0).However,secretscannot be solved with fewer thankshadow images.Finally,an ISS for a(k,n)threshold is achieved.

In addition,when the original polynomial-based secret sharing is applied to the ISS,we conduct the following analysis:Because 0≤SCi(h,w)≤255,fori=0,1,2,···,k-1,Pcannot be any prime greater thana0.The primes closest to 255 are 251 and 257.If 257 is used,we cannot store theithshadow pixel when SCi(h,w)=256;if 251 is used,we cannot reconstruct the secret pixela0when 251≤a0≤255.Finally,traditional polynomial-based ISS selectsP=251 for a slight loss.

2.2 Public key encryption

The basic idea behind public key encryption is that a cryptosystem with two distinct keys may be possible.A public key is used to encode the plaintext and a private key is used to decode the ciphertext,where the public key can be public,i.e.,known to everyone,and the private key is private,i.e.,known to only one person.In this way,a public key encryption system allows everyone to encode a plaintext to be sent to one person,and only that person can decode the ciphertext.

Algorithm 1 Shamir’s polynomial-based ISS Input:a grayscale secret image S of size H×W and the threshold parameters(k,n).Output:n shadow images SC1,SC2,···,SCn.Step 1:Select P=251.At each position(h,w)∈{(h,w)|1≤h≤H,1≤w≤W},repeat steps 2 and 3.Step 2:For s=S(h,w),if s≥P,fix s=P-1.To split s into pieces SC1(h,w),SC2(h,w),···,SCn(h,w),construct a(k-1)-degree polynomial as follows:f(x)=(a0+a1x+···+ak-1xk-1)mod P, (1)in which a0=s,and ai is random in[0,P-1],for i=1,2,···,k-1.Step 3:Calculate SC1(h,w)=f(1),SC2(h,w)=f(2),···,SCn(h,w)=f(n), (2)where i can be used for an identifying index or an order label for the ith participant.Step 4:Output n shadow images SC1,SC2,···,SCn.

A public key encryption system is suitable for shadow image authentication in ISS,which is further analyzed as follows.If each participant has his/her public key and private key,the dealer can use the public key to generate an authenticating message and only the participant with the private key can authenticate the shadow image.It is a significant challenge to achieve bidirectional shadow image authentication using a public key encryption system with the condition of no pixel expansion.

The RSA cryptosystem is the best-known example of a public key encryption system,and it is used in our introduced method.Note that other public key encryption systems can also be used with our method.

2.3 Hash function

A hash function is used to compress a plaintext of arbitrary length to a random-looking and short plaintext digest with a fixed length,which is a public function known to all.A hash function has the property that it is computationally infeasible to yield collisions;i.e.,it is difficult to decode the plaintext given digest.Additionally,if the plaintext is altered even a bit,the digest will no longer be valid.In this way,a hash function can achieve data authentication and integrity.

The hash function is suitable for detecting shadow images in ISS,which is further analyzed as follows.The dealer can compress a shadow image to a digest and send it to the participant along with the shadow image.The participant can use the digest to determine whether the shadow image has been altered.It is a significant challenge to achieve bidirectional shadow image authentication using a hash function without pixel expansion.

SHA-256 is a well-known hash function,and is used in our introduced method.Note that other hash functions can also be used in our method.

Above all,the difficult point is how to achieve bidirectional shadow image authentication by fusing the advantages of a public key encryption system and a hash function without pixel expansion.

3 Proposed public key based bidirectional shadow image authentication without pixel expansion

3.1 Proposed method

3.1.1 Framework

Fig.5 shows the framework of the proposed public key based bidirectional shadow image authentication method without pixel expansion.The key modules in the framework are as follows:The dealer generates the coordinates using his/her secret key so that he/she knows the concentrated positions to be hashed to authenticate the shadow image when receiving each shadow image during the decoding phase.The dealer encrypts the coordinates using each participant’s public key so that the true participant with the private key can authenticate the shadow image when receiving each shadow image during the shadow image distribution phase.The dealer embeds the encrypted coordinates and hash values into the firstnand lastnlines of each shadow image to avoid storing auxiliary information.In this way,no pixel expansion can be achieved.

Fig.5 Framework of the proposed public key based bidirectional shadow image authentication method

The design idea of the proposed public key based bidirectional shadow image authentication method without pixel expansion is shown in Fig.6.

3.1.2 Algorithms

Algorithm 2 is the proposed detailed encoding algorithm,and the decoding method is given in Algorithm 3.Fig.6 is the overview of the proposed method only for the current position(h,w),which must be combined with Algorithm 2 to better understand our method.

Fig.6 Design concept of the proposed public key based bidirectional shadow image authentication method

Regarding Algorithm 2,we comment as follows:

1.In step 1,kDserves as a seed.Security and coordinate ranges are considered in the generation of.As in Table 1,anddenote the starting and ending plain coordinates for theithparticipant to be hashed,respectively.Through the corresponding length of the binary bits,we can generate temporary random numbers,denoted byand,to further satisfy thatandusing simple shift operations,i.e.,andHere,the length of the binary form ofandisand that ofandis

2.In step 1,the dealer uses his/her secret key,kD,by a random number generator to generateand.Therefore,the dealer knows the concentrated positions to be hashed in step 7 and he/she can authenticate the shadow image when receiving each shadow image during the decoding phase.Them-sequence is selected as the random number generator.Some other enhanced random number generators can also be used to obtain better quality randomness.

3.In step 1,the dealer uses each participant’s public key to encryptto obtain cipherand furtherand.Thus,only the participant with his/her private key can decryptto obtain,i.e.,the concentrated positions to be hashed in step 8.Thus,during the shadow image distribution phase,the participant with the private key can authenticate the shadow image when receiving each shadow image.

4.To avoid supplementary bits,we handle value 256 in our scheme as follows.In step 2,we select a prime numberP=257 rather than 251 and in steps 5,7,and 10,we use a screening operation,SCi(h,w)＜P-1 to achieve a value of the shadow image pixel ranging from 0 to 255 and lossless decoding.Here,a“screening operation”denotes an operation that will screen the polynomial coefficients to satisfy some requirements.

Algorithm 2 Encoding phase of the proposed public key based method Input:any grayscale secret image S with size of H×W;kD,kip,and kis,i=1,2,···,n;threshold parameters(k,n).Output:shadow images SCi,i=1,2,···,n.Step 1:The dealer uses his/her secret key kD to generate■Zih1,Ziw1■■■Zih2,Ziw2 using a random number generator,for i=1,2,···,n,where Zih1∈(n,H 2],Zih2∈(H 2,H-n]and Ziw1∈[1,W],Ziw2∈[1,W].kip is used to encode plain Zix to obtain cipher Z＇ix.Z＇ix is then converted to its binary form,denoted by bZ＇ix,for x=h1,w1,h2,w2 and i=1,2,···,n.Expand bZ＇ix by adding 0 at the beginning to obtain 0bZ＇ix with length of W/4.Step 2:P=257 is selected.At each position(h,w)∈{(h,w)|1≤h≤H,1≤w≤W},repeat steps 3-10.Step 3:If h≤n,go to step 4;else if n＜h≤H-n,go to step 6;else go to step 8.Step 4:Construct a(k-1)-degree polynomial as follows:f(x)=(a0+a1x+···+ak-1xk-1)mod P, (3)where a0=S(h,w),and ai is random,for i=1,2,···,k-1.Calculate SCi(h,w)=f(i),for i=1,2,···,n.Step 5:If SCi(h,w)＜P-1 and XOR4LBs(SCi(h,w))=and■■ ■0bZ＇ix■,when w mod W 4/=0,0bZ＇ix w mod W 4■■W 4■,when w mod W 4=0,go to the next position(step 2),for i=1,2,···,n,where x=h1 when w≤W/4,x=w1 when W/4＜w≤W/2,x=h2 when W/2＜w≤3W/4,and x=w2 when 3W/4＜w≤W;otherwise,go to step 4.Step 6:Construct a(k-1)-degree polynomial as follows:f(x)=(a0+a1x+···+ak-1xk-1)mod P, (4)where a0=S(h,w),and ai is random,for i=1,2,···,k-1.Calculate SCi(h,w)=f(i),for i=1,2,···,n.Step 7:If SCi(h,w)＜P-1,go to the next position(step 2),for i=1,2,···,n;otherwise,go to step 6.Step 8:Concentrate SCi(Zih1,Ziw1),SCi(Zih1,Ziw1+1),···,SCi(Zih2,Ziw2),and then the concentration result is compressed using a hash function on a digest,denoted by HVi,for i=1,2,···,n.Step 9:Construct a(k-1)-degree polynomial as follows:f(x)=(a0+a1x+···+ak-1xk-1)mod P, (5)where a0=S(h,w),and ai is random,for i=1,2,···,k-1.Calculate SCi(h,w)=f(i),for i=1,2,···,n.Step 10: If SCi(h,w)＜P-1 and XOR4LBs(SCi(h,w))=HVi(w),where i=H-h+1,go to the next position(step 2),for i=1,2,···,n;otherwise,go to step 9.Step 11:Output n grayscale shadow images SC1,SC2,···,SCn.

5.In step 3,our information embedding and processing order for theithshadow image is further illustrated in Fig.7.

Fig.7 Information embedding and processing order for the ith shadow image

6.Steps 4,6,and 9 are used to achieve a(k,n)threshold using the polynomial without pixel expansion.

Algorithm 3 Authentication and decoding in the proposed public key based bidirectional shadow image authentication without pixel expansion Input:grayscale shadow images SC1,SC2,···,SCn;kD,kip,and kis,i=1,2,···,n.Output:decoded grayscale secret image S＇with a size of H×W and authentication result of SCi,for i=1,2,···,n.Step 1:In the shadow image distribution phase,when the ith participant receives SCi,extract Z＇ix through the XOR4LBs operation on the ith line of SCi,for x=h1,w1,h2,w2.Use kis to decrypt Z＇ix to obtain Zix.Concentrate SCi■Zih1,Ziw1■■Zih1,Ziw1+1■,···,SCi■,SCi Zih2,Ziw2■,and then the concentration result is compressed by the hash function to HVi.Perform the XOR4LBs operation on the last ith line of SCi.If the result is equal to HVi,pass the authentication;otherwise,identify the fake one,denoted by i*,and broadcast the fake one.Step 2:In the secret image decoding phase,when the dealer receives SCi,use his/her secret key kD by the random number generator to generate■■■■■Zih1,Ziw1■and ■Zih2,Ziw2. Concentrate SCi ■■■Zih1,Ziw1,,and then the concentration result is compressed by the hash function to HVi.Perform the XOR4LBs operation on the last ith line of SCi.If the result is equal to HVi,pass the authentication,and go to step 3;otherwise,identify the fake one,denoted by i*,and broadcast the fake one.Step 3:When collecting any k grayscale shadow images SCq1,SCq2,···,SCqk,for each position(h,w)∈{(h,w)|1≤h≤H,1≤w≤W},repeat steps 4 and 5.Step 4:Solve Eq.(6)by Lagrange interpolation to obtain a0:SCi Zih1,Ziw1+1,···,SCi Zih2,Ziw2■■■■■■■■■■■■ ■■■■■■■■■■■SCq1(h,w)=(a0+a1q1+···+ak-1q1k-1)mod P,SCq2(h,w)=(a0+a1q2+···+ak-1q2k-1)mod P,...SCqk-1(h,w)=(a0+a1qk-1+···+ak-1qk-1k-1)mod P,SCqk(h,w)=(a0+a1qk+···+ak-1qkk-1)mod P.(6)Step 5:Compute S＇(h,w)=a0.Step 6:Output the decoded grayscale secret image S＇with a size of H×W and the authentication result of SCi,for i=1,2,···,n.

7.Step 5 embeds 0bZ＇ixinto theithline of theithshadow image.Step 10 embeds hash code into the lastithline of theithshadow image.Finally,no pixel expansion occurs.However,0bZ＇ih1,0bZ＇iw1,0bZ＇ih2,0bZ＇iw2are inserted only in linei(Fig.6);HViis inserted only in lineH-i+1.The probability of hash collisions is decided by the adopted hash function;thus,it is not discussed.

8.In steps 5,7,and 10,we can screena1,a2,···,ak-1to satisfy the embedding and lossless decoding requirements because grayscalesa1,a2,···,ak-1are random,whenn-kis small.

9.Although it is possible to fake then-1 lines of the first and lastnlines in each shadow image,the influence on the secret image is minimal.

10.The authentication will not be broken if the attackers or cheaters attempt to modify the higher four bits of each generated shadow image SCi(h,w)because the grayscale pixel value(eight bits)is compressed in step 8.

Regarding Algorithm 3,we comment as follows:

1.Step 1 focuses on the authentication in the shadow image distribution phase,step 2 focuses on the authentication before decoding the secret image,and steps 3-5 focus on the secret image decoding during the secret image decoding phase.The dealers and participants are involved in different phases.

2.In step 1,the distributed shadow image is authenticated by the participant in the shadow image distribution phase to check whether the hash code is altered;thus,our method achieves the authentication of each distributed shadow image.

3.In step 2,each collected shadow image is authenticated by the dealer in the secret image decoding phase to check whether the hash code is altered;thus,our method achieves the ability of a separate shadow image authentication.

4.In step 4,at each position(h,w),to obtainS＇(h,w)we must construct a polynomial to solvea0.

5.In this way,our method achieves bidirectional shadow image authentication without pixel expansion.

6.The decoding process is just like Shamir’s approach except for the authentication phase.

7.Because the ISS algorithm complexity generally considers time complexity in the decoding phase,we analyze the time complexity of Algorithm 3.The decoding phase contains authentication and decoding.The main authentication operations are XOR and the hash function,and thus the main time complexity isO(k)because the hash function is computed once and XOR is the key factor.The main decoding operation is an interpolation,so the main time complexity isO(k(log2k)2).

3.2 Security and performance analyses

Here,we give the performance analyses and security proof of the proposed authentication method.Without loss of generality,the collectedkgrayscale shadow image pixels are denoted by scq1,scq2,···,scqkin the decoding phase.sindicatesS(h,w).

Lemma 1sand scican range from 0 to 255,fori=1,2,···,n.

ProofBecauseP=257,scan range from 0 to 255.Because SCi(h,w)＜P-1,scican range from 0 to 255,fori=1,2,···,n.

Lemma 2sis losslessly decoded with scq1,scq2,···,scqk.

ProofFrom Eq.(6)and by Lagrange interpolation,a0andaiare uniquely determined fori=1,2,···k-1.According to Lemma 1 ands=a0＜P,sis losslessly decoded with scq1,scq2,···,scqk.

Theorem 1Using SCiandkD,the dealer can authenticate whether SCiis fake fori=1,2,···,n.Using SCiandkis,theithparticipant can authenticate whether SCiis fake.

ProofIn step 8 of Algorithm 2,if an attacker intends to guessand,i.e.,the starting and ending plain coordinates for theithparticipant to be hashed,there arepossible coordinates;i.e.,the probability of brute-force guessing the coordinates isThe security essentially depends on the adopted random number generator,whose result is indistinguishable from a random number.The dealer withkDcan generateand,i.e.,the starting and ending plain coordinates for theithparticipant to be hashed.

However,the result of the XOR4LBs operation on the lastithline of SCihas 2Wpossible values;i.e.,the probability of brute-force guessing the hash code is 1/2W,whose security depends on the adopted hash function.However,the dealer receiving SCican extract the hash code.

In this way,using SCiandkD,the dealer can authenticate whether SCiis fake fori=1,2,···,n.

Similarly,theithparticipant can decryptbZ＇ixwith his/her private key to obtainandto authenticate whether SCiis fake,whose security essentially depends on the adopted public key encryption system.

Therefore,our method achieves public key based bidirectional shadow image authentication without pixel expansion.

Lemma 3The secret imageScannot be decoded with anyk-1 or fewer shadow images.

ProofIf anyk-1 equations are constructed in Eq.(6),there are a total ofPsolutions rather than only one for anyk-1 equations in Eq.(6).Finally,the secret imageScannot be decoded with anyk-1 or fewer shadow images.

Note that,although results from Lemma 3 are well known and are the property of a secret-sharing scheme,we provide the proof of their integrity here.

Theorem 2Our method is a valid ISS for a(k,n)threshold with lossless decoding whenn-kis small.

ProofBased on Lemmas 2 and 3,the mentioned conditions for a(k,n)threshold are satisfied.

Because whenkis fixed,nincreases,more requirements must be satisfied,which is further analyzed as follows.LetNRdenote the number of available random values ofa1,a2,···,ak-1in our method.

For each line of the first or lastnlines,;for the other lines,.Thus,the weightedNR=There are enough available random values to guarantee searchability.

Note that the inherent information-theoretic property of secret sharing may be compromised as we introduce our method,which is shown in Theorem 2.

Note that there is one possible security risk.If an attacker only modifies the pixels beyond the two random coordinates,it does not cause the decoding stage authentication to fail because the coordinates and the pixel values between the coordinates in the decoding stage are the same as those in the encoding stage;however,the received shadow image has been altered,in which case it is possible to bypass the encoding stage authentication and complete the modification of the shadow image.We call the possible risk the“beyond-coordinates-issue.”If the attacker modifies too many pixels,it will be detected.If the attacker modifies fewer pixels,it is possible to bypass the authentication although it has little effect on the image.One possible solution to the risk is to take the coordinates to both ends as much as possible;however,there will be a trade-offproblem of brute force guessing.At present,we have not thought of a more suitable solution,so we will continue to study it in the future work.

4 Experimental results and comparisons

In this section,we perform experiments to validate the effectiveness of the proposed public key based bidirectional shadow image authentication method without pixel expansion.Some discussions on our parameters are also provided.Finally,a comparison of illustrations and features with the most related schemes is provided to describe the features of our scheme.

4.1 Experimental settings

In our experiments,all the test images are of the same size,256×256,because there is no pixel expansion in the proposed ISS.More experiments are required to show that our scheme is suitable for general thresholds and different secret images.

RSA-1024 is used as the public key encryption system,SHA-256 is used as the hash function,andmsequence is used for the random number generator.Note that other functions can also be applied to our method.kD=[1 1 0 0 1 0 1 0 1 0 1 0 1 0].

4.2 Image illustration

Fig.8 presents the results of the proposed(k,n)threshold ISS scheme with bidirectional shadow image authentication without pixel expansion,wherek=2,n=2,k1s={36 296 023,42 414 499},k2s={6 980 681,34 960 501},k1p={7,42 414 499},k2p={5,34 960 501},and the input grayscale secret imageSis displayed in Fig.8a.Figs.8b and 8c illustrate the output two shadow images SC1and SC2,respectively.Fig.8d shows the secret image decoded with the two shadow images by Lagrange interpolation,where the secret image is losslessly decoded;i.e.,Fig.8d is the same as the secret image in Fig.8a.A randomly generated fake shadow image,denoted by SC＇1,is shown in Fig.8e.Fig.8f shows the secret image decoded with SC＇1and SC2using Lagrange interpolation,which reveals no information on the secret image and thus fails to decode the secret.

Fig.8 Experimental results of the proposed(k,n)threshold ISS scheme with bidirectional shadow image authentication without pixel expansion,where k=2 and n=2:(a)grayscale secret image S;(bc)two grayscale shadow images SC1 and SC2;(d)grayscale secret image S＇decoded with SC1 and SC2;(e)fake shadow image SC＇1;(f)grayscale secret image S＇decoded with SC＇1 and SC2

We will provide a detailed numerical encoding and authentication process of SC1.The detailed parameters are given in Table 2.

Table 2 Some parameters and their values in Fig.8

The result of the XOR4LBs operation on the lastithline of SCiis equal to HVi,fori=1,2,and thus SC1and SC2are real images.Finally,the real shadow images,i.e.,SC1and SC2,can be authenticated.However,the coordinate extraction offails and thusis fake.In the following experiments,we will omit the detailed parameters to save space.

Fig.9 presents the results of the proposed(k,n)threshold ISS scheme with bidirectional shadow image authentication without pixel expansion,wherek=3,n=4,k1s={5 999 297,30 045 641},k2s={10 558 901,52 880 551},k3s={24 523 229,30 704 257},k4s={37 471 565,46 915 867},k1p={5,30 045 641},k2p={5,52 880 551},k3p={5,30 704 257},k4p={5,46 915 867},and the input grayscale secret imageSis displayed in Fig.9a.Figs.9b-9e present the four shadow images.Figs.9f-9i illustrate the secret images decoded with two or more shadow images using Lagrange interpolation,where almost only the firsttthshadow images are used to save space.From Figs.9f-9i,the secret image decoded with any three or more shadow images is lossless,while no part of the secret image with two or fewer shadow images is recognized.A randomly generated fake shadow image,denoted by SC＇1,is illustrated in Fig.9j.Figs.9k-9n illustrate the secret imagesS＇decoded with SC＇1and another one or more shadow images using Lagrange interpolation,which reveals no information on the secret image and thus fails to decode the secret.

Fig.9 More experimental results of the proposed(k,n)threshold ISS scheme with bidirectional shadow image authentication without pixel expansion,where k=3 and n=4:(a)grayscale secret image S;(b-e)grayscale shadow images SC1,SC2,SC3,and SC4;(f-i)grayscale secret image S＇decoded with two or more shadow images;(j)fake shadow image SC＇1;(k-n)grayscale secret image S＇decoded with SC＇1 and the other one or more shadow images

Based on the above-mentioned experimental results,we conclude the following:

1.Each shadow image has no pixel expansion or cross-interference with the secret image.

2.No secret information is leaked with fewer thankshadow images,demonstrating the security of the proposed ISS.

3.The secret image is losslessly decoded with anykor more shadow images.

4.A separate shadow image is provided to achieve authentication.

5.An ISS scheme with bidirectional shadow image authentication without pixel expansion for a general(k,n)threshold is achieved,where 2≤k≤nandn-kis small.

4.3 Parameter analyses

We discuss the values of entropy,encoding time,andNRforkandnbecausekandnare important in our method,where the entropy of SC1is given as follows:

whereymeans a pixel value,and its statistical probability in an imageYis denoted by Prob(y).

Here,xindicates that the lowxbits of the shadow image is XORed,where in our introduced methodx=4.We also state why we setx=4.

The grayscale secret image shown in Fig.8 is used in our study.

Fig.10 presents the entropy,encoding time,andNRcurves fornwhenk=3,where we set the theoretical entropy 8,from which we know the following:

Fig.10 Entropy(a),encoding time(b),and NR(c)curves for n when x=4,k=3

1.The entropy is almost the same asnincreases and the experimental entropy fits well with the perfect theoretical value.This demonstrates that the shadow image is almost random,that our method is secure,and that our analyses are effective.

2.The encoding time is a monotonically increasing function ofn.Asnincreases,the number of screening operations increases,and thus the encoding time increases.

3.NRis a monotonically decreasing function ofn.Asnincreases,the number of screening requirements increases,and hence the available random values ofa1,a2,···,ak-1decrease.

Fig.11 shows the entropy,encoding time,andNRcurves forkwhenn=8,from which we know the following:

Fig.11 Entropy(a),encoding time(b),and NR(c)curves for k when x=4,n=8

1.The entropy is almost the same askincreases,and the experimental entropy fits well with the perfect theoretical value.This demonstrates that the shadow image is almost random,that our method is secure,and that our analyses are effective.

2.The encoding time has a close value askincreases.There are enough available random values ofa1,a2,···,ak-1,and thus it is easy to screen the available values.

3.NRis a monotonically increasing function ofkand increases dramatically whenk≥7.The space of available random values ofa1,a2,···,ak-1increases,askincreases.

Figs.12 and 13 show why we setx=4,wherek=2.

Fig.12 Entropy(a)and encoding time(b)curves for x when k=2,n=4,NR=249

Fig.13 Entropy(a)and encoding time(b)curves for x when k=2,n=6,NR=245

1.The values 3,4,and 5 are the alternative candidates ofxbecause their entropy is larger.

2.Considering the encoding time,x=4 represents an acceptable time.

3.In our method,we setx=4 to balance security and efficiency.

4.4 Comparison with related schemes

We compare our method with that of Yan et al.(2020a)using experiments and features in which the same secret image as shown in Fig.9a and the(2,3)threshold can be used.We choose the scheme of Yan et al.(2020a)for comparison because their scheme has a separate shadow authentication ability for a(k,n)threshold,which is also based on a polynomial.

Fig.14 displays the results of Yan et al.(2020a),wherek=2 andn=3,and the grayscale secret imageSis shown in Fig.14a.Fig.14b is a binary authentication image.Figs.14c-14e illustrate the three shadow images SC1,SC2,and SC3.Fig.14f is the output additional binary image preserved by the dealer for authentication.Fig.14g presents the authentication result of SC1by the dealer.Fig.14h presents the secret image decoded with the first two shadow images using Lagrange interpolation.Fig.14h shows that the decoded secret image with any two or more shadow images is lossless.

Fig.14 Experimental results of Yan et al.(2020a),where k=2 and n=3:(a)grayscale secret image S;(b)binary authentication image;(c-e)shadow images SC1,SC2,and SC3;(f)additional binary image preserved by the dealer for authentication;(g)authentication result of SC1 by the dealer;(h)grayscale secret image S＇decoded with SC1 and SC2

Fig.15 shows the results of our method with the same parameters.

Fig.15 Our experimental results,where k=2 and n=3:(a)grayscale secret image S;(b-d)shadow images SC1,SC2,and SC3;(e)grayscale secret image S＇decoded with SC1 and SC2

According to Figs.14 and 15,the schemes of Yan et al.(2020a)and ours are compared as follows:

1.Both our scheme and the scheme of Yan et al.(2020a)have the features of no pixel expansion,dealer-participatory separate shadow image authentication ability,(k,n)threshold,lossless decoding,and the use of a polynomial.

2.The scheme of Yan et al.(2020a)can authenticate the shadow image only in the decoding phase,i.e.,unidirectional authentication,whereas our method can authenticate the shadow image in both distributing and decoding phases,i.e.,bidirectional authentication.

3.The scheme of Yan et al.(2020a)requires an additional image preserved by the dealer to achieve authentication,whereas our method does not.

4.A little information leakage may appear in the shadow image in the scheme of Yan et al.(2020a)because they use only the MSB in their scheme,whereas no information leakage appears in our method because we setx=4 to balance security and efficiency.

5.Only a binarization operation is used to achieve authentication in the scheme of Yan et al.(2020a).Thus,their scheme has lower computational cost than ours.

We compare the proposed method with more related studies(Liu YJ and Chang,2018;Liu YX et al.,2018b;Jiang et al.,2020;Yan et al.,2020a)in terms of features.

Feature comparisons between the proposed method and related methods are presented in Table 3.

Table 3 Feature comparisons with related methods

Compared with conventional schemes,the proposed method with bidirectional shadow image authentication without pixel expansion achieves bidirectional separate shadow image authentication,lossless decoding,no pixel expansion,and no auxiliary information,and thus outperforms traditional schemes.

5 Conclusions

The main contribution of this study is the introduction of an image secret sharing(ISS)scheme with bidirectional shadow image authentication with no pixel expansion,lossless decoding,and no auxiliary information.The public key system and hash function were first introduced into the ISS to achieve admirable bidirectional shadow image authentication without pixel expansion or additional information,except for the secret key of the dealer and the public/private keys of participants.Theoretical analyses and experimental examples demonstrated the effectiveness of our method.The proposed ISS can losslessly decode secret images with bidirectional shadow image authentication without pixel expansion.We performed experiments and feature comparisons with related competitive schemes to show the advantages of our method.In the future,we willfocus on the use of other ISS principles,public key systems,and hash functions in our method to obtain more admirable features.In addition,we will study the ISS security analysis methods and consider the“beyond-coordinates-issue.”

Contributors

Xuehu YAN designed the research.Longlong LI processed the data.Jia CHEN drafted the paper.Lei SUN revised and finalized the paper.

Compliance with ethics guidelines

Xuehu YAN,Longlong LI,Jia CHEN,and Lei SUN declare that they have no conflict of interest.

Data availability

The data that support the findings of this study are available from the corresponding author upon reasonable request.