Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography
Matthias Krause, Hans Ulrich Simon · Combinatorics Probability Computing · 2003
This paper shows that the largest possible contrast $C_{k,n}$ in a $k$ -out-of- $n$ secret sharing scheme is approximately $4^{-(k-1)}$ . More precisely, we show that $4^{-(k-1)} \leq C_{k,n} \leq 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 finding a relationship between the largest possible contrast in a secret sharing scheme and the smallest possible approximation error in problems occurring in approximation theory.