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

9.2 Visual Cryptography Schemes
Let P = f1;:::;ng be a set of elements called participants, and let 2 P denote
the set of all subsets of P. Let Qual 2 P and Forb 2 P , where Qual \ Forb =
;. We refer to members of Qual as qualified sets and we call members of
Forb forbidden sets. The pair ( Qual ; Forb ) is called the access structure of
the scheme. Dene 0 to consist of all the minimal qualified sets: 0 = fX 2
Qual : X 0 62 Qual for all X 0 Xg: In the case where Qual is monotone
increasing, Forb is monotone decreasing, and Qual [ Forb = 2 P , the access
structure is said to be strong. In a strong access structure, Qual = fC
P : B C for some B 2 0 g, and we say that Qual is the closure of 0 . A
participant i 2 P is an essential participant for ( Qual ; Forb ) if there exists
a set X P such that X [fig 2 Qual but X 62 Qual . If a participant
is not essential then we can construct a visual cryptography scheme giving
him nothing as his share. In fact, a nonessential participant does not need to
participate actively in the reconstruction of the image, since the information
he has is not needed by any set in P in order to recover the secret image.
Therefore, unless otherwise specified, we assume throughout this chapter that
all participants are essential.
The secret image consists of black and white 1 pixels. In order to share each
pixel of the secret image the owner of the secret, usually called the dealer,
provides each participant with a share (transparency), which is an enlarged
version of the secret pixel consisting of a certain number m of subpixels,
which are printed in close proximity to each other, so that the human visual
system averages their individual black/white contributions. Notice that the
term "subpixel" is misleading since a pixel is the smallest unit we can control
on an image and thus we cannot further divide the pixel into subpixels. So
the shared version of the original secret pixel will consist of m pixels, which
are called subpixels because all together they represent the original secret
pixel. The value m is called pixel expansion. The shares can be conveniently
represented with an nm matrix S where each row represents one share, i.e.,
m subpixels, and each element is either 0, for a white subpixel, or 1 for a black
subpixel.
To reconstruct the secret image a group of participants stacks together
their shares. The grey level of the combined share, obtained by stacking the
transparencies i 1 ;:::;i s , is proportional to the Hamming weight w(V ) of the
m-vector V = OR(r i 1 ;:::;r i s ), where r i 1 ;:::;r i s are the rows of S associated
with the transparencies we stack. This grey level is interpreted by the visual
system of the users as black or as white in accordance with some rule of
contrast. Since each secret pixel is represented by m pixels in the shares,
the reconstructed image will be bigger than the original (depending on m
1 Where white should really be interpreted as transparent. So we use white as a synonym
for transparent.