Visual Cryptography Schemes with Reversing - Visual Cryptography and Secret Image Sharing - page 253

and on the actual positions of the pixels, the image can also be distorted;
a perfect square is a good choice for m because it avoids distortion). The
characteristics of the model are encapsulated in the following definition, which
is a generalization of the denition of (k;n)-threshold VCSs due to [12].

Definition 1 Let ( Qual ; Forb ) be an access structure on a set of n partici-
pants. Two collections (multisets) of nm Boolean matrices C 0 and C 1 con-
stitute a visual cryptography scheme ( Qual ; Forb )-VCS with pixel expansion
m if there exist two integers ` and h such that h > ` satisfying:

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

To share a white (black, resp.) pixel, the dealer randomly chooses one
of the matrices in C 0 (C 1 , resp.), and distributes row i to participant i. The
chosen matrix defines the m subpixels in each of the n transparencies.
The first property of Definition 1 is related to the contrast of the image.
It states that when a qualified set of participants stack their transparencies,
they can correctly recover the image shared by the dealer. A pixel will be seen
as a white pixel if suciently many subpixels (at least h) in the reconstructed
image are white; whereas, it will be seen as a black one if not too many (at
most `) are white. The value (h `)=(h + `) is referred to as the contrast
of the reconstructed image. Contrast gives a measurement of how clear the
reconstructed image is in relation to the original one. The second property of
Definition 1 is related to the security of the scheme, since it implies that, even
by inspecting all their shares, any forbidden set of participants cannot gain
any information in deciding whether the shared pixel was white or black.
Several visual cryptography schemes have been realized by using two nm
matrices, S 0 and S 1 , called basis matrices. The collections C 0 and C 1 are
obtained by permuting the columns of the corresponding basis matrix (S 0 for

C 0 , and S 1

for C 1 ) in all possible ways. This technique has been introduced in

[11].

9.2.1 (k;k)-Threshold Visual Cryptography Schemes
In a (k;k)-threshold visual cryptography scheme the secret image is visible
if and only if all k transparencies are stacked together, but totally invisible