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.
Steve Lu Daniel Manchala Rafail Ostrovsky
University of California, Los Angeles Xerox Corporation
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
225-234
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）