期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A visual cryptography scheme for a
set of n participants is a method to encode a secret
image SI into n shadow images called shares, where each participant in
receives one share. Certain qualified subsets of participants
can ``visually'' recover the secret image, but
other, forbidden, sets of
participants have no information (in an information-theoretic sense)
on SI. A ``visual'' recovery for a set X consists
of xeroxing the shares given to the participants in X
onto transparencies, and then stacking them.
The participants in a qualified set X will be able to see the secret
image without any knowledge of cryptography and without
performing any cryptographic computation. This cryptographic paradigm
has been introduced by Naor and Shamir \cite{NaSh}.
In this paper we propose two techniques to construct visual cryptography
schemes for general access structures. We analyze the structure of visual
cryptography schemes and we prove bounds on the size of the shares
distributed to the participants in the scheme. We provide a novel technique
to realize k out of n threshold
visual cryptography schemes. Finally, we consider
graph-based access structures, i.e., access structures in which any
qualified set of participants contains at least an edge of a given graph
whose vertices represent the participants of the scheme.
