Extended capabilities for visual cryptography

An extended visual cryptography scheme (EVCS), for an access structure (Gam ma (Qual), Gamma (Forb)) on a set of n participants, is a technique to enco de it images in such a way that when we stack together the transparencies a ssociated to participants in any set X is an element of Gamma (Qual) we get the secret message with no trace of the original images, but any X is an e lement of Gamma (Forb) has no information on the shared image. Moreover, af ter the original images are encoded they are still meaningful, that is, any user will recognize the image on his transparency. The main contributions of this paper are the following: A trade-off between the contrast of the reconstructed image and the contras t of the image on each transparency for (k,k)-threshold EVCS (in a (k,k)-th reshold EVCS the image is visible if and only if k transparencies are stack ed together). This yields a necessary and sufficient condition for the exis tence of (k,k)-threshold EVCS for the values of such contrasts. In case a s cheme exists we explicitly construct it. A general technique to implement EVCS, which uses hypergraph colourings. Th is technique yields (k,k)-threshold EVCS which are optimal with respect to the pixel expansion. Finally, we discuss some applications of this techniqu e to various interesting classes of access structures by using relevant res ults from the theory of hypergraph colourings. (C) 2001 Elsevier Science B. V. All rights reserved.