## 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 ]**