A hierarchical threshold secret image sharing
Cheng Guo a ,Chin-Chen Chang b ,c ,⇑,Chuan Qin b
a
Department of Computer Science,National Tsing-Hua University,Hsinchu 30013,Taiwan,ROC
b
Department of Information Engineering and Computer Science,Feng Chia University,No.100Wenhwa Rd.,Seatwen,Taichung 40724,Taiwan,ROC c
Department of Biomedical Imaging and Radiological Science,Chinese Medical University,Taichung 40402,Taiwan,ROC
a r t i c l e i n f o Article history:
Received 31March 2011
Available online 1October 2011Communicated by S.Sarkar Keywords:
Hierarchical threshold Distortion-free
Secret image sharing Access structure
a b s t r a c t
In the traditional secret image sharing schemes,the shadow images are generated by embedding the secret data into the cover image such that a sufficient number of shadow images can cooperate t
o recon-struct the secret image.In the process of reconstruction,each shadow image plays an equivalent role.However,a general threshold access structure could have other useful properties for the application.In this paper,we consider the problem of secret shadow images with a hierarchical threshold structure,employing Tassa’s hierarchical secret sharing to propose a hierarchical threshold secret image sharing scheme.In our scheme,the shadow images are partitioned into several levels,and the threshold access structure is determined by a sequence of threshold requirements.If and only if the shadow images involved satisfy the threshold requirements,the secret image can be reconstructed without distortion.
Ó2011Elsevier B.V.All rights reserved.
1.Introduction
A secret sharing scheme is a technique to share a secret among a group of participants.The secret data can be divided into several pieces,called secret shadows,which are distributed to the partici-pants.If enough participants cooperate to reconstruct the secret data and pool their secret shadows together,the secret data can be reconstructed.
In 1979,the first (t ,n )threshold secret sharing schemes were pro-posed by Shamir (1979)and Blakle
y (1979),based on Lagrange interpolating and liner project geometry,respectively.In 1995,based on the concept of threshold secret sharing,Naor and Shamir (1995)introduced visual cryptology,or the visual secret sharing scheme (VSS scheme).In the (t ,n )VSS schemes (Yang,2004;Wang et al.,2007;Chang et al.,2009;Lin and Wang,2010),the secret data is an image comprised of black and white pixels that is encoded into n shadow images,and the secret image can be reconstructed only by stacking t of the shadow images;no information about the secret im-age can be obtained from t À1or fewer shadow images.However,in this kind of visual secret sharing scheme,the shadow images are meaningless,which tends to call attention to them.In 2003,Thien and Lin (2003)utilized the steganography approach to embed the secret image into a cover image to generate the shadow images.In their scheme,the shadow images are meaningful and the distortion between the cover image and the shadow images is imperceptible.
Since then,the secret image sharing schemes (Lin and Tsai,2004;Wu et al.,2004;Yang et al.,2007;Chang et al.,2008;Zhao et al.,2009;Lin et al.,2009;Eslami et al.,2010;Lin and Chan,2010)have been extensively developed to meet the requirements of our daily lives.In 2004,Lin and Tsai (2004)proposed a secret image sharing scheme with steganography and authentication,in which the sha-dow images are meaningful,while the reconstructed secret image is distorted slightly.I
n 2007,Yang et al.(2007)improved Lin and Tsai’s scheme by making it possible to restore a distortion free secret image,but their scheme reduces the visual quality of the shadow images and increases the risk of their being deceived by malicious intruders.In 2009,Lin et al.(2009)employed the modulus operator to embed the secret image into a cover image,where each partici-pant can obtain a meaningful shadow image with high visual qual-ity,the authorized participants can detect intruders,and the secret image and the cover image can be recovered losslessly.In 2010,Lin and Chan (2010)proposed a new secret sharing scheme that achieves an excellent combination of embedding capacity and the visual quality of shadow images.In addition,their scheme can reconstruct the secret image and the cover image without distortion.However,in all of these schemes,all shadow images are equal in terms of privileges and authority in the process of reconstructing the secret image.In this paper,we consider a special situation in which the shadow images may be not equal.We achieve a hierar-chical threshold access structure by introducing Tassa’s threshold secret sharing scheme,and we present a novel hierarchical thresh-old secret image sharing scheme.
Secret sharing schemes have been extensively studied,and se-cret image sharing and its many variations form an important re-search direction.In 2007,Tassa (2007)proposed a hierarchical threshold secret sharing scheme.Tassa’s scheme is based on the
0167-8655/$-see front matter Ó2011Elsevier B.V.All rights reserved.doi:10.1016/j.patrec.2011.09.030
⇑Corresponding author at:Department of Information Engineering and Com-puter Science,Feng Chia University,No.100Wenhwa Rd.,Seatwen,Taichung 40724,Taiwan,ROC.Tel.:+886424517250x3790;fax:+886427066495.
E-mail addresses:guo8016@gmail (C.Guo),alan3c@gmail (C.-C.Chang),qin@usst.edu (C.Qin).
Birkhoff interpolation.In their scheme,the secret is shared by a set of participants partitioned into several levels,and the secret data can be reconstructed by satisfying a sequence of threshold ,it has at least t0participants from the highest level,as well as at least t1>t0participants from the two highest levels and so forth).There are many real-life examples of hierarchical thresh-old schemes.Consider the following example.According to a grad-uate school’s policy,a graduate who wants to apply for a postgraduate position must have letters of recommendation.As-sume that the graduate school’s policy concerning such recom-mendations is that the candidate must have at least two recommendations from professors and at leastfive recomm
enda-tions from a combination of professors and associate professors. In this scenario,the professor is the highest level,the associate pro-fessor is the second-highest level,the corresponding threshold val-ues are t0¼2and t1¼5,and the shadows of a higher level can substitute for those of a lower level.In this example,recommenda-tions from two professors and three associate professors,three professors and two associate professors,four professors and one associate professor,orfive professors are all acceptable.
The same situation also appears in the sharing of secret images. Inspired by the hierarchical secret sharing scheme,we construct a hierarchical threshold secret image sharing scheme.
The existing secret image sharing schemes(Lin and Tsai,2004; Wu et al.,2004;Yang et al.,2007;Chang et al.,2008;Zhao et al., 2009;Lin et al.,2009;Eslami et al.,2010;Lin and Chan,2010)have tried to improve the visual quality of the shadow images so the sus-picions of malicious intruders won’t be aroused.Two of the most popular steganographic methods are the least significant bits (LSB)replacement and the modulus operation.Shamir’s(t,n) threshold scheme is an ingenious method with which to share se-cret data among n participants.Traditional secret image sharing schemes(Lin et al.,2009;Lin and Chan,2010)usually transformed the secret image pixels into base-m representation,s1;s2;...;s M
S
ÂN S Âd log m255e,where M SÂN S denotes the size of the secret image, and then constructed a Lagrange interpolation polynomial f(x)by
using the s1;s2;...;s M
S ÂN SÂd log m255e
as the polynomial coefficients.In
order to make the shadow images meaningful for the purposes of camouflage—that is,to diminish the distortion of the shadow images—they utilized the modulus operator to embed secret data into the pixel of the cover image.
However,in Tassa’s scheme,the hierarchical threshold access structure can work so long as the modulus p is far greater than the threshold t,so it is difficult to combine the existing secret im-age sharing schemes based on the modulus operation directly with Tassa’s hierarchical threshold access structure.Therefore,how to combine the hierarchical threshold access structure proposed by Tassa(2007)with steganographic methods is our scheme’s main challenge.We also need to guarante
e that the secret image can be reconstructed losslessly.
To the best of our knowledge,no hierarchical secret image shar-ing schemes have been proposed in the literature to date.Since we believe that the application of secret image sharing in groups with hierarchical structure has good prospects,we provide a novel hier-archical threshold secret image sharing scheme.
In our scheme,the n shadow images generated from the secret image and the cover image are partitioned into several levels such that each level has a certain number of shadow images and a cor-responding threshold.The secret image can be reconstructed only by meeting a sequence of threshold requirements.
The novel characteristic of the proposed scheme is not available in the existing mechanisms,so the proposed scheme has the potential to work in many applications.In addition to the unique hierarchical threshold characteristic,our proposed scheme has three key characteristics:1.The secret image can be retrieved losslessly.
2.The scheme solves the problems of overflow and underflow.
3.Unlike the traditional secret image sharing schemes in which
the embedding capacity is proportional to the increase of t, the capacity of the embedded secret data is stable and large.
2.Review of Tassa’s hierarchical threshold secret sharing scheme
In case of hierarchical threshold secret sharing,the set of participants is partitioned into some levels P0,P1,...,P m and the access structure is then determined by a sequence of threshold requirements t0,t1,...,t m according to their hierarchy.Tassa’s method(2007)for hierarchical threshold secret sharing is based on Birkhoff interpolation.In this section,we briefly introduce Tassa’s hierarchical threshold secret sharing scheme.Assume that there are n participants and one dealer responsible for generating the secret shadows and distributing them to the participants.
1.The dealer generates the polynomial F(x)of degree at most
t mÀ1over GF q,FðxÞ¼Sþa1xþa2x2þÁÁÁþa t
mÀ1
x t mÀ1,where S is the shared secret data.
2.An element i e GF q is assigned to the participant i,for all
16i6n.
3.For any level j,each participant i from the j th level will receive
the secret shadow F t jÀ1ðiÞ,where F t jÀ1ð:Þis the(t jÀ1)th derivative of F(x)and t0=0.
acei4.In the reconstruction phase,the participants can cooperate to
reconstruct the shared secret data by using Birkhoff interpolation.
3.The proposed scheme
Given a shared secret image S and a cover image O,the dealer can generate n shadow images p i,for i=1,2,...,n.In the proposed scheme,the n shadow images do not have equal status;instead, the secret image is shared among n shadow images that are parti-tioned into several levels.Based on Tassa’s definition(Tassa,2007), we define the hierarchical secret image sharing as follows:
Definition1.Let P be a set of n shadow images and assume that P
is composed of levels;that is,P¼[m
i¼0
P i,where P i\P j¼/for all i–j and i,j e[0,m].Let t=f t i g m i¼0be a monotonically increasing sequence of integers.Then the(t,n)hierarchical threshold access structure is
C¼V&P:V\
[i
j¼0
P j
!
P t i;8i2f0;1;...;m g
()
:
3.1.Initialization procedure
First,the dealer constructs n secret shadow images and divides these n shadow images into(m+1)levels P={P0,P1,...,P m} according to the real-life situation.Then the dealer sets a sequence of threshold values{t0,t1,...,t m},0<t0&<t m,where t=t m is the overall number of shadow images that are required for recov-ery of the secret image,and assumes that
p
1
;p
2
;...;p
l0
2P0;
p
l0þ1
;p
l0þ2
;...;p
l1
2P1;
...
p
l mÀ1þ1
;p
l mÀ1þ2
;
...;p
n
2P m;
84 C.Guo et al./Pattern Recognition Letters33(2012)83–91
where p
i
;06i6n denotes the i th shadow image and P i;06i6m denotes the set of shadow images of the i th level.The secret image can be reconstructed by satisfying a sequence of threshold require-ments,such as that it has at least t0secret shadow images from the highest level as well as at least t1>t0secret shadow images from the two highest levels and so forth.
Assume that the cover image O has MÂN pixels, O={o i|i=1,2,...,(MÂN)},and secret image S has M SÂN S pixels.
Step1:The dealer selects a large prime modulus p.
Step2:The dealer obtains all pixels of the secret image S, denoted as S¼f s j j j¼1;2;...;ðM SÂN SÞg,where s j e[0,255].
3.2.Secret image sharing procedure
The procedure consists of two phases:(1)the sharing phase, and(2)the embedding phase.
3.2.1.Sharing phase
Without loss of generality,assume that we want to embed s0;s1;s2;...;s tÀ1into the cover image to generate n shadow images using a hierarchical access structure.The dealer performs the fol-lowing steps:
Step1.Construct a(tÀ1)th-degree polynomial FðxÞ¼s0þs1x þÁÁÁþs tÀ1x tÀ1mod p,where p is a large prime,t=t m,and s0,s1,s2,...,s tÀ1denote the pixel values of the shared secret image.
Step2.For thefirst level shadow images,utilize the(tÀ1)th-degree polynomial F(x)to generate the shadow images.The shadow images of other levels are processed in the following manner.The shadow images of the i th level in the hierarchy can be generated by using the polynomial F t iÀ1ðxÞ,where
F t iÀ1ðxÞis the(t iÀ1)th derivative of F(x).
For example,there are three levels in the shadow images, P=P0[P1[P2.Assume that the threshold sequence requirements are t0=2,t1=4and t2=7;that is,the secret image can be recon-structed if and only if there are at least seven shadow images,of which at least four are from P0[P1,and at least two are from P0. In this example,we should construct a6th-degree polynomial FðxÞ¼s0þs1xþÁÁÁþs6x6mod p:First,the dealer utilizes F(x)to generate the shadow images that belong to P0.Since t0=2,the sec-ond level shadow images are generated by using the polynomial F00ðxÞ,and since t1=4,the shadow images of the lowest level can be computed using the polynomial F(4)(x).
3.2.2.Embedding phase
In order to diminish the distortion of the shadow images,most existing secret image sharing schemes have utilized the modulus operator to embed the secret image data into the pixels of the cov-er image.However,in the proposed scheme,in keeping with Tas-sa’s scheme,we calculate the shadow images in afinitefield of size p,which is a large prime,so we need to develop a new method in order to embed the shadow data into the cover image.
Lin and Chan’s scheme(Lin and Chan,2010)formed a camou-flaged pixel usingyjp
Q i¼b o i=k cÂk;
q i ¼Q iþy i;
ð1Þ
where Q i is the quantized value of o i,and q i represents the i th cam-ouflaged pixel.Inspired by Lin and Chan’s scheme,we also use a quantization operation to embed the secret data.However,in Lin and Chan’s scheme,all operations are in afield modulo a small prime number r,such as5,7,or11,so y i can be directly embedded into a pixel of the cover image without causing a large distortion.However, in our scheme,the modulus p must be far greater than the threshold t,so we obtain a large integer y i=F(i)by feeding an integer i,i2[1,n]into F(x)and need to use r pixels of shadow images to rep-resent shadow data y i.In the traditional secret image sharing schemes,the dealer feeds a secret key or a unique ID i into the poly-nomial F(x)to obtain y i;and in order to facilitate the embedding of y i into the shadow image,the polynomial F(x)can modulo a small prime.However,in the proposed scheme,the polynomial F(x)needs to modulo a large prime,so we need more pixels to represent y i. Obviously,the larger y i is,the more pixels are needed to represent y i.
at mtTherefore,in order to minimize y i,we feed a series of integers i, for i=1,2,...,n into F(x)instead of feeding ID i.In order to guaran-tee that r pixels are sufficient to represent y i,we maximize the shared secret data s i and assume that all s i=255,for i=1,2,...,n.
Wefirst talk about how to generate the highest level shadow images.Assume that the highest level P0includes l0shadow images p
1
;p
2
;...;p
l0
,and the selected r camouflage pixels in the cover im-age O are o i,o i+1,...,o i+rÀ1.In the embedding phase,we perform the following steps:
Step1.Assume that we want to generate the shadow image p i,i e[1,l0].The dealerfirst computes y i by feeding i into F(x).
Step2.We utilize Lin and Chan’s method(2010)to generate and camouflage the shadow images.Firstly,we convert the secret data y i into the r-ary notational system.In Lin and Chan’s scheme(2010),Eq.(1)may lead to an overflow situation.There-fore,we must ensure that b o i=k cÂkþr6255.Meanwhile,the parameters(k,r)can also affect the quality of the shadow images and the embedding capacity.The greater the value r is,the larger the embedding capacity is.However,the value r may increase the gap between adjacent pixel values,especially for the smooth image.Therefore,the greater the value r is,the less smooth the shadow image is.In regard to the different cov-er images,if the cover image is smooth,we need to select a small r.On the contrary,if the cover image is rich,we can select
a great r aiming at improving the embedding capacity.In order
to simplify the proposed method,in this paper,we let k=10and transform the y i into base-5representation.For instance,if y i=1304,we obtain y i=(2,0,2,0,4)5.This pair(10,5)can effec-tively avoid the overflow problem since b255=10cÂ10þ5
6255.And,we need r¼d log
5
Fðl0Þe pixels of the shadow image to represent y i.As to the i th level,r i can be computed by r i¼d log5F t iÀ1ðl iÞe;where F t iÀ1ðl iÞdenotes the(t iÀ1)th derivative of the function F(x).
Step3.Without loss of generality,assume that we use r pixels
p
ij
;j¼1;2;...;r of the shadow image p i to represent y i as follows:
p
i1
¼b o i=10cÂ10þy i1;
p
i2
¼b o iþ1=10cÂ10þy i2;
...
p
ir
¼b o iþrÀ110cÂ10þy ir;
ð2Þ
where each y
ij
;j¼1;2;...;r,denotes y
i
’s base-5representation.
Step4.By repeating Steps1–3,the dealer can camouflage all se-cret data y i into the cover pixels,and by feeding i,for i=1,2,...,l0into F(x),the dealer can obtain thefirst level sha-dow images.
As to the shadow images at the second highest level,since the threshold values are{t0,t1,...,tm},the dealer uses the polynomial F t0ðxÞto generate the shadow data yi,and so forth,so the shadow images of the i th level in the hierarchy are computed using the polynomial F t iÀ1ðxÞ.
C.Guo et al./Pattern Recognition Letters33(2012)83–9185
The generation process for the other levels of shadow images is the same as that of the highest level except that different polyno-mials are used.Repeat the above steps until all shadow images of various levels are generated.Fig.1displays theflowchart of the se-cret image sharing scheme.
3.3.Secret image retrieving procedure
In the traditional secret image sharing schemes,given any t sha-dow images,the shared secret image can be reconstructed.In our scheme,according to Tassa’s threshold access structure,given sha-dow images must satisfy a sequence of threshold requirements.In order to extract the secret digi
ts,the polynomial F(x)must be reconstructed by retrieving the shadow data y
i
from the shadow images p i’s.The same method is used for different levels of shadow images.The details are as follows:
Step1.Compute y i by
y
i
¼y i1jj jj y ir;ð3Þ
where y
ij
¼p ij mod5,for j=1,2,...,r,and p ij denotes the j th pixel value of the i th shadow image,for i=1,2,...,t m.
Step2.Collect enough t pairs(i,yi)’s to satisfy the hierarchical threshold access structure and employ the Birkhoff interpola-tion to reconstruct the(tÀ1)degree polynomial F(x).
Step3.Extract the corresponding t coefficients s0,s1,s2,...,s tÀ1.
Step4.Repeat Steps1–3until all secret data is extracted.
Step5.Reconstruct the secret image.
4.Experimental results and analysis
This section describes some experimental results in order to demonstrate the characteristics of the proposed scheme.
We perform experiments for n=10.A secret image can be gen-erated in ten shadow images,and the ten shadow images are par-titioned into three levels.Assume that thefirst(highest)level has three shadow images,the second level has three shadow images, and the third(lowest)level has four shadow images.Assume a se-quence of threshold requirements t¼ðt0;t1;t2Þ¼ð2;4;7Þ;that is, the secret image can be reconstructed if and only if a subset of sha-dow images has at least seven shadow images,of which at least four are from thefirst two levels and at least two are from thefirst lev
el.
4.1.Simulation results
The peak signal-to-noise ratio(PSNR),defined in Eq.(4),can be used to measure the distortion of the shadow images after the se-cret data have been embedded into the cover
image. Fig.1.The diagram of the secret image sharing scheme.
福田论坛PSNR¼10log
102552 MSE
!
dB:
The mean square error(MSE)between the pixels and the shadow image is defined as
MSE¼
1
MÂN
X
浙江树人
大学后勤MÂN
j¼1
ðp jÀp0
j
Þ2;
where p j is the original pixel value and p0
j
is the
dow image.
We usefifteen grayscale images with size
the test images,as shown in Fig.2,and the
Airplane is set to256Â256pixels,as shown in
Table1displays the PSNR value of the
using the proposed scheme.Although the pixel
images of the proposed scheme are slightly
existing secret image sharing methods,it is
what we use as the cover image,the PSNR values
always maintain a steady level and are within
more,we obtained a new access structure that
cations,and the distortion between the shadow
image is imperceptible by visual perception.
In order to demonstrate the visual perception of the shadow
images,we use Peppers as the cover image with size512Â512pix-els and Airplane as the secret image with size256Â256pixels.If the secret images involved meet the hierarchical threshold access structure,our method can reconstruct them without distortion. Fig.4(a)and(b)shows the cover image and the extracted secret image,respectively.
Fig.5(a)–(j)display ten shadow images of Peppers that are partitioned into three levels.Since the distortion between the cover image and the shadow images is slight,we can success-fully conceal the embedded the secret image data’s existence from intruders.
(a) Bird (b)Woman (c) Lake (d) Man (e)Tiffany
(f)Peppers (g)Lena (h)Fruits(i)定位销
Baboon(j)
Airplane
(k) Couple (l) Crowd (m) Cameraman(n) Boat(o) House
Fig.2.The test images.
Fig.3.The secret image.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议