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

Interpret the row vectors of M W and M B as incidence vectors of the sets
A i and B i .

The security requirement ((b) in Dention 1) says j S i2S A i j = j S i2S B i j
for all proper subsets S of f1;:::;ng. By the inclusion-exclusion formula this
is equivalent to j T i2S A i j = j T i2S B i j for all proper subsets S of f1;:::;ng.
By Theorem 3 we have

S i=1 B i S i=1 A i

S i=1 B i

2 1n :

=

Vice versa the incidence vectors of sets solving the approximated inclusion-
exclusion problem define a contrast optimal n-out-of-n visual cryptography
scheme. Note that 1= is also a lower bound for the pixel expansion m and
the example shows that this bound is sharp.

2
Using the proof technique of Theorem 3 one could also solve the approxi-
mate inclusion-exclusion problem for the case that only the size intersections
of up to n 2 sets are known.

Result 5 (see [12] Theorem 3.6) Let A 1 ;:::;A n and B 1 ;:::;B n be two
collections of sets satisfying

=

\ \

A i B i

i2S i2S

for all proper subsets S of f1;:::;ng with jSj n 2. Then
S i=1 A i

n 1
b n 2 c

1

S i=1 B i 1

:

The bound is sharp.

For the proof see [12]. At this point we show only the construction that
proves the sharpness.
We give for every subset S f1;:::;ng the size

:

\

A i n [
i2S

\

B i n [
i2S

A i and B i

i2S i2S

The construction is best understood if we look at the example n = 9 first.

jSj 1 2 3 4 5 6 7 8 9

j T i2S A i n S i2S A i j 0

3 0 1 0 0 2 0 4

j T i2S B i n S i2S B i j 4 0 2 0 0 1 0 3 0