# Image Secret Sharing - A (k,n)-threshold scheme, Basis matrices in visual cryptography

### shares binary bit iss

*Rastislav Lukac and Konstantinos N. Plataniotis
University of Toronto, Toronto, Canada*

**Ching-Nung Yang
National Dong Hwa University, Shou-Feng, Taiwan, ROC**

**Definition:** Among numerous cryptographic solutions proposed in the past few years, secret sharing schemes have been found sufficiently secure to facilitate distributed trust and shared control in various communication applications

Digital rights management systems are used to protect intellectual property rights of digital media itself or secure its transmission over untrusted communication channels. The required protection is achieved by employing either cryptography or steganography. Steganography hides the secret message inside a cover signal producing its stego-version with an imperceivable difference from the original cover, whereas cryptography alters the meaningless of the secret message through its encryption necessitating the use of a decryption key to recover the original content.

Among numerous cryptographic solutions proposed in the past few years, secret sharing schemes have been found sufficiently secure to facilitate distributed trust and shared control in various communication applications, such as key management, conditional access, message authentication, and content encryption. Due to the proliferation of imaging-enabled consumer electronic devices and the extensive use of digital imaging in networked solutions and services, secret sharing concepts have been used to secure transmission and distribution of personal digital photographs and digital document images over public networks.

## A (k,n)-threshold scheme

Most of the existing secret sharing schemes are generalized within the so-called ( *k* , *n* ) -threshold framework where *k* = *n* . The framework confidentially divides the content of a secret message into *n* shares in the way which requires the presence of at least *k* shares for the secret message reconstruction. If *k* = *n* , then all the shares are required in the ( *n* , *n* ) -threshold scheme to recover the secret. However, the lost of any of the shares produced using the ( *n* , *n* ) -threshold scheme results in inaccessible secret messages.

Therefore, apart from the simplest (2,2)-schemes commonly used as a private key cryptosystem solution, general ( *k* , *n* ) -threshold schemes with *k* < *n* are often the object of interest due to offer their ability to recover the secret message even if several shares are lost. In this case, any of [ *n* !/( *k* !( *n* – *k* )!)] possible combinations of *k* shares can be used to recover the secret message. Since protection against cryptoanalytic attacks, including brute force enumeration, should remain unchanged regardless of how many shares are available until the threshold *k* is reached, the use of *k* – 1 shares should not reveal additional information compared to that obtained by a single share.

## Basis matrices in visual cryptography

Probably the most well-known ( *k* , *n* ) -secret sharing schemes for encryption of visual data are those based on visual cryptography (VC). Among the numerous VC-based schemes (Figures 1 and 2), such as the ( *k* , *n* ), ( *k* , *n* , *c* ) and extended VC schemes, the so-called ( *k* , *n* ) -VC framework is the most widely used. The traditional VC schemes (Figure 1) produce meaningless, noise-like, shares as opposed to the meaningful shares obtained using complex, extended VC schemes (Figure 2). Furthermore, compared to ( *k* , *n* , *c* )-VC schemes constructed using *c* colors, the ( *k* , *n* ) – VC framework uses frosted/transparent (or binary) representation of the shares keeping the simplicity of the approach at the level suitable for practical implementation. It should be noted that within the ( *k* , *n* )-VC framework, the special cases of (2,2), (2, *n* ), and ( *n* , *n* ) -VC schemes can be obtained.

Operating on a *K* 1 × *K* 2 binary or binarized secret image, a ( *k* , *n* ) -VC scheme encrypts, via an encryption function, each binary pixel into a *m* 1 × *m* 2 block of binary pixels in each of the *n* binary shares. The spatial arrangement of bits in the produced blocks varies depending on the value of secret pixel to be encrypted and the (random) choice of the matrix from the so-called matrices’ generation set *C* 0 or *C* 1 . The sets *C* 0 and *C* 1 include all matrices obtained by permuting the columns of the *n* × *m* 1 *m* 2 basis binary matrices *A* 0 and *A* 1 , respectively [ 2 ]. Examples of the basis matrices are listed here for the most widely used ( *k* , *n* ) -VC schemes:

The value *m* 1 *m* 2 is the so-called expansion factor and therefore, the basis matrices are constructed in the way to minimize the expansion factor as much as possible. By repeating the encryption operations at each spatial location of the secret image, a *K* 1 × *K* 2 secret image is encrypted into *n* binary shares with dimensions of *m* 1 *K* 1 × *m* 2 *K* 2 pixels.

VC-based decryption, which has to be performed over the set of ? = *n* shares, can be modeled through a decryption function similar to the one proposed in . Following the formulation of a { *k* , *n* } -threshold schemes, the secret image is revealed only if ? = *k* . Due to the utilization of the transparent/frosted concept: i) the VC decryption process recovers the decrypted pixel as black if any of the share pixels at the same spatial location of the shares stacked for decryption is black, or recover it as white if all the pixels at the same spatial location in the stacked shares are transparent, and ii) do not recover the original secret image.

