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

Let ( Qual ; Forb ) be an access structure on a set of n participants. Let
B 0 and B 1 be the collections of distribution functions realizing a BSS
for ( Qual ; Forb ). Let r be the size of the shares distributed by the BSS.
Distributionphase.To share a white (black, resp.) pixel of the orig-
inal image, the dealer has to:
randomly choose a distribution function f 2B 0 (resp. f 2B 1 ),
for each participant i, consider the binary representation si,1, i;1 ;:::;s i;r
of the share f(i) and, for each j = 1;:::;r, 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 image by performing the sequence of revers-
ing and stacking operations on their transparencies, corresponding to
the NOT and OR gates of the Boolean circuit computing in parallel
Rec (f(i 1 );:::;f(i p )), for each pixel of the original image, where f is
the distribution function chosen to share that pixel.
FIGURE 9.2
A construction for ideal contrast VCS with reversing using a BSS.
circuit simulating the reconstruction algorithm of the underlying BSS. The
security of the scheme directly follows from the security of the underlying
BSS.
As shown in the following, we can construct an ideal contrast (k;k)-
threshold VCS with reversing, with k 2, where each participant has to
store only one transparency, if we use as a building block a (k;k)-threshold
BSS distributing shares of one bit. This improves on the construction for a
(k;k)-threshold VCS with reversing of Figure 9.1, where each participant has
to store c transparencies, each containing 2 k1 subpixels for each pixel of
the original secret image, c being the number of runs of the underlying VCS
needed to obtain an asymptotically ideal contrast. Indeed, consider the fol-
lowing (k;k)-threshold BSS: to share a secret s 2f0; 1g, the dealer randomly
chooses k1 random bits s 1 ;:::;s k1 and computes s k = ss 1 s k1 ,
where denotes the XOR operation. For i = 1;:::;k, the share for partic-
ipant i is the bit s i . In order to reconstruct the secret s in the BSS the k
participants are required to compute the XOR of their shares s 1 s k .
By arranging the k > 2 bits s 1 ;:::;s k as the leaves of a binary tree of height
dlog ke, where internal nodes have two children and the leaves are distributed
on at most two levels, the problem of computing the XOR of k bits can be
reduced to the problem of computing k 1 pairwise XORs, corresponding
to the internal nodes of the tree. Since each pairwise XOR operation can be