Lehrstuhl Mathematik & InformatikConstruction of Visual Secret Sharing Schemes with Almost Optimal Contrast
Abstract. It was shown in [KS3] that the largest possible contrast C(k,n) in a k-out-of-n secret sharing scheme is approximately 4-(k-1) (with equality in the limit when n approaches infinity). However, the proof of this result was not constructive and did not answer the question how schemes with almost optimal contrast might look like. In this paper, we present an easy and universal construction of an appropriate k-out-of-n secret sharing scheme. The construction works for all values of k and n and achieves contrast-optimality in the limit with a fairly small gap for finite n. For small values of k (and all values of n), we get even contrast-optimality (without any gap). Finally, we argue that the problem to close the gap in general is related to a long standing open question in Approximation Theory.
References:
- [KS3] Matthias Krause and Hans Ulrich Simon.
- On contrast-optimal secret sharing schemes in visual cryptography. Technical Report 255, Fakultät für Mathematik der Ruhr-Universität Bochum, D-44780 Bochum, 1999.