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

If the Hadamard conjecture is true the bounds are sharp.

We remark that there are 2-out-of-n visual cryptography schemes with
smaller pixel-expansion that are not contrast optimal. In [3] (Theore m 4 .12)
2-out-of-n visual cryptography schemes with pixel expansion m p n and
contrast 4

there exists a 2-out-of-n
visual cryptography scheme with pixel expansion m and contrast 1=m (just
color on each transparency is a dierent set of bm=2c subpixels). This is the
minimal possible pixel expansion.

are constructed. For n = m
bm=2c

8.5 Optimal3-out-of-nSchemes
We construct a scheme that has the normal form of Lemma 2. Remember that
we denoted by x (W i the number of subpixels when encoding a white pixel
that are black of the slides 1;:::;i and white on the other slides. Similarly
x (B i describes the encoding rule for a black pixel. As we have seen in the
introduction, a k-out-of-n scheme must satisfy

nk
i

nk
i

n X n X

x (W)
i

x (B)
i

m = (8.12)

i=0 i=0

and

nj
i

nj
i

n X n X

x (W)
i

x (B)
i

= (8.13)

i=0 i=0

for j = 0;:::;k 1.
Let S(3;g;n) be the visual cryptography scheme that is described by the
values x (W)
0

= x (B n = n1
g

n1
g1

, x (W)

ng = x (B g = 1 and all other variables

are 0.

Theorem 12 ([2] Theorem 4.6) S(3;g;n) is a 3-out-of-n visual cryptogra-

phy scheme with pixel expansion m = 2 n1
g

and contrast

g(n 2g)
2(n 1)(n 2) :

=

Proof
For j = 0 we have in (8.13):
n
0

n 1
g

n 1
g 1

n
ng

n
g

n
n

n 1
g

n 1
g 1

+ 1 = 1+ = m

For j = 1 we get
n 1
0

n 1
g

n 1
g 1

n 1
ng

n 1
g

+ 1 = 1