Improved (k, n) Visual Secret Sharing Based on Random Grids

Abstract

(k, n) Visual secret sharing (VSS) is a cryptographic procedure in which secret information in the form of images is encoded into ‘n’ shares (or shadow images) such that secret is recovered only if ‘k’ or more shares are superimposed, whereas superimposing not as much as ‘k’ shares provides no information regarding secret. In this paper, (k, n) VSS based on random grids is proposed which requires no design for codebook and does not involve pixel expansion. The proposed scheme produces better results in terms of improved contrast which decides visual quality. Many experiments are executed to assess the efficacy and security of the proposed approach. The proposed scheme is compared with existing schemes to show its benefits.

1 Introduction

Since the Internet applications have started growing, more digital information is accessed and distributed via Internet. But security of such digital information is still a threat. To protect digital information from unauthorized access, various techniques like cryptography, steganography and watermarking are employed. But these involve much computational cost in the decryption phase. So, optimal solution for the protection of digital images is visual secret sharing (VSS). This scheme does not require complex computations to decode the secret.

Naor and Shamir [1] presented (k, n) VSS technique. In (k, n) VSS, the secret visual information is encoded into ‘n’ random and innocent shares (also called shadow images), with each share given to one participant. Shares are xeroxed onto transparencies which separately do not disclose any useful data regarding the secret. Human visual system (HVS) can easily recovers the secret when any ‘k’ or more transparencies are superimposed together, whereas stacking transparencies less than ‘k’ provides no data about the secret. The visual quality increases as the number of shares to be stacked increases. Unfortunately, this scheme requires codebook design, also expands pixel and gives the poor visual quality of the revealed secret.

Kafri and Keren [2] investigated the idea of sharing images (binary) securely using a novel approach of random grids (RG) in 1987: encrypting secret into two innocent looking random grids (shadow images) which are as large as the original secret image. The decoding phase recovers secret by stacking two random grids together. This RG-based VSS requires no codebook designing and eliminates the pixel expansion problem.

The remaining portion of the proposed paper is structured as follows: related work and short explanation of traditional RG-based VSS is given in Sect. 2. Section 3 introduces the proposed (k, n) VSS based on random grids, explains some definitions and states assumptions. Results based on experiments and comparisons with existing schemes are presented in Sect. 4, while Sect. 5 gives the conclusion of paper.

2 Related Work

VSS schemes based on general access structures were presented [3] to give more adaptable sharing system. Many researchers tried to extend Naor and Shamir’s work to improve the visual quality [4, 5] and reduce pixel expansion [6, 7]. Scheme [7] eliminates the pixel expansion problem completely. Conventional VSS makes use of random shares which attract the hacker’s attention. So, to solve this problem, extended visual secret sharing [8, 9] was developed which uses some innocent looking images as shares rather than random shares. It also tackles the issue which arises during managing non-meaningful shares. Many researchers [10, 11] introduced Halftone visual cryptography (HVC) which creates halftone shares consisting of significant information.

Shyu [12] broadened Kafri and Karen’s approach to produce VSS based on random grids which encodes color images and grayscale images using halftoning. Schemes [2, 13, 14] reduce pixel expansion but are not meant for generalized (k, n) VSS. Shyu [14] presented (n, n) visual cryptography sharing based on random grids. Chen and Tsao [13] used the concept of random grids to demonstrate (2, n) and (n, n) VSS with its ability to encode binary as well as color images. Chen and Tsao [15] gave a new method to formulate (k, n) threshold VCS schemes by RG. Guo et al. [16] presented (k, n) VSS using concept of RG which helps increase the visual quality as long as k is less than or equal to n/2. The proposed paper introduces (k, n) random grid-based VSS scheme. The original secret can be revealed with improved contrast by stacking (Boolean OR) sufficient number of shares together by HVS.

Traditional (2, 2) RG-based VSS [15], which is used in our proposed scheme, is explained below. A random grid [2] is characterized as a rectangular matrix of pixels in which every element is pixel and can have one of two possible values, i.e., ‘0’ meaning white or transparent pixel and ‘1’ meaning black or opaque pixel. Each pixel has an equal probability of being transparent or opaque. $\varvec{ } \otimes$ and ⊕ denote Boolean OR and XOR operations, respectively.

Traditional (2, 2) RG-based VSS

Input: Binary secret image SI with size r × c

Output: Two random grids $RS_{1}$ and $RS_{2}$

