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

S-extended schemes exists as the following theorem shows.
Theorem 17 (see [9]) AnS-extended schemes with pixel expansion
m = X
S2S

2 jSj1

and contrast = 1=m exists.

Proof
TheS-extended scheme is built from several k-out-of-k schemes. For each
S 2Swe reserve 2 jSj1 subpixels. On slides with number i 2 S these subpixels
are colored black. For the slides i 2 S these 2 jSj1 subpixels are used to
construct an jSj-out-of-jSj visual cryptography scheme to encode the image
I S (see Theorem 4 for the construction).
To illustrate the construction letS= ff1; 2g;f1; 3gg then m = 4. The
first two pixels are used to encode the image I f1;2g and the next two subpixels
are for the image I f2;3g .
A typical matrix ofM ; is

0 1

1 0 1 1

@ A

M ; =

1 0 1 0

1 1 1 0

and a typical matrix ofM ff1;2gg is

0 1

1 0 1 1

@ A :

M ; =

0 1 1 0

1 1 1 0

In the upper right corner you see the 2-out-of-2 scheme for the image I f1;2g .
We claim that this construction yields anS-extended scheme.
Let T f1;:::;ng, what happens if we stack the transparencies i 2 T?
In the 2 jTj1 subpixels associated with the image IT T we have jTj-out-of-
jTj scheme and hence either all 2 jTj1 subpixels in the stack are black or only
2 jTj1 1 subpixels are black depending on the color in the image IT T .
For S 6= T and T 6 S we nd an i 2 T with i 2 S. On transparency
i all 2 jSj1 subpixels associated with IT S are black. Hence, in the stack of
the transparencies i 2 T these 2 jSj1 subpixels are always black and do not

contribute to the encoded color.
For S 6= T and T S we have a jSj-out-of-jSj scheme for the image I S . By
the security requirement stacking only the transparencies i 2 T the number
of black subpixels must be independent of the color of image I S . (There will
be exactly 2 jSj1 2 jSjjTj1 black subpixels associated with the image I S .)
As we can see, only the 2 jTj1 subpixels associated with the image IT T
contribute to the image that we see when stacking the transparencies i 2 T.
Hence, the stack of the transparencies i 2 T reveals image I T .
Since the scheme is built from several standard k-out-of-k schemes, it in-
herits the security from the standard visual cryptography scheme. 2