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

operations. A further improvement can be obtained by considering as a build-
ing block a ( Qual ; Forb )-VCS with a perfect reconstruction of black pixels

having a smaller pixel expansion than m = P X2 Qual 2 jXj1 . In particular,
by considering the set 0 of all the minimal qualified subsets, and by using
the same technique proposed in [1], it is possible to construct a ( Qual ; Forb )-
VCS with a perfect reconstruction of black pixels, having pixel expansion
m 0 = P X2 0 2 jXj1 , thus reducing the number of transparencies held by each
participant.

9.4.2.2 The Scheme by Hu and Tzeng

In this section we describe an ideal contrast VCS with reversing for any access
structure ( Qual ; Forb ), due to Hu and Tzeng [9]. The construction uses the
basis matrices of the Naor-Shamir's (k;k)-VCS described in Section 9.2.1 along
with the properties of the XOR operator.
Let S 0 and S 1 be the basis matrices of the Naor-Shamir's (k;k)-VCS. The
key idea behind Hu and Tzeng's construction relies upon the fact that the
XOR of the bits belonging to a column of S 0 (S 1 , respectively) is zero (one,
respectively). With such an observation in mind, a (k;k)-VCS with reversing
may be easily constructed by issuing to the participant i a transparency of
the same size as the original image constructed as follows: for each white
(black, respectively) pixel the dealer chooses a column in S 0 (S 1 , respectively)
and puts on the transparency the i-th item of the chosen column. Since each
column of S 0 (S 1 , respectively) has an even (odd, respectively) number of
ones, it is easy to see that by XORring k transparencies the original image is
reconstructed without any loss of resolution. In the following we refer to this
construction as the XOR-(k;k)-VCS. As seen in Section 9.4.1, the problem
of computing the XOR of k transparencies can be reduced to a sequence of
stacking and reversing operations.
By using j 0 j executions of the XOR-(k;k)-VCS, a naive VCS with revers-
ing for any access structure ( Qual ; Forb ) can be obtained. Indeed, we simply
execute the above XOR-(jXj;jXj)-VCS for each qualied set X 2 0 . Such a
solution requires each participant to store as many transparencies as the num-
ber of qualified sets he belongs to. Each transparency has the same size as the
original image, on the other hand, each participant needs to keep track of the
correspondence between a transparency and the related qualified set. In order
to overcome such a drawback, Hu and Tzeng proposed a way to combine the
transparencies distributed to a participant in a single transparency. Such a
transparency is then used by a participant in a qualified set along with an ad-
ditional transparency to reconstruct the original image. Both transparencies
held by each participant are j 0 j times larger than the size of the secret im-
age. Indeed, each transparency contains j 0 j blocks and each qualied subset
of participants reconstructs, without loss of resolution, the secret image in a
single block, whereas the other reconstructed blocks contain only white pixels.