Network Science Seminar

Date and Location

May 26, 2015 - 4:00pm
Network Science Lab, Bldg 434, Rm 122


John Retterer-Moore and Arya Pourzanjani
Computer Science
UC Santa Barbara


Computer Science graduate students John Retterer-Moore and Arya Pourzanjani will each present a short overview of a recent paper.

John will present "Visual Cryptography on Graphs" (Steve Lu, UCLA,  Daniel Manchala, Xerox Corporation, and Rafail Ostrovsky, UCLA). 

Abstract: 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 such that when the encoded images of two adjacent vertices are printed on transparencies and overlapped, the secret image corresponding to the 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 proportional to 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. This compares favorably to previous works, where pixel expansion and contrast are proportional to the number of images.