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

shared image by stacking their transparencies.
Formally, for any M 2C W , the "or" V of rows i 1 ;i 2 ;:::;i p satisfies
w(V ) `; whereas, for any M 2C B it results that w(V ) h.
2. Any (forbidden) set X = fi 1 ;i 2 ;:::;i p g2 Forb has no informa-
tion on the shared image.
Formally, the two collections of pm matrices D t , with t 2fB;Wg,
obtained by restricting each nm matrix in C X to rows i 1 ;i 2 ;:::;i p
are indistinguishable in the sense that they contain the same matri-
ces with the same frequencies.

In many schemes, the collection C W (resp. C B ) consists of all the matrices
that can be obtained by permuting all the columns of a matrix M W (resp.
M B ). For such schemes, the matrices M W and M B are called the base matri-
ces of the scheme. Base matrices constitute an ecient representation of the
scheme. Indeed, the dealer has to store only the base matrices and in order to
randomly choose a matrix from C X he has to randomly choose a permutation
of the columns of the base matrix M X .
A scheme is characterized by several parameters: the number of partic-
ipants n, the threshold k that determines whether a set of participants is
qualified to reconstruct the image, the pixel expansion m, and the contrast
thresholds ` and h, which determine whether a reconstructed pixel is consid-
ered white or black.

5.2.2 The Probabilistic Model
In a probabilistic scheme the reconstruction property is no more guaranteed,
but each pixel can be correctly reconstructed only with a probability given as
a parameter of the schema. This means that the distribution matrices must be
carefully selected in order to satisfy the above properties. For a probabilistic
scheme, as done in [22], it is possible to define the probabilities of (un)correctly
reconstructing a (black)white pixel, given a qualified set of participants Q.
With p ijj is denoted the probability of having a reconstructed pixel i, given
that the corresponding pixel in the secret image was j, where i;j 2 fb;wg.
Then p wjw (Q), denotes the probability of correctly reconstructing a white
pixel when superimposing the shares of Q, and p bjw (Q) as the probability of
incorrectly reconstructing a white pixel. Notice that p wjw (Q) =

z

jC W j where z
is the number of distribution matrices M in C W for which M Q reconstructs
a pixel with at most ` black subpixels and p bjw (Q) =

z

jC W j where z is the
number of distribution matrices M in C W for which M Q reconstructs a pixel
with at least h black subpixels. In a similar way p bjb (Q) and p wjb (Q) can be
dened.
The quantities

p bjb (Q) p bjw (Q)