Contrast optimal threshold visual cryptography schemes

A (k, n)-threshold visual cryptography scheme (VCS) 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. However, by inspecting less than k shares one cannot gain any information on the secret image. The "visual" recovery consists of copying 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 the contrast of the reconstructed image for a (k, n)-threshold VCS. We define a canonical form for a ( k, n)-threshold VCS and provide a characterization of a ( k, n)-threshold VCS. We completely characterize a contrast optimal (n- 1, n)-threshold VCS in canonical form. Moreover, for n greater than or equal to 4, we provide a contrast optimal ( 3, n)-threshold VCS in canonical form. We first describe a family of (3, n)-threshold VCS achieving various values of contrast and pixel expansion. Then we prove an upper bound on the contrast of any (3, n)-threshold VCS and show that a scheme in the described family has optimal contrast. Finally, for k = 4, 5 we present two schemes with contrast asymptotically equal to 1/64 and 1/256, respectively.