Improved schemes for visual cryptography

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. 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. For any value of k and n, where 2 less than or equal to k less than or equal to n, we give a construction for (k,n)-threshold VCS which improves on the best previously known constructions with respect to the pixel expansion (i.e., the number of subpixels each pixel of the original image is encoded into). We also provide a construction for coloured (2, n)-threshold VCS and for coloured (n, n)-threshold VCS. Both constructions improve on the best previously known constructions with respect to the pixel expansion.