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

In the following only canonical schemes will be considered, remembering
that for a canonical scheme p xjy (Q 1 ) = p xjy (Q 2 ), for x 2fw;bg and y 2fw;bg
and thus we will just write p xjy , without specifying the qualified set.

5.4 Probabilistic Schemes with No Pixel Expansion
Probabilistic threshold schemes give the possibility to construct a VCS scheme
with no pixel expansion, that is having m = 1. In [22] it has been proved
that a deterministic scheme S with contrast (S) can be transformed into
a -probabilistic scheme S 0 with (S 0 ) = (S) and no pixel expansion. In
[11] a complementary result has been proven showing that there is a one-to-
one correspondence between the probabilistic model with no pixel expansion
and the deterministic one where the contrast is traded for the probabilistic
factor. Indeed a -probabilistic scheme S with no pixel expansion can be
transformed into a deterministic scheme S 0 with contrast (S 0 ) = (S). An
immediate consequence is that any bound on the contrast of a deterministic
scheme is also a bound on the probabilistic factor of probabilistic schemes
with no pixel expansion. In the following we report the lemma proving the
correspondence between probabilistic schemes with no pixel expansion and
deterministic schemes.
The following lemma has been proved in [22] and applies to VCS with
basis matrices.

Lemma 3 [22] Let S be a deterministic (k;n;`;h;m)-VCS with base matrices
M B and M W . Then, there exists a canonical -probabilistic (k;n;` 0 ;h 0 ; 1)-VCS
scheme with = (S).

Proof Let S be a deterministic (k;n;`;h;m)-VCS. Construct a probabilistic
scheme S 0 , by letting C B (S 0 ) (resp. C W (S 0 )) consists of all the n 1 vectors
that appear in the matrices M B (resp. M W ).
We need to prove that S 0 is a -probabilistic (k;n;` 0 ;h 0 ;m 0 )-VCS scheme
with ` 0 = `;h 0 = h;m 0 = 1 and = (S) = (h`)=m. Obviously S 0 has pixel
expansion m 0 = 1.
By the properties of S, we know that when the secret pixel is black the
reconstruction in S gives at least h black subpixels, that is p bjb h=m. Obvi-
ously this gives p wjb (mh)=m. Similarly, we have p wjw (m`)=m and
p bjw `=m.
Hence, in S 0 we have that
p wjw p wjb m`

m mh

= h`
m m

and

p bjb p bjw h

m ` m = h` m