Constructions and bounds for visual cryptography

A visual cryptography scheme for a set P of η participants is a method to encode a secret image SI into η 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 of 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 performing 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 η visual cryptography schemes. Finally, we consider graph-based access structures, that is access structures in which any qualified set of participants contains at least an edge of a given graph whose vertices represent the participants of the scheme. Our constructions for 2 out of n visual cryptography schemes are the best possible with respect to pixel expansion and relative difference.