16-08-2012, 03:23 PM
Two secret sharing schemes based on Boolean operations
boolean ss-measure ss.pdf (Size: 1.37 MB / Downloads: 65)
Abstract
Traditional secret sharing schemes involve complex computation.A visual secret sharing (VSS) scheme decodes the secret without computation,
but each shadow is m times as big as the original. Probabilistic VSS solved the computation complexity and space complexity problems at
once. In this paper we propose a probabilistic (2, n) scheme for binary images and a deterministic (n, n) scheme for grayscale images. Both use
simple Boolean operations and both have no pixel expansion. The (2, n) scheme provides a better contrast and significantly smaller recognized
areas than other methods. The (n, n) scheme gives an exact reconstruction.
Introduction
A secret kept in a single information-carrier could be easily
lost or damaged. Secret sharing (SS) schemes, called (k, n)
threshold schemes, have been proposed since late 1970s to encode
the secret into n pieces (“shadows” or “shares”) that the
pieces can be distributed to n participants at different locations
[1,2]. The secret can only be reconstructed from k or more
pieces (kn). A (k, n) threshold scheme is “Shannon perfectly
secure” if the knowledge of any k−1 or fewer shadows provide
no information about the original secret [3–5]. Although some
schemes were designed to only allow a particular sub-group of
qualified participants to decode the secret [6–10], the schemes
designed for any subgroup of k participants are most common
[1,2,11–35]. Among them, the special cases of (2, n) schemes
and (n, n) schemes receive more attention.
VSS scheme
A number of other SS schemes [11–17] are related to Ref. [2].
Naor and Shamir [18] proposed a VSS scheme that encodes
the secret image into n shadow images, each of which does not
reveal any information of the secret image. Every original pixel
is subdivided into a collection of m black and white sub-pixels
in each share. The shadow images are printed on transparencies
and can be easily reconstructed by the human visual system
without computations. When shadows are stacked together in a
way that properly aligns the subpixels, one can see a recovered
image whose black subpixels are represented by the Boolean
“OR”-ed corresponding subpixels in the shadows.
Schemes for grayscale images
Most SS schemes were designed for binary (black and white)
images, the optimal (n, n) VSS schemes for black and white
image are given in Ref. [18]. Blundo et al. [28] defined and analyzed
visual cryptography schemes for grayscale images and
provided the necessary and sufficient conditions for constructing
a grayscale scheme for general access structures. The minimum
relative differences are obtained in any (n, n) VSS for
grayscale images.
Some schemes have been proposed for color images [19–33].
Among them, the special cases of (n, n) schemes have received
more attention [23–32]. Verheul and Van Tilborg [19] introduced
a theoretical construction for a (k, n) VSS for secret images.
Blundo et al. [25] provided a method for construction of a
maximal-contrast color (2, n) visual cryptography scheme and
two constructions for a color (n, n) threshold VSS. This method
is an improvement of the one given in Ref. [19] with respect to
pixel expansion. In Ref. [26], Yang and Laih proposed a new
construction method for a color VSS on the basis of black-andwhite
VSS and got much better pixel expansion than that of
Ref. [19]. Cimato et al. [27] provided a characterization of a
c-color (k, n) threshold scheme with optimal contrast. The results
in Refs. [26–28,31] have the same pixel expansion and
relative difference although different construction methods are
used, when treating different gray-levels as different color.
Conclusions
In this paper we have presented two SS schemes for images.
One is a (2, n) scheme for binary images and the other is an
(n, n) scheme for binary and grayscale/color images. Boolean
AND and XOR operations are used in the (2, n) algorithm and
only XOR operations are used in the (n, n) algorithm. The
proposed (2, n) scheme is probabilistic and the contrast of the
recovered image is 1
2 , higher than other probabilistic (2, n)
schemes when n is greater than 2. The same as other ProbVSSs,
no pixel expansion is involved. The proposed (n, n) scheme is
deterministic and the reconstructed image is exactly the same as
the original. Common software tools, such as Photoshop can be
used to implement the Boolean operations and reconstruct the
secret images.