Cryptography Reference
In-Depth Information
participants. The shares are such that only qualified subsets of participants
can "visually" recover the secret image. The secret pixels are shared with
techniques based on subdividing each secret pixel into a certain number m,
m 2 of subpixels. Such a parameter m is called the pixel expansion, since
the reconstructed shared image becomes m times bigger than the original.
This cryptographic paradigm was introduced by Naor and Shamir [16]. They
analyzed the case of (k;n)-threshold visual cryptography schemes, in which a
black and white secret image is visible if and only if any k transparencies are
stacked together.
The pixel expansion has a number of drawbacks, affecting the quality of
the reconstructed image and the complexity of the visual cryptography scheme
(VCS). In some cases, the pixel expansion is exponential, and this limits the
applicability of the VCS. In general, the "quality" of the reconstructed image
depends both on the pixel expansion and on the contrast, which is another
measure of the goodness of the scheme. A number of papers studying the
best pixel expansion and the best contrast have appeared in the literature. A
partial list of such papers include [2, 4, 5, 6, 7, 12, 14, 15]. Some other papers
have focused on different models or properties. For example, in [1], visual
cryptography schemes for general access structures (where the qualified set
of participants are arbitrary and not defined by a threshold of participants)
have been studied. Schemes where the shares show meaningful pictures (not
related to the secret) are studied in [3]. In [24] the problem of not distorting
the original image is considered. Some research has also considered the case
of colored images (see for example [10, 9, 19, 25]).
To deal with the pixel expansion, Yang [22, 23] has introduced a new
model of visual cryptography in which the reconstruction of the secret image
is probabilistic, but the shares have the same size of the secret image, i.e., the
schemes have no pixel expansion. To be fair, a first attempt to provide VCS
without pixel expansion has been done by Ito et al. in [13]. In both Ito and
Yang models, each pixel is reconstructed "OR"ing the corresponding single
pixel contained in the shares. Such models are called probabilistic, because
they give no absolute guarantee on the correct reconstruction of the original
pixel: in some cases, the reconstructed pixel is wrong. This differs from the
traditional VCS, which are now called deterministic, where the reconstruction
of an "approximation" of the secret pixel is guaranteed. Here the approxi-
mation means that a white (black) pixel can be, in some cases, replaced in
the reconstructed image by a set of subpixels having a given set of white-
ness (blackness). Since in probabilistic models the secret pixel is correctly
reconstructed with some probability, the quality of the reconstructed images
depends on how big is the probability of correctly reconstructing the secret
pixels.
Between deterministic schemes and probabilistic schemes it is possible to
set a trade-off. In a deterministic scheme a certain pixel expansion is paid
for the guarantee of a correct reconstruction. In a probabilistic scheme a re-
construction with no pixel expansion is paid with a (small) probability of
Search WWH ::
Custom Search