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

9.4.2.1 The Scheme by Cimato, De Santis, Ferrara, and Masucci

In this section we describe a general technique, due to Cimato, De Santis,
Ferrara, and Masucci [6], to construct an ideal contrast VCS with reversing for
any access structure ( Qual ; Forb ). The scheme uses as a building block a VCS
with perfect reconstruction of black pixels, having a certain pixel expansion
m, and requires each participant to store m transparencies, each having the
same number of pixels as the original image.
In the distribution phase of the scheme, the encoding of the secret image
is handled pixel by pixel, where each pixel is considered independently of the
others. For each pixel of the original image and for each participant i, the
dealer generates the corresponding pixel in each transparency ti,1, i;1 ;:::;t i;m . In
the reconstruction phase, any qualified set of participants recover the original
secret image with no loss of resolution by performing a sequence of stacking
and reversing operations on their transparencies. The construction is described
in Figure 9.3.

Let ( Qual ; Forb ) be an access structure on a set of n participants.
Let C 0 and C 1 be the collections of Boolean matrices constituting a
( Qual ; Forb )-VCS with a perfect reconstruction of black pixels and pixel
expansion m.

Distributionphase.To share a white (black, resp.) pixel, the dealer
has to:

randomly choose a matrix S = [s i;j ] in C 0 (S in C 1 , resp.);
for each participant i, consider the m bits si,1, i;1 ;:::;s i;m composing
the i-th row of S and, for each j = 1;:::;m, put a white (black,
resp.) pixel on the transparency t i;j if s i;j = 0 (s i;j = 1, resp.).
Reconstructionphase.Let X = fi 1 ;:::;i p g2 Qual : Participants in
X reconstruct the secret pixel by computing:

j = OR(s i 1 ;j ;:::;s i p ;j ), for j = 1;:::;m;
j , for j = 1;:::;m;
= OR( 1 ;:::; m );
; which is the reconstructed pixel.

FIGURE 9.3
Cimato, De Santis, Ferrara, and Masucci's ideal contrast VCS with reversing.

It is easy to see that the construction of Figure 9.3 gives an ideal contrast
( Qual ; Forb )-VCS with reversing. Indeed, let us consider the encoding pixel by
pixel and analyze separately the reconstruction phase in case the dealer shared
a white pixel or a black pixel. Let X = fi 1 ;:::;i p g2 Qual be a qualified subset
of participants and assume that the secret pixel shared by the dealer was