The Computer Journal Advance Access originally published online on December 1, 2005
The Computer Journal 2006 49(1):97-107; doi:10.1093/comjnl/bxh152
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Probabilistic Visual Cryptography Schemes
Università di Salerno, Dipartimento di Informatica ed Applicazioni, 84081 Baronissi (SA), Italy and 1 Dipartimento di Tecnologie dell'Informazione, Università di Milano, Via Bramante, 26013 Crema, Italy
* Corresponding author: robdep{at}dia.unisa.it
Visual cryptography schemes allow the encoding of a secret image, consisting of black or white pixels, into n shares which are distributed to the participants. The shares are such that only qualified subsets of participants can ‘visually’ recover the secret image. The secret pixels are shared with techniques that subdivide each secret pixel into a certain number m, m 
2 of subpixels. Such a parameter m is called pixel expansion. Recently Yang introduced a probabilistic model. In such a model the pixel expansion m is 1, that is, there is no pixel expansion. The reconstruction of the image however is probabilistic, meaning that a secret pixel will be correctly reconstructed only with a certain probability. In this paper we propose a generalization of the model proposed by Yang. In our model we fix the pixel expansion m 1 that can be tolerated and we consider probabilistic schemes attaining such a pixel expansion. For m = 1 our model reduces to the one of Yang. For big enough values of m, for which a deterministic scheme exists, our model reduces to the classical deterministic model. We show that between these two extremes one can trade the probability factor of the scheme with the pixel expansion. Moreover, we prove that there is a one-to-one mapping between deterministic schemes and probabilistic schemes with no pixel expansion, where contrast is traded for the probability factor.
Key Words: visual cryptography • probabilistic schemes • secret sharing