New Results on the Randomness of Visual Cryptography Schemes
Annalisa De Bonis, Alfredo De Santis · Birkhäuser Basel eBooks · 2001
Visual cryptography schemes have been introduced in 1994 by Naor and Shamir as a mean to share images among a given group of participants. A visual cryptography scheme (VCS) for a set P of n participants encodes a secret image into n shadow images called shares each of which is given to a distinct participant. Certain qualified subsets of participants can recover the secret image, whereas forbidden subsets of participants have no information on the secret image. The shares given to participants in X ⊑ P are xeroxed onto transparencies. If X is qualified then the participants in X can visually recover the secret image by stacking their transparencies without any cryptography knowledge and without performing any cryptographic computation. In this paper we provide a new technique to derive lower bounds on the randomness of VCSs for any access structure. We also analyse minimum randomness ( k , k )-threshold VCSs thus giving a new insight into the structure of these schemes.