Visual Cryptography and Contrast Bounds - Visual Cryptography and Secret Image Sharing - page 220

8.2 Preliminaries
For the moment we will ignore the pixel expansion and the randomness. Then
contrast optimal visual cryptography schemes can be simplified.

Lemma 1 Let be any access structure then there exists a contrast optimal
visual cryptography scheme (M W ;M B ) for with the property thatM W is the
multiset of all column permutations of a matrix M W andM B is the multiset
of all column permutations of a matrix M B .

Proof
Let (M 0 W ;M 0 B ) be a contrast optimal visual cryptography scheme for with
pixel expansion m and randomness r.
Let M W = (M 0 W (1) ;:::;M 0 W (r) ) be the n (mr) matrix which consist of
all matrices M 0 W (i) 2M 0 W (i = 1;:::;r) written in sequence, one after the
other. Similarly let M B be the n (mr) matrix that consists of the matrices
inM 0 B written after each other.
Let G 2 , by Denition 1 (b) the restriction of M W and M B to the rows
i 2 must give return two matrices that dierent only for a permutation of
their columns, i.e., the scheme (M W ;M B ) satisfies the security requirement
(Definition 1 (b)).
Now let G 2 by Denition 1 (c) the restriction of every matrix inM B to
the rows i 2 contains at least m more nonzero columns than the restriction
of a matrix inM W to the same rows. Thus, the restriction of M B to the rows
i 2 contains at least mr more nonzero columns than the restriction of M W
to the rows i 2 . That proves that the scheme (M W ;M B ) reconstructs the
secret image.

2
The advantage of the scheme constructed by Lemma 1 is that the visual
cryptography scheme is now described by just two Boolean matrices M 0 W and
M 0 B instead of two multisets of Boolean matrices. Moreover the order of the
columns in M 0 W and M 0 B does not matter. For each S f1;:::;ng let x (W)

S
denote the number of columns in M 0 W with 1 in the rows corresponding to
S and 0 in the other rows. Similarly define the variables x (B)
S

. The scheme is

described completely by the values x (B S , x (W S .
The security requirements of the visual cryptography scheme translates to
the linear equations

X

= X
Sf1;:::ng
S\G6=0

x (W)
s

x (B)
s

(8.1)

Sf1;:::ng
S\G6=0

for all G 2 and the requirement that a qualied subset can see the image
translates to

X

< X
Sf1;:::ng
S\G6=0

x (W)
s

x (B)
s

(8.2)

Sf1;:::ng
S\G6=0