Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-012 | 14th December 1995 00:00

Visual Cryptography for General Access Structures


Authors: Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson
Publication: 12th February 1996 14:03
Downloads: 1324


A visual cryptography scheme for a
set $\cal P $ of $n$ participants is a method to encode a secret
image $SI$ into $n$ shadow images called shares, where each participant in
$\cal P$ 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\subseteq{\cal P}$ 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.

ISSN 1433-8092 | Imprint