Randomness in secret sharing and visual cryptography schemes

Secret sharing schemes allow a secret to be shared among a group of participants so that only qualified subsets of participants can recover the secret. A visual cryptography scheme (VCS) is a special kind of secret sharing scheme in which the secret to share consists of an image and the shares consist of xeroxed transparencies which are stacked to recover the shared image. In this paper, we analyze the relationship between secret sharing schemes and VCSs, focusing our attention on the amount of randomness required to generate he shares. We prove hat secret sharing schemes for a set of secrets of size two (BSSs) and VCSs are "equivalent" with respect to the randomness. Indeed, we show how to transform a BSS for a given access structure into a VCS for the same access structure while preserving the randomness of the original scheme. We provide both upper and lower bounds on the randomness of BSSs. All VCSs presented in this paper allow a perfect reconstruction of black pixels. (C) 2003 Elsevier B.V. All rights reserved.