Resolving the Alignment Problem in Visual Cryptography - Visual Cryptography and Secret Image Sharing - page 293

satisfying 2 k n and 0 l < h m. The two collections of nm binary
matrices (C 0 ;C 1 ) constitute a visual cryptography scheme (k;n)-VCS if the
following properties are satisfied:

1. (Contrast) For any s 2 C 0 , the OR of any k out of n rows of s
is a vector v that satises w(v) l.
2. (Contrast) For any s 2 C 1 , the OR of any k out of n rows of s
is a vector v that satises w(v) h.
3. (Security) For any i 1 < i 2 < < i t in f1; 2; ;ng with
t < k, the two collections of tm matrices D j , j = 0; 1, obtained by
restricting each nm matrix in C j , j = 0; 1, to rows i 1 ;i 2 ;i t , are
indistinguishable in the sense that they contain the same matrices
with the same frequencies.

Note that, in the above definition,

1. m is called the block length and determines the pixel expansion of the scheme.
A pixel of the original secret image is represented by m subpixels in the
recovered secret image. In general, we are interested in schemes with m
being as small as possible. h and l are called the darkness thresholds of the
black and white pixels, respectively.

hl

2. Dene the value =

m to be the contrast of the scheme. Note that,
however, there are other definitions of the contrast of VCS. We use this
definition to establish our result. The proof is similar for other definitions
of contrast.

We consider VCS in which C 0 , C 1 are constructed from a pair of nm
binary matrices M 0 , M 1 , called basis matrices. The set Ci, i , i = 0; 1 consists of
the m! matrices obtained by applying all permutations to the columns of M i .
This approach of VCS construction will have small memory requirements (it
only keeps the basis matrices) and high eciency (to choose a matrix in C 0
(resp: C 1 ) as it only needs to generate a permutation of the basis matrix). We
will use the basis matrices to simplify the discussions.
The above definition of VCS is also called the Deterministic Visual Cryp-
tography Scheme (DVCS). The original secret image can be deterministically
recovered by the qualified shares pixel by pixel in such schemes. In contrast to
the DVCS, Yang and Cimato et al. proposed the Probabilistic Visual Cryptog-
raphy Scheme (PVCS) in [14, 4], where the pixels of the original secret image
can only be probabilistically recovered by the qualified shares, however, in the
overall view the original secret image can be recovered visually as well.

Definition 2 (Probabilistic VCS [14, 4]) Let k, n, and m 0 be nonneg-
ative integers, l and h be positive numbers, satisfying 2 k n and
0 l < h m 0 . The two collections of n m 0 binary matrices (C 0 ;C 1 )
constitute a probabilistic threshold Visual Cryptography Scheme (k;n)-PVCS
if the following properties are satisfied: