Determining the Optimal Contrast for Secret Sharing Schemes in visual Cryptography.

Abstract.  This paper shows that the largest possible contrast Ck,n in a k-out-of-n secret sharing scheme is approximately 4^{-(k-1)}. More precisely, we show that 4^{-(k-1)} <= Ck,n <= 4^{-(k-1)}n^k/(n(n-1)...(n-(k-1))). This implies that the largest possible contrast equals 4^{-(k-1)} in the limit when n approaches infinity. For large n, the above bounds leave almost no gap. For values of n that come close to k, we will present alternative bounds (being tight for n=k). The proofs of our results proceed by revealing a central relation between the largest possible contrast in a secret sharing scheme and the smallest possible approximation error in problems occuring in Approximation Theory.