Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T11:32:22.503Z Has data issue: false hasContentIssue false

Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography

Published online by Cambridge University Press:  20 May 2003

MATTHIAS KRAUSE
Affiliation:
Theoretische Informatik, Universität Mannheim, D-68131 Mannheim, Germany (e-mail: krause@th.informatik.uni-mannheim.de)
HANS ULRICH SIMON
Affiliation:
Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780 Bochum, Germany (e-mail: simon@lmi.ruhr-uni-bochum.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
© 2003 Cambridge University Press