• 1. Create the first random grid $RS_{1}$ by randomly choosing each pixel to be either ‘0’ or ‘1.’

• 2. Compute the second random grid $RS_{2}$ as given in Eq. (1) for each secret pixel $SI\left( {p,q} \right)$

$$ RS_{2 } \left( {p,q} \right) = \left\{ {\begin{array}{*{20}c} {RS_{1} \left( {p,q} \right), \,if\,SI\left( {p,q} \right) = 0} \\ {} \\ {\overline{{RS_{1} \left( {p,q} \right)}} \,if\,SI\left( {p,q} \right) = 1} \\ \end{array} } \right\} $$

(1)

In recovery phase, recovered secret image RI is obtained by stacking (Boolean OR) of both shares $RS_{1 }$ and $RS_{2 }$ as given in Eq. (2).

$$ \begin{aligned} RI\left( {p,q} \right) & = RS_{1 } \left( {p,q} \right) \otimes RS_{2 } \left( {m,n} \right) \\ & = \left\{ {\begin{array}{*{20}c} {RS_{1 } \left( {p,q} \right) \otimes RS_{1 } \left( {p,q} \right) = RS_{1} \left( {p,q} \right),\,if\;SI\left( {p,q} \right) = 0 } \\ \\ {RS_{1 } \left( {p,q} \right) \otimes \overline{{RS_{1 } \left( {p,q} \right) }} = 1,\;if\,SI\left( {p,q} \right) = 1} \\ \end{array} } \right. \\ \end{aligned} $$

(2)

If secret pixel is black, i.e., $SI\left( {m,n} \right) =$ 1, then the recovered image bit is always black, whereas the recovered bit has half probability to be white or black if $SI\left( {m,n} \right) =$ 0 because $RS_{1}$ is generated randomly.

3 The Proposed Scheme

This section introduces (k, n) RG-VSS (2 $\le n \le 5$ and 2 $\le k \le n$) which uses the concept of RG and stacking operation and also explains some definitions which are used in the proposed work.

In order to analyze VSS based on RG, few definitions have been borrowed from [12, 13] which are explained below (Fig. 1):

Fig. 1

Implementation results of the proposed (2, 3) case. a Binary image Text, b Share $RS_{1}$, c Share $RS_{2 }$, d Share $RS_{3}$, e $RS_{1} \otimes RS_{2}$, f $RS_{1} \otimes RS_{3}$, g $RS_{2} \otimes RS_{3}$, h $RS_{1} \otimes RS_{2} \otimes RS_{3}$

Definition 1 (Average light transmission [12, 13]) Let L(i) refer to the light transmission of a pixel ‘i’ in binary secret image SI having size $h \times w$ which is ‘1’ for transparent pixel and ‘0’ for opaque pixel. The average light transmission of SI is computed as

$$ L\left( {SI} \right) = \frac{{\mathop \sum \nolimits_{i = 1}^{i = h} \mathop \sum \nolimits_{j = 1}^{j = w} L\left( {SI\left( {i,j} \right)} \right)}}{h \times w} $$

(3)

Definition 2 (Contrast [12]) Given the original secret image SI, the superimposed image $RI$ has contrast (α) given in Eq. (4), as follows

$$ \upalpha = \frac{{ L\left( {RI\left[ {SI\left( 0 \right)} \right]} \right) - L\left( {RI\left[ {SI\left( 1 \right)} \right]} \right) }}{{1 + L\left( {RI\left[ {SI\left( 1 \right)} \right]} \right) }} $$

(4)

where $RI\left[ {SI\left( 1 \right)} \right]$ (respectively $RI\left[ {SI\left( 0 \right)} \right])$ is that portion in the recovered image RI that corresponds to all the black (respectively white) pixels of SI. Contrast is one of important metrics which evaluates the image quality of recovered image. Large contrast is desirable due to fact that recovered secret will be easily recognized by HVS if the stacked result has large α.

Definition 3 (Visually recognizable [13]) The original image SI and the recovered image RI are more similar if the contrast of recovered image is greater than 0. The condition $L\left( {RI\left[ {SI\left( 0 \right)} \right]} \right) > L\left( {RI\left[ {SI\left( 1 \right)} \right]} \right)$ implies that RI can be recognized as SI by HVS.

3.1 Shares Generation Phase and Secret Recovery Phase

Shares generation phase is shown in Fig. 2 which generates ‘n’ shares $RS_{1}$, $RS_{2} , \ldots ,\,RS_{n}$. The steps of shares generation phase of the proposed scheme are described below:

Fig. 2

Implementation results of the proposed (3, 4) case. a Binary secret image Lena, b Share $RS_{1}$, c Share $RS_{2}$, d Share $RS_{3}$, e Share $RS_{4}$, f $RS_{1} \otimes RS_{2}$, g $RS_{3} \otimes RS_{4}$, h $RS_{1} \otimes RS_{2} \otimes RS_{3}$, i $RS_{1} \otimes RS_{2} \otimes RS_{4}$, j $RS_{1} \otimes RS_{3} \otimes RS_{4}$, k $RS_{2} \otimes RS_{3} \otimes RS_{4}$, l $RS_{1} \otimes RS_{2} \otimes RS_{3} \otimes RS_{4} .$

Shares Generation Algorithm

Input: Binary secret image SI of size r × c

Output: ‘n’ shadow images $RS_{1} ,RS_{2} , \ldots ,RS_{n}$.

Repeat steps 1–3 for every secret pixel $SI\left( {m,n} \right)$,

• 1. Utilize traditional (2, 2) RG-based VSS to encrypt a secret pixel $SI\left( {m,n} \right)$ to generate two bits $b_{1}$ and $b'_{2}$. Encode $b'_{2}$ in the similar way as two bits $b_{2}$ and $b'_{3}$ are generated, similarly encode $b'_{3}$ into $b_{3}$ and $b'_{4}$. Repeat this operation until $b_{1} ,$ $b_{2}$, $b_{3} , \ldots, b_{k - 1}$, $b'_{k}$ are produced (the last bit $b'_{k}$ is same as $b_{k}$).

• 2. Generate remaining ‘n − k’ bits, i.e., $b_{k + 1} ,$ $b_{k + 2} , \ldots, b_{n}$ by assigning each of them to $b_{k}$.

• 3. Randomly arrange the ‘n’ bits $b_{1} ,$ $b_{2}$, $b_{3} , \ldots, b_{n}$ and assign the rearranged bits to shares $RS_{1} \left( {m,n} \right)$, $RS_{2} \left( {m,n} \right), \ldots , RS_{n} \left( {m,n} \right)$.

• 4. Output ‘n’ shadow images $RS_{1}$, $RS_{2} , \ldots ,RS_{n}$.

In step 1 of the above algorithm, the traditional (2, 2) RG-VSS is applied repeatedly ‘k’ times to generate ‘k’ bits. Remaining ‘n − k’ bits are obtained by equating them to kth bit which is shown in step 2. In step 3, these ‘n’ bits are randomly rearranged to show that all shares are of equal importance. In the proposed approach, we construct (k, n) RG-VSS from step 1 given in the above algorithm.

3.2 Extending Grayscale Images

The proposed algorithm encrypts grayscale images by applying halftoning like dithering, error diffusion [13, 15] which takes grayscale image and produces binary halftoned image. After that, the proposed algorithm is implemented on halftoned binary image.

3.3 Assumptions

The assumption [17] given below must be met for showing that the proposed VSS is valid construction.

Assumption: The following three conditions are fulfilled to claim the RG-based VSS as a valid construction:

• 1. Each shadow image is a random grid and does not produce any data about the secret image: ${\text{L(}}R_{t} [SI(0)]) = {\text{L}}(R_{t} [SI(1)])$ where 2 ≤ t ≤ n.

• 2. If t < k, the stacked result $R_{1 \otimes 2 \otimes 3 \ldots \otimes t} = R_{1} \otimes R_{2} \otimes \cdots \otimes R_{t}$ provides no hint about the secret: ${\text{L(}}R_{1 \otimes 2 \otimes 3 \ldots \otimes t} [SI(0)]) = {\text{L(}} R_{1 \otimes 2 \otimes 3 \ldots \otimes t} [SI(1)])$.

• 3. If t $\ge$ k, the stacked result $R_{1 \otimes 2 \otimes 3 \ldots \otimes t} = R_{1} \otimes R_{2} \otimes \cdots \otimes R_{t}$ reveals the secret image: ${\text{L}}(R_{1 \otimes 2 \otimes 3 \ldots \otimes t} [SI(0)]) > {\text{L}}( R_{1 \otimes 2 \otimes 3 \ldots \otimes t} [SI(1)])$.

The first condition ensures that the individual share is not capable of delivering any information related to secret image. The second condition claims that stacking inadequate number of shares reveals no hint about the secret information. The third condition says that only stacking sufficient number of shadow images reconstructs the secret image. These assumptions are proved by conducting experiments in the next section.

4 Experimental Results and Analyses

We have presented results for the experiments we conducted on images in this section. In the proposed (k, n) random grid-based VSS scheme, experiments are implemented for 2 $\le n \le 5$ and 2 $\le k \le n$. Several images of size 512 × 512 like binary secret image Text given in Fig. 1a, image Lena in Fig. 2a, grayscale secret image Boat given in Fig. 3a are taken as input to do experiments to analyze the performance of the proposed scheme.

Fig. 3

Implementation results of proposed (3, 3) case. a Grayscale secret image Boat, b Halftoned binary image, c Share $RS_{1}$, d Share $RS_{2}$, e Share $RS_{3}$, f $RS_{1} \otimes RS_{2}$, g $RS_{1} \otimes RS_{3}$, h $RS_{2} \otimes RS_{3}$, i $RS_{1} \otimes RS_{2} \otimes RS_{3}$

4.1 Image Illustration

In Fig. 1, experiment results carried out for (2, 3) (i.e., k = 2, n = 3) VSS scheme are given. Figure 1a shows the original binary secret image Text. Figure 1b–d shows the three shares generated. These shares individually cannot disclose anything about the secret image. Reconstructed secret is shown in Fig. 1e–g which is generated by stacking any two shares. Stacked result when all shadows are collected is presented in Fig. 1h.

In Fig. 2, experiment results conducted for (3, 4) (i.e., k = 3, n = 4) VSS scheme are given. In Fig. 2a, the secret image Lena is shown, and Fig. 2b–e shows the four shares created. Figure 2f–g shows the two of stacked results when any two shares are stacked together. Stacking when any three shares are collected is displayed in Fig. 2h–k. Figure 2l shows the stacked result when all four shares are collected.

In our experiments, results for (3, 3) (i.e., k = 3, n = 3) VSS scheme conducted on grayscale image Boat are shown in Fig. 3a. Halftoned binary image is given in Fig. 3b which is obtained by applying halftoning on the grayscale image Boat. Three shadow images which are generated are demonstrated in Fig. 3c–e. Stacked results when any two shadow images are stacked are presented in Fig. 3f–h. Figure 3i shows the stacking on all three shares.

The following observations can be made from experiments conducted for (k, n) VSS:

• Every share is noise-like random image.

• If t ≥ k, recovered secret image is visually recognizable, where ‘t’ is the number of stacking shares.

• When t < k, recovered secret gives no information about the original secret image.

• Contrast decreases when we increase the value of ‘n.’ Therefore, we assume the maximum value for ‘n’ is 5.

• The proposed scheme is also applicable for grayscale images.

4.2 Comparison with Related Schemes

This section shows the comparison of the proposed scheme with related schemes to show the advantages of proposed approach. Like [18, 15, 19, 20], the proposed RG-based VSS also benefits from no codebook designing and removes the problem of pixel expansion.

4.2.1 Contrast Comparison

Contrast in definition 2 evaluates the image quality for reconstructed secret. We have compared the proposed algorithm with scheme [20] in terms of average contrast.

Table 1 demonstrates the results of contrast of the decoded secret for the scheme [20] and the proposed scheme. The results show that:

Table 1 Average contrast of the proposed approach and [20] for binary images Text and Lena

• Contrast comes out to be greater than 0 as t increases than k. Here, ‘t’ represents the number of shares to be stacked.

• The average contrast of the proposed algorithm exceeds the average contrast given by scheme [20].

4.2.2 Features Comparison

We have compared the proposed schemes with related schemes with respect to some features. It is listed in Table 2. Benefits of the proposed RG-based VSS over related schemes are displayed in Table 2.

Table 2 Comparison of features of previous related schemes with the proposed scheme

5 Conclusion

This paper presented (k, n) random grid-based VSS which could be adopted for encryption of binary or grayscale images. The shadow images are copied onto transparencies. Secret image could be well identified by HVS when ‘k’ or more transparencies are superimposed together. One cannot get any useful data about the secret on stacking not as much as ‘k’ shares. Compared with [20], the proposed approach benefits from the greater visual quality in terms of the large contrast. The proposed scheme has advantages of no codebook designing, avoiding pixel expansion, having same importance for all shares. In the future, there may be further improvement in the visual quality of the revealed secret. This scheme could be stretched to encrypt color images. Also, meaningful shares can be generated instead of random shares. There is still scope for improvement in security of shadow images.