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

which is also true, since n1
ng

= n1
g1

. For j = 2 we get

n 2
0

n 1
g

n 1
g 1

n 2
ng

n 2
g

+ 1 = 1

which is true since n1
g

n1
g1

= n2
g

and n2
g

+ n2
ng

= n2
g

+ n2
q1

=

n2
g

.
Thus, S(3;g;n) satises the security requirements of an 3-out-of-n visual
cryptography scheme.
The contrast of S(3;g;n) is

n 3
0

n 1
g

n 1
g 1

n 3
ng

n 3
g

m = + 1 1

n 2
g

n 2
g 1

n 1
g 1

n 3
g 3

n 3
3

= + +

n 3
g 1

n 2
g 3

n 3
g 3

= +

n 3
g 1

n 3
g 2

=

So the image is indeed recovered.

2
The scheme S(3;g;n) archives optimal contrast if we choose g = b n+ 4 c.
This is the best possible contrast for a 3-out-of-n scheme. To prove this result
we introduce the canonical form of a k-out-of-n scheme.
Remember that a k-out-of-n scheme is described by the following linear
program.
Maximize:

nk
i

nk
i

n X n X

x (W)
i

x (B)
i

= (8.14)

i=0 i=0

Subject to

n
i

n
i

X X

x (W)
i

x (B)
i

= = 1 (8.15)

i=0 i=0

and

nj
i

nj
i

n X n X

x (W)
i

x (B)
i

= (8.16)

i=0 i=0

for j = 0;:::;k 1.

Lemma 13 There is an optimal solution of the linear program defined by
(8.14), (8.15), and (8.16) that satisfies:

1.If k is even, then x (W)
i

= x (W)

ni and x (B)

= x (B)

ni for i = 0;:::;n. i