Color Image

Des. Codes Cryptogr. (2011) 61:223–249 DOI 10.1007/s10623-010-9449-x

A general method for construction of (t, n)-threshold visual secret sharing schemes for color images
Hiroki Koga · Takeru Ishihara

Received: 20 June 2007 / Revised: 1 September 2010 / Accepted: 20 November 2010 / Published online: 1 January 2011 © Springer Science+Business Media, LLC 2010

Abstract This paper isconcerned with the construction of basis matrices of visual secret sharing schemes for color images under the (t, n)-threshold access structure, where n ≥ t ≥ 2 are arbitrary integers. We treat colors as elements of a bounded semilattice and regard stacking two colors as the join of the two corresponding elements. We generate n shares from a secret image with K colors by using K matrices called basismatrices. The basis matrices considered in this paper belong to a class of matrices each element of which is represented by a homogeneous polynomial of degree n. We first clarify a condition such that the K matrices corresponding to K homogeneous polynomials become basis matrices. Next, we give an algebraic scheme for the construction of basis matrices. It is shown that under the (t, n)thresholdaccess structure we can obtain K basis matrices from appropriately chosen K − 1 homogeneous polynomials of degree n by using simple algebraic operations. In particular, we give basis matrices that are unknown so far for the cases of t = 2, 3 and n − 1. Keywords Visual cryptography · Visual secret sharing · Threshold scheme · Contrast 94A62

Mathematics Subject Classification (2000) 1 IntroductionVisual secret sharing scheme (or visual cryptography) is a new field of cryptography that originates from a seminal paper by Naor and Shamir [20]. In a visual secret sharing scheme

Communicated by P. Wild. H. Koga (B ) Graduate School of Systems and Information Engineering, University of Tsukuba, 1-1-1 Tennoudai, Tsukuba-shi, Ibaraki 305-8573, Japan e-mail: koga@iit.tsukuba.ac.jp T. Ishihara NTTDOCOMO, Inc., 3-6, Hikarinooka, Yokosuka-shi, Kanagawa 239-8536, Japan e-mail: ishiharat@nttdocomo.co.jp

123

224

H. Koga, T. Ishihara

(hereinafter abbreviated as VSSS) with n ≥ 2 participants, a dealer generates n images called shares from a secret image. Each share is printed on a transparency sheet and is securely distributed to each participant. Under the (t, n)-threshold accessstructure, the secret image is recovered from any collection of exactly t shares simply by stacking the t shares in an arbitrary order, with no information on the secret image revealed by any collection of less than t shares, where t is an arbitrarily fixed integer satisfying n ≥ t ≥ 2. A VSSS is usually realized by matrices called basis matrices. Since the proposal of VSSS, much research on VSSS hasbeen published. Most of the research is related to the optimization of basis matrices, extensions of frameworks, and the investigation of applications. In particular, VSSS for color images has been discussed in various papers [1,3–5,8–11,13–15,21–24]. When we consider a VSSS for color images, we need to take a mathematical model of colored pixels into consideration. References [3,4,24] give basismatrices under the model of Verheul and van Tilborg [23]. On the other hand, [1,9,15] discuss constructions of basis matrices under the model of Koga and Yamamoto [14], where pixels are treated as elements of a semilattice and stacking pixels is regarded as taking the join of elements of the semilattice. Recently, Cimato et al. [5] gave a new model of stacking colored pixels that is closelyrelated to the model in [14]. Furthermore, [8,10,21,22] discuss the VSSS for images such as natural images that contain many colors. In this paper, we propose a new method for the construction of basis matrices of a VSSS under the model of colors in [14]. The new method enables us to obtain basis matrices of the VSSS under the (t, n)-threshold access structure for any n ≥ t ≥ 2. We can obtain basis...