Step Construction of Visual Cryptography Schemes-FWx, Information Forensics and Secu

[ Pobierz całość w formacie PDF ]
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 5, NO. 1, MARCH 2010
27
Step Construction of Visual Cryptography Schemes
Feng Liu, Chuankun Wu
, Senior Member, IEEE
, and Xijun Lin
ABSTRACT—
Two common drawbacks of the visual cryptography
scheme (VCS) are the large pixel expansion of each share image
and the small contrast of the recovered secret image. In this paper,
we propose a
step construction
to construct VCS
and VCS
for general access structure by applying (2,2)-VCS recursively,
where a participant may receive multiple share images. The pro-
posed step construction generates VCS
and VCS
which
have optimal pixel expansion and contrast for each qualied set
in the general access structure in most cases. Our scheme applies
a technique to simplify the access structure, which can reduce the
average pixel expansion (APE) in most cases compared with many
of the results in the literature. Finally, we give some experimental
results and comparisons to show the effectiveness of the proposed
scheme.
INDEX TERMS—
Secret sharing, step construction, visual cryptog-
raphy.
i.e., the
XOR
operation can also be achieved by the operation
OR
and
NOT
, which is implemented by using a copy machine with
the reversing function.
In the following, we will consider the VCS both under the op-
erations
XOR
and
OR
. To simplify the discussion, the notion VCS
means a visual cryptography scheme regardless of the under-
lying operation, and we use the notations VCS and VCS
to denote the visual cryptography scheme with particular under-
lying operations
XOR
and
OR
respectively.
Traditionally, visual cryptography schemes are evaluated by
two parameters: the pixel expansion, which is the number of
subpixels that each pixel of the original secret image is encoded
into, and the contrast, which reects the visual quality of the re-
covered secret image. From the point of view of the participants,
the pixel expansion is expected to be as small as possible, and
the contrast is expected to be as large as possible. Many studies
focused on improving the properties of pixel expansion and con-
trast [8]–[11], [7], [12]. Also studies have tried to trade the pixel
expansion for the contrast [13].
In this paper, we propose a step construction which generates
VCS and VCS that, in most cases, have optimal pixel
expansion and contrast for each qualied set in the general ac-
cess structure. Because each participant in the proposed scheme
may have multiple share images with different pixel expansions,
so we introduce the notion
average pixel expansion
(APE, for-
mally dened in Section III). The proposed scheme can also re-
duce APE in many cases compared with the known results in the
literature. With our
step construction
, the VCS with general ac-
cess structure can be constructed only by applying a (2,2)-VCS
recursively, for both the
OR
and
XOR
operations. This result is
important for the reason that the construction of VCS for
the general access structure was once thought as impossible be-
fore. Finally, we give the experimental results and comparisons
to show the effectiveness of our scheme compared to the known
results in [14], [2].
The rest of this paper is organized as follows. In Section II, we
give some denitions about the VCS. In Section III, we propose
the
step construction
of VCS for the general access structure.
In Section IV, we give some experimental results and compar-
isons to show the effectiveness of our scheme, and the paper is
concluded in Section V.
I. I
NTRODUCTION
was rst introduced by Naor and Shamir. The idea of the
visual cryptography model proposed in [1] is to split a secret
image into two random share images (printed on transparencies)
which separately reveal no information about the original secret
image. The secret image is composed of black and white pixels.
The original secret image can be recovered by superimposing
the two share images together. The underlying operation of such
a scheme is the logical operation
OR
. Generally, a -VCS
takes a secret image as input, and outputs share images that
satisfy two conditions: First, any out of share images can
recover the secret image; second, any less than share images
cannot get any information about the secret image.
Similar models of visual cryptography with different under-
lying operations have been proposed, such as the
XOR
operation
introduced in [2]–[6], and the
NOT
operation introduced in [7],
which uses the reversing function of the copy machines. Denote
as the
XOR
operation, as the
OR
operation, as
the
AND
operation, and as
NOT
operation; then, we have the
following relation between the operations
XOR
and
OR
:
Manuscript received June 03, 2009; accepted October 09, 2009. First pub-
lished December 01, 2009; current version published February 12, 2010. This
work was supported by China national 973 Project 2007CB807902 and Project
2007CB311202, by NSFC Grant 60873260 and Grant 60903210, and by China
National 863 Project 2009AA01Z414. The associate editor coordinating the re-
view of this manuscript and approving it for publication was Prof. Ton Kalker.
F. Liu and C. Wu are with The State Key Laboratory of Information Security,
Institute of Software, Chinese Academy of Sciences, Beijing 100190, China
(e-mail: liufeng@is.iscas.ac.cn; ckwu@is.iscas.ac.cn).
X. Lin is with the Department of Computer Science and Technology, Ocean
University of China, Qingdao 266100, China (e-mail: linxj77@is.iscas.ac.cn).
Digital Object Identier 10.1109/TIFS.2009.2037660
II. P
RELIMINARIES
Suppose all the participants of an access structure form a set
. The specication of all qualied and for-
bidden subsets of participants constitutes an access structure
. Denote as the set of qualied sets (the par-
ticipants in a qualied set can collaboratively recover the secret
image), and as the set of forbidden sets (the participants in
a forbidden set cannot recover the secret image). Obviously, we
have
. In this paper, we only consider access
1556-6013/$26.00 © 2010 IEEE
AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:48:23 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.
T
HE basic principle of visual cryptography scheme (VCS)
28
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 5, NO. 1, MARCH 2010
structures with , where is the power set
of , i.e., the set of all the possible subsets of . The set
is monotone because of that, if part of the participants in a set
can recover the secret image, then obviously all the
participants in can recover the secret image as well. We de-
ne
is denoted by the number 1. We notice that the denitions of
VCS under
OR
and
XOR
operation are quite similar. We will give
some denitions about visual cryptography under the operation
“ ”, which can either be the
OR
operation such as in [1] or the
XOR
operation such as in [2]. In this paper, we use the subscripts
and for emphasizing different underlying operations
when necessary.
Because the proposed constructions in this paper are all based
on the traditional
and
-VCS, we rst give the denition of the
traditional -VCS.
For a vector , denote as the Hamming
weight of the vector , i.e., the number of nonzero coordinates
in .A -VCS, denoted by , consists of two col-
lections of binary matrices and . To share a white
(respectively, black) pixel, a dealer (the one who sets up the
system) randomly chooses one of the matrices, called a
share
matrix
,in (respectively, ) and distributes its rows (rep-
resenting a pattern of subpixels in the share image) to the
participants of the scheme, i.e., giving row to participant
. More precisely, we give a formal denition of
-VCS as follows.
Denition 1:
Let
We call
the minimal qualied access structure, and a subset
is called the minimal qualied set. We call
the
maximal forbidden access structure, and a subset
is called the maximal forbidden set. For any , dene
. We call the
closure
of . Since is monotone, then .
This means that the qualied access structure and the min-
imal qualied access structure are determined by each other.
Similarly, and can be determined by each other as
well. Furthermore, because , we have that
and can be determined by each other. So when we dis-
cuss a general access structure, we only need to give discussions
based on its minimal qualied access structure
and be nonnegative integers satis-
fying
. The two collections of binary matrices
constitute a visual cryptography scheme
-VCS
in the fol-
if there exist a value and satises:
1) (Contrast) Any participants can recover the secret image
by stacking (the “ ” operation) their share images. More
precisely, for any , the stacking (the “ ” operation)
of any out of rows of is a vector that satises
, whereas for any ,wehave .
2) (Security) Any less than participants have no information
about the secret image. More precisely, for any
in with , the two collections
of matrices , , obtained by restricting
each matrix in ,torows , are
indistinguishable in the sense that they contain the same
matrices with the same frequencies.
In the above denition, is called the
pixel expansion
of the
scheme, and each secret pixel is represented by subpixels in
the recovered secret image. We denote and as the
pixel expansions under the operation
OR
and
XOR
, respectively.
The dened above is called the
contrast
and is related to
the visual quality of the recovered secret image. For different
operations
OR
and
XOR
, we use the notations and ,
respectively. In fact, there are several denitions about contrast
in the literature; we use the simple one to simplify the discus-
sion, and this denition of contrast has also been used in [1],
[14], etc.
The implementation of VCS has two phases: the distribution
phase and the reconstruction phase. In the distribution phase,
the dealer generates all the share images and distributes them
to the participants; in the reconstruction phase, the participants
reconstruct the secret image by stacking a qualied set of share
images.
The (2,2)-VCS, for
OR
and
XOR
operations, respectively, is as
follows:
lowing of this paper.
Particularly, we call a qualied set
that has the
largest cardinality the
maximum qualied set
of
. Formally,
the maximum qualied set satises
. Note that, the maximum qualied set of may not be
, and there may be several maximum qualied sets in .
It should be pointed out that, the threshold access structure is a
special case of the general access structure, because a threshold
access structure is a general access structure with the fol-
lowing constraints:
and
In a VCS, there is a secret image which is encrypted into
some share images. The secret image is called the
original secret
image
for clarity, and the share images are the encrypted images
(and are called the transparencies if they are printed out). When
a qualied set of share images (transparencies) are stacked to-
gether properly, it gives a visual image which is almost the same
as the original secret image; we call this the
recovered secret
image
. In the case of black and white images, the original se-
cret image is represented as a pattern of black and white pixels.
Each of these pixels is divided into subpixels which themselves
are encoded as black and white to produce the share images. The
recovered secret image is also a pattern of black and white sub-
pixels which should visually reveal the original secret image if
a qualied set of share images is stacked.
In this paper, we will focus on the black and white images,
where a white pixel is denoted by the number 0 and a black pixel
AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:48:23 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.
LIU
et al.
: STEP CONSTRUCTION OF VISUAL CRYPTOGRAPHY SCHEMES
29
Example 1:
The
-VCS :
2) (Security) Any forbidden set of participants has no infor-
mation about the secret image. More precisely, for any for-
bidden set , there exist a participant , then the
share images of set , after being adjusted, form a
VCS under the Denition 1, where is a forbidden set of
the VCS under the Denition 1.
In the above denition, because a qualied set of share im-
ages may have different pixel expansion when they are stacked,
they should rst be adjusted to the same size, i.e., the share im-
ages should be expanded by replicating their sub-
pixels for times, respectively. The ad-
justing stacking makes sense because the share images need to
be stored, and only need to be expanded when used to recover
the secret image. Apparently a smaller share image is more con-
venient to preserve. Furthermore, the VCS often carries impor-
tant secret information, however, it does not provide authenti-
cation ability. Hence, the participants should authenticate other
participants by other authentication means. Therefore, it is rea-
sonable to assume that the participants have authenticated each
other before stacking their share images, i.e., they can know,
in advance, the exact set of participants who are going to stack
their shares. According to the step constructions proposed in this
paper (Construction 1, Construction 2, and Construction 3), any
participant can know, in advance, the size of other participants
share images. This also implies the reasonableness of the adjust
stacking.
According to the security condition of Denition 2, a for-
bidden set of share images of VCS under Denition 2 is also
a forbidden set of share images under Denition 1, hence the
security condition of Denition 2 is no weaker than that of Def-
inition 1.
Note that, for the security condition of Denition 2, we only
need to guarantee that any set in cannot recover the secret
image, because, for any forbidden set , there exists
a set in , denoted by , satisfying . It is clear that
if cannot get any information about the secret image, then
cannot either.
In a traditional VCS, each participant takes one share image
and all the share images have the same pixel expansion. How-
ever, in the proposed construction of this paper, each of the par-
ticipants may take multiple share images with different pixel
expansions. So, in the following part, we list the pixel expan-
sions of all the share images for each participant. We compute
the average pixel expansion (APE) as well, where the APE is
dened as the average value of the total pixel expansions of the
share images that each participant holds.
Particularly, for a set of participants , we dene the pixel
expansion of as the largest pixel expansion of the share images
of .If is a qualied set, then dene the contrast of as the
contrast of the recovered secret image after adjusting stacking.
The participants may have multiple share images, and dif-
ferent qualied sets of share images may result in different con-
trasts. So, in the following part of this paper, we will list all the
possible contrasts of the proposed VCS.
To make things clearer, we give the following example for the
step construction of (3,3)-VCS.
Example 2:
The step construction of (3,3)-VCS can be real-
ized by applying traditional (2,2)-VCS twice. Denote the secret
and
The (2,2)-VCS
:
and
In Example 1, for the (2,2)-VCS , the pixel expansion and
contrast are and , respectively, i.e.,
the size of the recovered secret image and share images will
be twice the size of the original secret image. The contrast of
the recovered secret image will be half of that of the original
secret image. For the (2,2)-VCS , we have that,
and , i.e., the recovered secret image is identical to
the original secret image and the share images have no pixel
expansion.
III. S
TEP
C
ONSTRUCTION OF
VCS
FOR
G
ENERAL
A
CCESS
S
TRUCTURE
In this section, we give a formal denition of step construc-
tion VCS. We propose the step construction of general access
structure VCS in Construction 3, which is based on two sim-
pler step constructions: Construction 1 and Construction 2 in
Section III-A and Section III-C, respectively.
A. Denition of Step Construction and Step Construction of
-VCS
In this section, we rst show the formal denition of step con-
struction VCS, and then give a step construction of
-VCS
in Construction 1.
Recall that and are the minimal qualied access
structure and the maximal forbidden access structure of
, respectively. The formal denition of step
construction VCS is as follows.
Denition 2:
Denote as an access structure on the par-
ticipant set . The step construction -VCS
exists if there exist values and satisfying:
1) (Contrast) Any qualied set of participants can recover the
secret image by stacking (the “ ” operation) their share
images. More precisely, for any share images in a quali-
ed set with pixel expansion
, respectively, let ,
then the adjusting stacking (the “ ” operation) of the share
images can recover the secret image.
If the secret pixel is black, the adjusting stacking (the
“ ” operation) of is a vector that satises
, whereas for a white secret pixel, we have
.
AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:48:23 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.
30
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 5, NO. 1, MARCH 2010
Fig. 1. The
step construction
of the (3,3)-VCS
.
Fig. 3. The construction tree for the
-VCS.
and
Fig. 2. The
step construction
of the (3,3)-VCS .
In Example 2, for the VCS in Fig. 2, the pixel expansion
of the share image is 2, and the pixel expansion of the share
images and is 4. So in the reconstruction phase, the par-
ticipants should rst adjust (enlarge) the smaller share image
to which is of the same size as the other share ( or
). We call the share image the
primary share image
of
. The dealer only needs to distribute the primary share im-
ages to the participants, because the participants can expand
their share images easily in the reconstruction phase. Hence,
for the VCS , the pixel expansions for the share images of
the three participants are 2, 4, and 4, respectively, the average
pixel expansion is APE , and
the contrast is . For the VCS , the pixel expan-
sions are 1, 1, and 1, respectively, the average pixel expansion
is APE , and the contrast is .
For step construction of -VCS, we start with a (2,2)-
VCS, and by taking one of its share images as the secret image
of another (2,2)-VCS, we get a (3,3)-VCS; then we take one of
the newly generated share images as the secret image of another
(2,2)-VCS, and so on, repeat the process times, and then
get an -VCS (Construction 1). The procedure can be de-
scribed by using the binary tree (Fig. 3). We call such a binary
tree the
construction tree
, and we call this kind of construction
the
step construction
.
In a construction tree, once a (2,2)-VCS is applied, we gen-
erate two new share images out of a “secret image;” we call
such a generation of share images the
dividing generation
.For
example, the “secret image”
image of the (3,3)-VCS as , and denote and as the two
share images of the (2,2)-VCS by encrypting the secret image
. Then taking as the secret image of a new (2,2)-VCS, we
get another two share images and . It is easy to verify
that the share images , , and constitute a (3,3)-VCS.
Fig. 1 depicts the step construction of (3,3)-VCS .
According to Fig. 1, the corresponding collections
of share matrix of the (3,3)-VCS
, denoted as
, are as follows:
and
Fig. 2 depicts the step construction of (3,3)-VCS .
According to Fig. 2, the corresponding collections
of share matrices of the (3,3)-VCS , denoted as
, can be as follows:
is divided into two new share
images and .
Because the construction tree depicts how to generate the
share images precisely, hence in the proposed Constructions 1,
2, and 3 of this paper, we only provide the construction trees in-
stead of the detailed text descriptions for explicit access struc-
tures.
Formally, we give the following step construction of
-VCS.
AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:48:23 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.
LIU
et al.
: STEP CONSTRUCTION OF VISUAL CRYPTOGRAPHY SCHEMES
31
Construction 1:
As the construction tree of Fig. 3 depicts, we
apply the traditional (2,2)-VCS for times which takes
as the secret images in turn, and distributes
the share image images
in
is represented by two black subpixels in
, whereas
a white pixel in
is represented by a black subpixel and a
to the par-
white subpixel in
. Then adjust the share image
to the
size of
, and denote it as
. Denoting the stacking result
ticipants, respectively.
For the
step construction
of VCS , the share images of the
-VCS may not have the same pixel expansions. So, in
the distribution phase, the dealer distributes the primary share
images to the participants, and in the reconstruction phase, the
participants adjust the smaller share images to the size of the
largest share image before stacking. More precisely, the share
images
of
and
as
, we have that
recovers
where a black pixel in
is represented by four black sub-
pixels in
, and a white pixel in
is represented by three
black subpixels and a white subpixel in
. When we repeat
the process for
times, we have that the adjusting stacking of
should be expanded by
share images
recovers the secret image
, and the contrast is
and the pixel expansions
times, respectively.
For the step construction of VCS , because all the share
images have the same pixel expansion, the participants do not
need to adjust their share images.
It should be pointed out that the construction trees of this
paper all satisfy that at most one of the two share images of a
dividing generation is divided by other dividing generation, i.e.,
there does not exist the case that both the two share images of a
dividing generation are divided by another dividing generation.
The reason that we do not divide both the share images of
a dividing generation is to avoid the bad visual quality of the
recovered secret image. In fact, if both the share images of a di-
viding generation are divided, then the newly generated share
images will not satisfy the contrast condition of Denition 2 (or
equivalently that of Denition 1) any more, and the newly gener-
ated share images will form a probabilistic visual cryptography
scheme (PVCS), which was introduced in [15] and [16]. How-
ever, the PVCS has bad visual quality of the recovered secret
image, and Yang
et al.
has pointed out the phenomenon in [15]
and given some simulations about the visual quality of PVCS.
We conclude the above discussion as the following theorem.
Theorem 1:
Construction 1 is a step construction of
-VCS which is realized by applying traditional (2,2)-VCS
recursively for times. For VCS , the pixel expansion
for each share image is , and the APE of the
VCS is APE , and the contrast is .
For VCS , the pixel expansions for the share images are
, and the APE of the VCS is
APE , and the contrast is .
Proof:
In order to prove that Construction 1 is a step con-
struction of -VCS, we need to prove that it satises the
contrast and security conditions of Denition 2.
First, we prove the contrast condition. According to the con-
struction tree of Fig. 3, for the VCS , the adjusting stacking
procedure is as follows: The stacking result of the share images
and
of the share images are
, which implies
APE .
Then we prove the security condition. Consider the share im-
ages . For any forbidden set ,
the participants of lack one of these share images. We
prove that the share images form an
-VCS under the security condition of Denition 1.
For
the
XOR
operation,
the
stacking
of
recovers
the
secret
image,
i.e.,
. We have that the
share matrices corresponding to
can
be as follows:
.
.
and
.
.
where a simple example of
can be
found in Example 2.
It is easy to verify that satisfy
the security condition of Denition 1, where by deleting one
row of the share matrices in
and
,
we will get the same collection of submatrices; i.e.,
is a
forbidden set of the
-VCS under the Denition 1. Hence,
also satisfy the security condition of
is
, and the stacking result of
and
Denition 2.
For the
OR
operation, similarly, we have that the share ma-
trices corresponding to
is
. When we repeat the process for
times, we have that
the stacking result of the share images
recovers the secret image , which means that, a black pixel
in the secret image is represented by a black pixel and a white
pixel in the secret image is represented by a white pixel. Hence,
we have and the pixel expansions of all the share
images equal to 1, which implies APE .
For the VCS , the adjusting stacking procedure is as fol-
lows: According to the share matrices in Example 1, we have
that the stacking result of the share images
can be as fol-
lows:
and
, de-
noted by
, recovers the
. More precisely, a black pixel
AUTHORIZED LICENSED USE LIMITED TO: IEEE XPLORE. DOWNLOADED ON MAY 13,2010 AT 11:48:23 UTC FROM IEEE XPLORE. RESTRICTIONS APPLY.
[ Pobierz całość w formacie PDF ]