ECCC-Report TR00-003https://eccc.weizmann.ac.il/report/2000/003Comments and Revisions published for TR00-003en-usMon, 17 Jan 2000 19:05:50 +0200
Paper TR00-003
| Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography |
Matthias Krause,
Hans Ulrich Simon
https://eccc.weizmann.ac.il/report/2000/003This 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)) <= C_{k,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.
Mon, 17 Jan 2000 19:05:50 +0200https://eccc.weizmann.ac.il/report/2000/003