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

1. There exists > 0, such that for any set Q of exact k partici-
pants p bjb (Q) p bjw (Q) and p wjw (Q) p wjb (Q)
2. For any set Q of strictly less than k participants, the sets C W =
fM Q jM 2C W g and C B = fM Q jM 2C B g are equal.
Notice that the definition of the scheme requires the reconstruction of
a secret pixel (Property 1) to be well defined for qualified sets of exact k
participants. This is without loss of generality because if a qualified set has
more than k participants one can simply choose k of the shares and use only
those k shares to reconstruct the image. Hence in the rest of the chapter a
qualified set is assumed to consist of exact k participants.
The goodness of a scheme is measured by the pixel expansion m, the
contrast = (h `)=m and by the probabilistic factor . Notice that for
m = 1 the above definition is equivalent to the one provided by Yang [22].
Whereas for a big enough m, it is possible to construct schemes with = 1,
and in such a case the above definition is equivalent to the classical definition
of a visual cryptography scheme.
If the pixel expansion m is assumed to be a parameter of a scheme, then
on one extreme, when m = 1 one gets the probabilistic model with no pixel
expansion, and on the other extreme, when m is big enough, one obtains the
deterministic model. In between such two extremes it is possible to consider
probabilistic models with a given pixel expansion, trading the probability of
a good reconstruction with the number of subpixels required to reconstruct
each secret pixel.
5.3 Canonical Probabilistic Schemes
By restricting the attention on a particular class of probabilistic schemes, it is
possible to show that results valid for all the other schemes can be obtained,
without loss of generality. The trick is to prove that for a given scheme it is pos-
sible to define a similar scheme satisfying well-defined additional properties,
without modification on the parameters of the scheme. For this reason canon-
ical -probabilistic (k;n;`;h;m)-VCS schemes are dened as those schemes
that satisfy the following properties:
1. The cardinality of the collections C W and C B are equal and
2. For any two qualified sets Q 1 and Q 2 of participants, we have that
p xjy (Q 1 ) = p xjy (Q 2 ), for x 2fw;bg and y 2fw;bg.
The first lemma says that given a probabilistic scheme S a new scheme S 0
can be constructed such that the cardinality of C W (S 0 ) is the same as that of
C B (S 0 ) and such that S 0 has the same characteristic parameters as S.