## ISS with perfect reconstruction of the secret image

To recover the original secret image and prevent the introduction of visual impairments, a different decryption strategy should be used. Following the approach introduced in , the decryption function should observe the contrast properties of the share blocks when stacked together. Similarly to VC decryption, the difference between the encrypted ‘black’ and ‘white’ binary values reveals only if ? = *k* . In this case, the decryption process recovers the corresponding original binary pixel. By decrypting the binary share blocks over the image domain the procedure recovers the original binary secret image, as it is shown in Figure 3. This suggests that such an approach can be used to construct an Page 331 image encryption scheme which satisfies the essential perfect reconstruction property.

Built on the framework presented in a number of solutions with different design characteristics and performance can be obtained. For example, instead of the utilization of a halftoning module in processing a *K* 1 × *K* 2 continuous-tone image as it is suggested by traditional VC, the encryption operations can be performed (Figure 4a) at the decomposed bit-levels of the secret image with *B* -bits per pixel representation. Each of *B* bit-levels represents a *K* 1 × *K* 2 binary image which is commonly required in the input of the VC encryption procedure. By repeating the VC-based encryption operation at each bit-level, the generated share bits are used to obtain the *B* -bit share pixel and thus, the bit-level processing based encryption process splits the *B* -bit secret image into *n,* seemingly random, *m* 1 *K* 1 × *m* 2 *K* 2 shares. Each of the constructed shares has *B* -bit representation identical to the bit-level representation of the secret image (Figure 5).

The decryption process (Figure 4b) decomposes the bit levels of all *B* -bit shares which are available for decryption. If *?* = *k* , then the procedure recovers the individual bit levels which are then used by to re-construct the original, continuous tone secret image. Thus, the decryption process recovers the original secret image (Figure 5) in a digital form making the framework ideal for modern, digital, multimedia systems.

The ISS framework allows for the design of both input-agnostic and input-specific solutions. Such solutions: i) differ in their design characteristics and complexity, ii) may introduce different protection levels during the encryption process, and iii) can be used to process the secret image using an arbitrary { *k,n* } configuration and expansion factor *m* 1 *m* 2 .

## Input-agnostic ISS solutions

The input-agnostic (IA) ISS solution follows the representation of the input and process sequentially all bit-levels decomposed from the secret image. As it is shown in Figure 6, the IA-ISS solution encrypts: i) the binary secret image into the binary shares, ii) the gray-scale secret image into the gray-scale shares, or iii) the color secret image into the color shares. As the result, the IA-ISS solution always produces shares with the image (bit) representation identical to that of the secret image, and decrypts the original secret image with perfect reconstruction.

## Input-specific ISS solutions

The input specific (IS)-ISS solution encrypts the secret image arranged in the specific image format. For example, IS-ISS solution can require to convert: i) the binary or grayscale input image into the color image when the solution is color image specific to produce color shares, ii) the binary or color input image into the gray-scale image when the solution is gray-scale image specific to produce gray-scale shares, and iii) the color or gray-scale input image into the binary image when the solution is binary image specific to produce binary shares. Thus, any IS-ISS solution can be used to process the image with less rich or richer bit-representation than that of the required in the IS input. The approach requires format conversion such as the replication of the input (Figure 7a) or reduction of image representation (Figure 7b) in order to meet the requirements for the input, ii) the procedure requires to transmit *Q* times more (Figure 7a) or less (Figure 7b) share information compared to the share information produced by the IA-ISS solution, and iii) inverse format conversion is necessary to recover the original (Figure 7a) or due to the loss in input format conversion approximated (Figure 7b) secret image.

## Security characteristics of the ISS framework

The randomness of the encryption processes in the ISS framework is fortified by the depth of the *B* -bit representation of the secret image makes the original pixel and the share pixels significantly different. The variety in the share pixels, which can be viewed as the degree of protection, increases with the value of *B* which denotes the number of bits used to represent the image pixel (Figure 8). Assuming that *N* denotes the number of unique matrices either in *C* 0 or *C* 1 , the *B* -bit pixel is encrypted using one of *N B* unique *m* 1 × *m* 2 share blocks of *B* -bit pixels instead of one of only *N* unique share blocks of binary pixels used in the traditional and halftoning based VC schemes. In this way, the IS-ISS solution in Figure 7a increases the protection by generating ‘richer’ noise compared to the shares obtained using the IA-ISS solution. Similarly, by reducing the image representation, the IS-ISS solution in Figure 7b reduces protection of the secret image compared to the case when the IA-ISS solution is used. Depending on the application, security requirements, available computational resources, and nature of the secret image, the end-user may select the particular cryptographic solution designed within the proposed framework to process the input (secret) image.

## User Comments