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 it or more shares enable the "visual" recovery of the secret image, but by inspecting less than fi 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 it 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. (C) 1998 Elsevier Science Ltd. All rights reserved.