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

9.4.1 A Construction Using a Binary Secret Sharing Scheme
In this section we describe an ideal contrast VCS with reversing for any access
structure ( Qual ; Forb ), proposed in [6]. The scheme uses as a building block
a binary secret sharing scheme (BSS for short).
A BSS for an access structure ( Qual ; Forb ) on a set of n participants is a
method to share a secret s 2f0; 1g among the n participants in such a way that
only subsets of participants in Qual can recover the secret, whereas, subsets
of participants in Forb have no information about the secret. A BSS consists
of two collections B 0 and B 1 of distribution functions. A distribution function
f 2B 0 [B 1 is a function associating each participant i to the share f(i). In
the reconstruction phase, any qualified set of participants X = fi 1 ;:::;i p g2
Qual run a reconstruction algorithm Rec (f(i 1 );:::;f(i p )), which on inputs
the shares they hold, outputs the secret s. See [7] for a formal definition of
BSSs. Let r be the number of bits in the binary representation of the largest
share f(i). Without loss of generality (W.l.o.g.), we consider the r-bits binary
representation of each share f(j), where j 6= i, obtained by prefixing the
r 0 -bits binary representation of f(j), where r 0 < r, with r r 0 zeroes. The
reconstruction algorithm Rec(f(i 1 );:::;f(i p )) computes a Boolean function
on its inputs. Such a function can be computed by using a Boolean circuit.
It is well known that OR and NOT represent a complete basis for Boolean
functions, i.e., any Boolean function can be computed by a binary circuit
composed only of OR and NOT gates. Therefore, Rec(f(i 1 );:::;f(i p )) can
be computed by a Boolean circuit composed only of OR and NOT gates,
corresponding to stacking and reversing operations, respectively.
In the distribution phase of the VCS with reversing, the encoding of the
secret image is handled pixel by pixel, where each pixel is considered inde-
pendently of the others. For each pixel of the original image and for each par-
ticipant i, the dealer generates the corresponding pixel in each transparency
t i;1 ;:::;t i;r , where r is the size of the shares distributed by the underlying
BSS. 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. Such a sequence of
operations corresponds to simulating parallel runs of the reconstruction algo-
rithm of the BSS, that is, one run for each pixel of the original image. Such
a parallel execution enables the reconstruction of the original image, because
each transparency contains the same number of pixels of the original image
and each pixel can be reconstructed by using the same Boolean circuit. The
construction is described in Figure 9.2.
It is easy to see that the construction of Figure 9.2 gives an ideal contrast
VCS with reversing with no loss of resolution. Indeed, let us consider the
encoding pixel by pixel. Let X 2 Qual be a qualified set of participants.
From the reconstruction property of the underlying BSS, the participants in
X can reconstruct the secret pixel, by performing the sequence of stacking
and reversing operations on their transparencies corresponding to the binary