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

that the human visual system averages their individual black/white contribu-
tions. The encoding is done in such a way that certain subsets of participants,
called qualied sets, can "visually" recover the secret image, but other sub-
sets of participants, called forbidden sets, cannot gain any information (in an
information-theoretic sense) about the secret image by inspecting their shares.
A "visual" recover for a set of qualied participants consists of xeroxing each
share onto a separate transparency, of stacking together the transparencies
and projecting the result with an overhead projector. If the transparencies
are aligned carefully, then the participants will be able to see the secret image
(without any knowledge of cryptography and without performing any crypto-
graphic computation).
This cryptographic paradigm was introduced by Naor and Shamir [11].
They analyzed the case of (k;n)-threshold visual cryptography schemes, in
which the qualified subsets of participants have cardinality k, whereas, the
forbidden subsets of participants have cardinality less than k. Some results on
(k;n)-threshold visual cryptography schemes ((k;n)-threshold visual cryptog-
raphy scheme (VCS), for short) can be found in [1, 2, 5, 8, 10, 12]. The model
by Naor and Shamir has been extended in [1] to general access structures (an
access structure is a specification of all qualified and forbidden subsets of par-
ticipants), where general techniques to construct visual cryptography schemes
for any access structure have been proposed.
Visual cryptography schemes are characterized by two parameters: The
pixel expansion, corresponding to the number of subpixels contained in each
share (transparency) and the contrast, which measures the "dierence" be-
tween a black and a white pixel in the reconstructed image. Visual cryp-
tography schemes such that, in the reconstructed image, all the subpixels
associated to a black pixel are black, are referred to as visual cryptography
schemes with perfect reconstruction of black pixels. Such schemes have been
considered in [12, 4, 3]. Unfortunately, it is not possible to obtain visual cryp-
tography schemes with perfect reconstruction of both black and white pixels.
Such schemes are said to have ideal contrast.
In order to obtain perfect black visual cryptography schemes whose recon-
struction of white pixels is almost perfect, Viet and Kurosawa [13] proposed
a different kind of VCS, called VCS with reversing. Such VCSs require the in-
troduction of an extra noncryptographic operation, that participants can use
to reconstruct the image. Such an operation, which can be easily performed
by many copy machines, is applied to a transparency and creates another
transparency in which black pixels are reversed to white pixels and vice versa.
Specifically, Viet and Kurosawa [13] proposed to run c times (with c arbi-
trary constant) the distribution phase of a VCS with perfect reconstruction of
black pixels and pixel expansion m, hence requiring each participant to store
c m subpixels for each pixel of the original image. The larger the number
of runs c, the better the contrast of the resulting VCS with reversing. The
drawback of such a solution is that the number of pixels in the reconstructed
image, which depends on both the number of runs and on the pixel expansion