RUB » LMI » Mitarbeiter » H. Simon » Publications in Proceedings » On Contrast-Optimal Secret Sha...

On Contrast-Optimal Secret Sharing Schemes in Visual Cryptography

Abstract.  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)<Ck,n<4- (k-1)nk/(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. (A similar relation has been used recently in the paper [LN2] of Linial and Nisan about Approximate Inclusion-Exclusion).

References:
[LN2]        N. Linial, N. Nisan, Approximate inclusion-exclusion, Combinatorica 10, 349-365, 1990.