On the contrast in visual cryptography schemes (Q1819123)

A visual cryptography scheme (VCS) for a set \(\mathcal{P}\) of \(n\) participants is a method to encode a secret image \(SI\) into shadow images, called shares, where each participant in \(\mathcal{P}\) receives one share. Certain qualified subsets of participants can visually recover the image but other, forbidden sets have no information on the recovery, in an information theoretic sense. A visual recovery for a set \(X \subseteq \mathcal{P}\) consists of xeroxing the shares given to participants onto transparencies and stacking them to view the resulting image. Such a scheme was first introuced by \textit{M. Naor} and \textit{A. Shamir} [Eurocrypt `94, Lect. Notes Comput Sci. 950, 1-12 (1995; Zbl 0878.94048)] in which any \(k\) out of \(n\) participants could view an image. It is assumed here that the secret image consists of black and white pixels, each pixel appearing in \(n\) versions (shares), one for each transparency. Each share is a collection of \(m\) black and white subpixels. The structure can be viewed as a collection of \(n \times m\) Boolean matrices. The gray level of the combined share when the transparencies are stacked is proportional to the Hamming weight for the pixel. This paper analyzes the contrast of the reconstructed image for \(k\) out of \(n\) VCS's. This contrast is measured by the relative difference of the scheme, a notion introduced here. In the case of \(2\) out of \(n\) threshold schemes an exact formula of the optimal relative difference is obtained. It is shown how to realize this optimal relative difference with minimal pixel expansion. Upper and lower bounds on the optimal relative difference are obtained for the case of \(k\) out of \(n\) threshold schemes for \(k \geq 3\). A lower bound on the pixel expansion is also obtained for this case. The notion of a basis matrix is introduced for the construction of VCS's and a necessary and sufficient condition is given for a pair of \(n \times m\) matrices to be the basis matrices of a \(k\) out of \(n\) VCS with pixel expansion \(m\).