TR00-003 Authors: Matthias Krause, Hans Ulrich Simon

Publication: 17th January 2000 19:05

Downloads: 1370

Keywords:

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)) <= 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.