Visual Cryptography on Graphs

摘要

In this paper, we consider a new visual cryptography scheme that allows for sharing of multiple secret images on graphs: we are given an arbitrary graph (V, E) where every node and every edge are assigned an arbitrary image. Images on the vertices are "public" and images on the edges are "secret". The problem that we are considering is how to make a construction in which every vertex image is encoded and printed on a transparency, such that if two adjacent vertices' transparencies are overlapped, the secret image of their edge is revealed. We define the most stringent security guarantees for this problem (perfect secrecy) and show a general construction for all graphs where the cost (in terms of pixel expansion and contrast of the images) is dependent on the chromatic number of the cube of the underlying graph. For the case of bounded degree graphs, this gives us constant-factor pixel expansion and contrast.