Constructions and Bounds for Visual Cryptography

摘要

A visual cryptography scheme for a set P of n participants is a method to encode a secret image SI into n images in such a way that any participant in P receives one image and only qualified subsets of participants can "visually" recover the secret image, but non-qualified sets fo participants have no information, in an information theoretical sense, on SI. A "visual " recover for a set X P consists of stacking together the images associated to participants in X. The participants in a qualified set X will be able to see the secret image without any knowledge of cryptography and without performign any cryptographic computation. IN this paper we propose two techniques to construct visual cryptography schemes for any access structure. We analyze the structure of visual cryptography schemes and we prove bounds on the size of the image distributed to the participants in the scheme. We provide a novel technique to realize k out of n visual cryptography schemes. Finally, we consider graph-based access structurs, that is access structures in which any qualified set of participants contains at least an edge of a given graph whose vertices represent the aprticipants of the scheme. Our constructions for 2 out of n visual cryptography schemes are the best possible with respect to pixel expansion nad relative difference.