Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-29T01:18:04.337Z 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: [email protected])
HANS ULRICH SIMON
Affiliation:
Fakultät für Mathematik, Ruhr-Universität Bochum, D-44780 Bochum, Germany (e-mail: [email protected])

Abstract

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.

Type
Research Article
Copyright
© 2003 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)