Visual cryptography for color images

: formal security analysis and new construction

Abstract

Visual Cryptography, introduced by Naor and Shamir in 1994, is a secret shar- ing scheme for black-and-white images. It divides a secret image into a number of shares, in such a way that without adequate number of shares, no one can re- veal any information about the secret image. The covert information can only be recovered if and only if an adequate number of shares are superimposed. During the secret recovery process, no computation is required. Due to the rapid development of multimedia technology, secret images are no longer con- fined to black-and-white. Instead, more work has recently been taken place for color images. One of the major research problems in this field is to construct information-theoretic secure while high quality visual cryptography schemes for color images. However, most of the current work is constructed on the scheme proposed by Naor and Shamir. In this thesis, we target to contribute on both cryptanalysis and exploration of new way to construct provably secure while having high image quality visual cryptography schemes for color images. We start off our research by reviewing some of the existing schemes for color images. One of the earliest and mostly referred work on visual cryptography schemes for color images is Hou’s work in 2003. In his paper, three schemes have been proposed which enjoy the high quality and also have widely been believed that they achieve information theoretic security. However, there is no formal security analysis carried out since their first appearance dated back to six years ago. The question which leaves unanswered is whether all the three Hou’s schemes which achieve different level of quality are secure as they are believed to be. In the first part of this thesis, we target to answer this question for these three schemes. In particular, we show that the first scheme is only secure for some specific two-color secret images. For other type of images, unfortunately, security cannot be guaranteed. We show that a randomly chosen two-color secret image can be compromised with probability 4 7 . The advantage will increase to 6 7 if more shares are collected by the adversary. If the secret image has three or four colors, we show that the adversary can compromise it with probability 4 7 and 8 35 , respectively. For analyzing Hou’s second and third scheme, we formalize an information theoretic definition on the security of visual cryptography schemes for color images. We show that both schemes can achieve our definition and no apparent attack can be found against them.

Date of Award	2 Oct 2009
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Shek Duncan WONG (Supervisor)