Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography

This paper shows that the largest possible contrast Ck, n in an k-out-of-n secret sharing scheme is approximately 4 − − ( k− − 1). More precisely, we show that \(4^{-(k-1)} \le C_{k,n} \le 4^{-(k-1)}n^k/(n(n-1)\cdots(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 occurring in Approximation Theory.