language: en

Extended Capabilities for Visual Cryptography

Giuseppe Ateniese 1 , Carlo Blundo 2 , Alfredo De Santis 2 , and Douglas R. Stinson 3
1 Dipartimento di Informatica e Scienze dell'Informazione, Universita di Genova,
via Dodecaneso 35, 16146 Genova, Italy
E-mail: ateniese@disi.unige.it
2 Dipartimento di Informatica ed Applicazioni, Universita di Salerno,
84081 Baronissi (SA), Italy
E-mail: {fcarblu,adsg}@dia.unisa.it
3 Department of Combinatorics and Optimization University of Waterloo,
Waterloo Ontario, N2L 3G1, Canada

Abstract An extended visual cryptography scheme, EVCS for short, for an access structure ( Qual ; Forb ) on a set of n participants, is a technique to encode n images in such a way that when we stack together the transparencies associated to participants in any set X 2 Qual we get the secret message with no trace of the original images, but any X 2 Forb has no information on the shared image. Moreover, after 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 contrast of the image on each transparency for (k; k)-threshold EVCS (in a (k; k)-threshold EVCS the image is visible if and only if k transparencies are stacked together). This yields a necessary and sufficient condition for the existence of (k; k)-threshold EVCS for the values of such contrasts. In case a scheme exists we explicitly construct it. * A general technique to implement extended visual cryptography schemes, which uses hypergraph colourings. This technique yields (k; k)-threshold EVCS which are optimal with respect to the pixel expansion. Finally, we discuss some applications of this technique to various interesting classes of access structures by using relevant results from the theory of hypergraph colourings.

Keywords: Visual Cryptography, Secret Sharing Schemes.

1 Introduction