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

In general we will have a zigzag line of numbers starting on the left side
in the B-row with the value b n 2 c, going down to 1, then has one gap and
restart with 1. The general rule is as follows:

8
< jSjd 2 e if jSj > n=2, and jSj is odd

d 2 ejSj if jSj < n=2, and jSj is even
0

=

\

A i n [
i2S

A i (8.10)

:

i2S

in all other cases

8
< jSjd 2 e if jSj > n=2, and jSj is even

d 2 ejSj if jSj < n=2, and jSj is odd
0

=

\

B i n [
i2S

B i (8.11)

:

i2S

in all other cases

Some elementary combinatorial calculations ([12] Theorem 3.8) show that
this example satisfies Result 5 with equality.
Similar to Theorem 4 we can use Result 5 to prove that the contrast of
the optimal (n1)-out-of-n visual cryptography scheme satises

2
n ( n1
b n1

2 c ) .
The example given above can be used to construct a scheme that satisfies the
bound with equality (see [12] Theorem 3.10).

8.4 Designs and Codes
2-out-of-n visual cryptography schemes are a very special case. In a symmetric,
contrast optimal scheme we encode a white pixel by giving all participants
the same share. For a black pixel we want to minimize the overlap of black
subpixels on the transparencies. This is a typical coding theory problem.
The link to coding theory becomes clear by comparing the following two
theorems and their proofs.

Theorem 6 (Plotkin bound) A binary code of length n with minimal dis-

tance d > 2 n has at most 2 j d

k codewords.

2dn

Proof
Let m be the number of codewords. Let A = P c6=c 0 d(c;c 0 ) where the sum
ranges over all pairs of codewords. Since the code has minimal distance d the

sum is bounded below by 2

d.
Let m i be the number of codewords that have 1 in the ith column. The
contribution of those columns to the total distance A is mi) i (m m i )
bm=2cdm=2e.
Hence, bm=2cdm=2e A 2 m(m1)d. For d > 2 n this gives the bound
stated by the Theorem.

2