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

Thus the collections A 0 i , B 0 i satisfy the induction hypothesis, i.e., we have

j S i=1 B 0 i j k2 n1 .
On the other hand, we have the collections A 0 i = A i \ A n+1 and B 0 i =
B i \B n+1 . Since

=

[ [

A i B i

i=1 i=1

+ = +

[ [ [ [

A 0 i A 0 i B 0 i B 0 i

()

i=1 i=1 i=1 i=1

and j S i=1 A 0 i j+ k = j S i=1 B 0 i j we nd that the collections A 0 i and B 0 i satisfy

the induction hypothesis with j S i=1 B 0 i j + k = j S i=1 A 0 i j. Thus, jB n+1 j =

jA n+1 jj S i=1 A 0 i j k2 n1 . This proves

= + jB n+1 j k2 n1 + k2 n1 = k2 n

n+ [ [

B 0 i

B i

i=1 i=1

as desired.
To see that the bound is sharp consider the sets

A i = fS f1;:::;ngjjSj even;i 2 Sg

and

B i = fS f1;:::;ngjjSj odd;i 2 Sg :
Since for each nonempty set the number of subsets of even cardinality is the

same as the number subsets of odd cardinality (0 = (11) n = P j=0 (1) j j

)

we get

= = 2 njSj1

\ \

A i B i

i2S i2S

for each proper subset S of f1;:::;ng. Hence, the sets A i and B i satisfies the
requirement conditions of the approximate inclusion-exclusion problem and
S i=1 B i S i=1 A i

2 n1 (2 n1 1)
2 n1

1
2 n1 ;

S i=1 B i

= =

i.e., the bound given by the Theorem is sharp.

2
Theorem 3 translates directly to an contrast optimal n-out-of-n visual
cryptography scheme.

Theorem 4 (see [16]) The optimal contrast of a n-out-of-n visual cryptog-
raphy scheme is = 2 1n and the minimal pixel-expansion is m = 2 n1 .

Proof
By Lemma 1 a n-out-of-n visual cryptography scheme can be described by
two Boolean matrices M W and M B .