(Extended) visual cryptography scheme for color images with no pixel expansion

Abstract

In 1994, Naor and Shamir introduced the notion of Visual Cryptography Scheme (VCS), which is the secret sharing of digitized images. A k-out-of-n VCS splits an image into n secret shares which are indistinguishable from random noise. These shares are then printed on transparencies. From any k - 1 or less shares, no information about the original image (other than the size of it) will be revealed. The image can only be recovered by superimposing k or more shares. This recovery process does not involve any computation. It makes use of the human vision system to perform the pixel-wise OR logical operation on the superimposed pixels of the shares. When the pixels are small enough and packed in high density, the human vision system will average out the colors of surrounding pixels and produce a smoothed mental image in a human's mind. Early VCS schemes mainly focused on black-and-white secret images. If the original image is not black-and-white, for example, a gray-scale image, dithering is employed to preprocess the original image. However, this technique would degrade the image quality. Another issue that is common to most of the previous work is pixel expansion, which means that the size of each secret share is several times larger than that of the original image. Two important parameters which govern the quality of reconstructed images are m (pixel expansion rate which represents the loss in resolution from the original image to the shares) and α (the relative difference in weight between the superimposed shares that come from one color level (e.g. black) and another color level (e.g. white)). For image integrity, a good VCS should make the value of m close to one (i.e. no pixel expansion) and α as large as possible. It is unknown if there is a scheme which satisfies all the following four commonly desired properties: (1) supporting images of arbitrary number of colors; (2) no pixel expansion; (3) supporting k-out-of-n threshold setting; and (4) a 'tunable' number of color levels in the secret share creation process. We answer this question affirmatively by proposing a k-out-of-n threshold visual cryptography scheme which satisfies all these properties. In particular, our scheme utilizes a probabilistic technique for achieving no pixel expansion and generically converts any k-out-of-n threshold visual cryptography scheme for black-and-white images into one that supports color images. Furthermore, we propose an extension of our VCS called Extended Visual Cryptography Scheme (EVCS). In this EVCS, the n shares which are generated from the secret image also carry n meaningful and independently chosen images. To the best of our knowledge, our EVCS is the first scheme for color images that supports the general k-out-of-n secret sharing while having no pixel expansion.

Date of Award	4 Oct 2010
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Qing LI (Supervisor) & Shek Duncan WONG (Co-supervisor)