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

the collections C B (S) and C W (S)). By the security property of S we have that
the k 0 rows of M B are equal to the k 0 rows of M W , except for a permutation
of the columns. Hence, S 0 satisfies the security property.
Finally, the contrast of S 0 is (S 0 ) = h 0 ` 0

m 0 = c 1 B c 1 r = p bjb p bjw (S).
As already said, the correspondence between deterministic schemes and
probabilistic schemes with no pixel expansion allows the reuse of bounds
found on the contrast as bounds on the corresponding probabilistic factor.
For example, in [14] it has been proved that the contrast of any deterministic
(2;n)-VCS is upper bounded by

n k
n(n 1)(n (k 1)) :

= 4 (k1) (5.1)

As an immediate, the following lemma, which is a corollary of Lemma 5,
also holds:

Corollary 6 For any -probabilistic (2;n; 0; 1; 1)-VCS we have that

= 4 (k1) n k

n(n 1)(n (k 1)) :
Proof Assume by contradiction that a probabilistic scheme with >
exists. By Lemma 5, we can construct a scheme with contrast . Since
> = we get that > , contradicting Equation (5.1).

5.5 Trading Pixel Expansion with Probabilities
In the above section, the correspondence between deterministic and probabilis-
tic schemes has been stated in Lemma 3 and Lemma 5, showing a trade-off
between pixel expansion and probability factor. It shows that by using a large
enough pixel expansion we can transform a probabilistic scheme into a de-
terministic one. Indeed, on one extreme it is possible to have schemes with
no pixel expansion, where the reconstruction relies entirely on the probability
factor of the scheme. On the other extreme, it is possible to have deterministic
schemes, where the reconstruction is guaranteed but a certain pixel expansion
is required. In the next section we show how it is possible to stay in between
the two extremes, realizing schemes for which the probability factor is traded
for the pixel expansion.

5.5.1 Probabilistic Schemes with Given Pixel Expansion
Lemma 5 shows the basic technique for the construction of a deterministic
scheme with pixel expansion equal to the cardinality r of the collections C B