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

As we have seen above every block consists of 2 points.
Since for every two transparencies the number of subpixels that is white on
the first and black on the second is constant. Each transparency must have the
same number of black subpixels. Since each subpixel is black on exactly half
of the transparencies the number of black subpixels per transparency must be
m

2 .

Thus, two transparencies have exactly 2 m = m(n1)

4n4 common black
subpixels. In the interpretation as incidence structure: Each two points are
joined by m(n1)

4n4 blocks.
In other words M B is the incidence matrix of a 2 (n; 2 ; m(n2) ) design.

4n4

Conversely the incidence matrix of a 2 (n; 2 ; m(n2)

4n4 ) design satisfies all
requirements of a 2-out-of-n visual cryptography scheme.

2
Similarly, we can deal with the case of n odd. The Proof of Theorem 7
shows that every column in M B must contain either bn=2c or dn=2e zero
entries. So we do not get a design (every block is of the same size), but a
structure called pairwise balanced design (PDB) where the size of block may
vary between some values. We skip the details and just state the final result.

Result 9 (see [3] Theorem 4.5) Let n be odd. A 2-out-of-n visual cryptog-
raphy scheme with optimal contrast = n

4n4 and pixel expansion m exists
if and only if there exists a 2 (n;f n 2 ; n+ 2 g;w m(n+1)

4n ) PBD such that
every point lies in exactly w blocks, where w is an integer in the range

(n 1)m
2n

w (n + 1)m
2n

:

A well-known result from coding theory states that Hadamard codes
archive equality in the Plotkin bound. So we are not surprised that Hadamard
matrices can also be used to construct optimal 2-out-of-n visual cryptography
schemes.
Recall the Definition of Hadamard matrices.

Denition 3 A Hadamard matrix is a nn matrix H with entries 1 and
HH t = nI.

It is well known that except for n = 1; 2 the order of a Hadamard matrix
must be divisible by 4. The famous Hadamard conjecture states that for every
n a (4n)(4n) Hadamard matrix exists. See [8] for an overview of constructions
of Hadamard matrices.
The connection to visual cryptography is established by the next theorem.

Theorem 10 (see [3] Theorem 4.7) The pixel expansion of a contrast op-
timal 2-out-of-(4n 1) visual cryptography scheme is at least m 4n 1. A
scheme with m = 4n 1 is equivalent to the existence of a 2 (4n 1; 2n
1;n1) design (called a Hadamard design). This is equivalent to the existence
of a Hadamard matrix of order 4n.