Probabilistic Visual Cryptography Schemes - Visual Cryptography and Secret Image Sharing - page 128

square is a good choice for m because it avoids distortion). Depending on the
stacked shares, each secret pixel will be reconstructed with a certain number
of black and white subpixels. A reconstructed pixel is considered white if the
number of white pixels in its reconstruction is big enough, i.e., the number of
black subpixel is less than or equal to a given threshold `, and is considered
black if the number of black subpixels is big enough, i.e., greater or equal
a given threshold h. Obviously one has to require that ` < h. l ` and h are
called the contrast thresholds of the scheme. In some other papers, the contrast
thresholds are used slightly dierently: mh is an upper bound on the number
of black subpixels in a white pixel and m` is a lower bound on the number
of black subpixels in a black pixel.
Since a reconstructed pixel has to be either black or white, we consider
only schemes such that in the reconstructed image each reconstructed pixel
has a number of black pixels, which is either ` or h. An easy way to
resolve ambiguities in the reconstruction is to assume ` = h 1.
We consider threshold schemes where a qualified set of participants consists
of k or more participants. For these schemes, a nonqualified set of participants,
i.e., a set of less than k participants, will not have any information about the
secret image from the shares. Instead, a qualified set of participants, i.e., a
set of at least k participants will be able to reconstruct the secret image. The
quality of the reconstructed image depends on the scheme.
In a deterministic scheme the quality of the reconstructed image depends
on the so-called contrast that is a function of the pixel expansion m, and
the contrast thresholds ` and h. The contrast of a scheme is dened as =
(h`)=m:
In a deterministic scheme it is guaranteed that, for any qualified set of
participants, the pixel is reconstructed correctly; that is, if the secret pixel is
white then the number of black subpixels in the reconstructed image, corre-
sponding to that secret pixel, is at most `, whereas if the secret pixel is black,
the number of black subpixels in the reconstructed pixel is at least h.
In order to provide shares to the participants the dealer chooses uniformly
at random a distribution matrix from a collection of matrices C B , if the secret
pixel is black, or from a collection of matrices C W , if the secret pixel is white.
Hence, for a deterministic scheme it holds that for any distribution matrix M
of the set C B , the reconstruction of a pixel obtained by M Q for any qualified
set Q, gives at least h black subpixels, whereas for any distribution matrix M
of the set C W the reconstruction of a pixel obtained by M Q for any qualified
set Q, gives at most ` black subpixels. Let us report here the formal definition
of a deterministic VCS:
Definition 1 Let ( Qual ; Forb ) be an access structure on a set of n partici-
pants. Two collections (multisets) of nm boolean matrices C W and C B con-
stitute a visual cryptography scheme ( Qual ; Forb ;m)-VCS if there exist the
integers ` and h, ` < h, such that:
1. Any (qualified) set Q = fi 1 if 2 ;:::;i p g 2 Qual can recover the