Visual cryptography schemes with perfect reconstruction of black pixels

A (k,n)-threshold visual cryptography scheme ((k,n)-threshold VCS, for short) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the "visual" recovery of the secret image, but by inspecting less than k shares one cannot gain any information on the secret image. The "visual" recovery consists of xeroxing the shares onto transparencies, and then stacking them. Any k shares will reveal the secret image without any cryptographic computation. Visual cryptography schemes are characterized by two parameters: The pixel expansion, which is the number of subpixels each pixel of the original image is encoded into, and the contrast which measures the "difference" between a black and a white pixel in the reconstructed image. In this paper we analyze visual cryptography schemes in which the reconstruction of black pixels is perfect, that is, all the subpixels associated to a black pixel are black. We show that the minimum pixel expansion of such schemes can be simply computed by solving a suitable linear programming problem. Moreover, we give a construction for (3,n)-threshold VCS and a construction for (n - 1,n)-threshold VCS. These two constructions improve on the best previously known constructions with respect to the pixel expansion. © 1998 Elsevier Science Ltd. All rights reserved.