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

` 0 = 1 and h 0 = 2, scheme S 0 has p 0 bjb = 1=3 and p 0 bjw = 0. As already said,
here we are considering values satisfying the condition ` 0 = h 0 1. Notice that
for the values the case ` 0 = 0 and h 0 = 2, some reconstructed pixels cannot
be classified as either black or white. In such a scheme the probabilities of
correctly reconstructing secret pixels are smaller (since some of the matrices
are wasted with a reconstruction that is neither black nor white). We also
remark that one could try to eliminate distribution matrices for which the
reconstruction gives a number of black subpixels in the gap between ` 0 and
h 0 ; however it is not clear whether this can be done without violating the
security property. In the particular case above, ` 0 = 0 and h 0 = 2 is clearly
not possible (indeed we would have a perfect reconstruction of both white
and black). One could also extend the formal model to allow this possibility;
but then the contrast should be redefined in order to account for unclassified
reconstructed pixels.
The matrices M B and M W consisting of all the columns of C B and C W can
be used to represent the new scheme S 0 , since they give an ecient represen-
tation of the collections C 0 B and C 0 W ; clearly together with M B and M W , the
pixel expansion m 0 and the thresholds ` 0 and h 0 need to be specified.
Construction 1 starts from probabilistic schemes with no pixel expansion.
Using Lemma 3 or Lemma 4 a probabilistic scheme with no pixel expansion
can be obtained starting from a deterministic scheme. Hence, probabilistic
schemes with pixel expansion can be constructed by starting from a deter-
ministic scheme, applying first Lemma 3 and then Construction 1.
The probabilistic schemes obtained with Construction 1 satisfy the security
property. Indeed, consider a nonqualified set Q of participants and let C W (S)
(resp. C B (S)) be the vectors of C W (S) (resp. C B (S)) restricted to the rows
corresponding to participants in Q. By the security property of S, C W (S) and
C B (S) are the same collection of vectors. Since the way in which C W (S 0 ) and
C B (S 0 ) are constructed is the same (except that for the former we start from
C W (S) and for the latter from C B (S)), also C W (S 0 ) and C B (S 0 ) are the same
collection of matrices. Hence, the security property for S 0 holds.
In this section, a formula for the probabilities of the scheme built with
Construction 1 as a function of the probabilities of the starting scheme is
provided. Let S be a canonical probabilistic scheme with no pixel expansion
and let p bjb ;p bjw ;p wjb and p wjw be the probabilities of S.
Fix an m 0 and build a probabilistic scheme with pixel expansion m 0 using
Construction 1. Fix also a threshold ` 0 , 0 ` 0 < m 0 . Fixing ` 0 also gives
h 0 = ` 0 + 1. Notice that, even with this restriction, not all choices of ` 0 will
result in valid schemes. Let r be the cardinality of the collections C W and C B
of S.
The cardinality of the collections C 0 W and C 0 B , of scheme S 0 , is r 0 = r(r
1) ::: (rm 0 + 1) because the first column can be selected in r ways, the
second in r 1 ways, and so on until the last column for which r m 0 + 1