Determining the optimal contrast for secret sharing schemes in visual cryptography

Krause, Matthias ; Simon, Hans Ulrich

Document Type: Working paper
Year of publication: 2000
The title of a journal, publication series: Electronic Colloquium on Computational Complexity : ECCC
Volume: TR00-003
Place of publication: Trier
Publishing house: Universität Trier
ISSN: 1433-8092
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause)
Subject: 004 Computer science, internet
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)) <= 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.
Additional information: Online-Ressource

Dieser Eintrag ist Teil der Universitätsbibliographie.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item