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

8.7 Contrast Trade-Offs for Extended Visual
Cryptography Schemes
In this section we look at a visual cryptography scheme with extended ca-
pacity. In [16] Naor and Shamir show that it is possible to create two trans-
parencies such that each transparency shows an image and the stack of the
two transparencies reveals another image. The three images must not satisfy
any relation.
In general, we have n slides and a subsetSof P(f1;:::;ng)nf;g. For an
S-extended visual cryptography scheme we require that for every S 2Sthe
stack of the transparencies i 2 S reveals an image I S . Furthermore, we require
that there is no other way to get information about the image I S .
As in the case of the simple visual cryptography schemes we formalize
these ideas by describing the encoding algorithm by a multiset of Boolean
matrices. This leads to Definition 4.

Denition 4 LetSP(f1;:::;ng)nf;g.
AnS-extended visual cryptography scheme is described by multisetsM T
of n m Boolean matrices forTS. (For givenTeach Boolean matrix
inM T describes the colors of the subpixels on each transparency, where the
corresponding pixel in image IT T is black if and only if T 2T. For encoding,
each matrix inM T is chosen with the same probability.)
The multisetsM T must satisfy the following conditions:

1. Let B 2M T . For fi 1 ;:::;i q g 2Sthe Hamming weight of the
OR of the rows i 1 ;:::;i q of B is h fi 1 ;:::;i q g if fi 1 ;:::;i q g 2Tand
l fi 1 ;:::;i q g otherwise, i.e.,

w Ham ((b i 1 ;1 ;:::;b i 1 ;m ) OR ::: OR (b i q ;1 ;:::;b i q ;m ))

( h fi 1 ;:::;i q g if fi 1 ;:::;i q g2T

=

l fi 1 ;:::;i q g if fi 1 ;:::;i q g 2T :2

(This means stacking the transparencies i 1 ;:::;i q together we re-
cover the image I fi 1 ;:::;i q g .)
2. For fi 1 ;:::;i q g f1;:::;ng andT;T 0 SwithT\
P(fi 1 ;:::;i q g) =T 0 \P(fi 1 ;:::;i q g) we obtain the same multi-
sets if we restrict the matrices inM T andM T 0 ; respectively, to the
rows i 1 ;:::;i q .
(This condition guarantees the security of the different images.)

IfS= P(f1;:::;ng)nf;g we simply call this an extended visual cryptography
scheme.