Visual Cryptography Schemes for Graph Based Access Structures

Visual cryptography schemes (VCS) have been introduced by Naor and Shamir [NS94] and involve a dealer encoding a secret image into shares that are distributed to a number of participants. In general, the collection of subsets of participants that can recover the secret is organized in an access structure. In this paper we consider graph based access structures, where participants are nodes of a graph G and only subsets containing an edge are allowed to reconstruct the secret image. We provide some bounds on the pixel expansion of path and cycle graphs, showing also a simple construction for such graphs for a generic number of n participants.