3.1

Basic 2 out of 2 scheme

The simplest way to understand Naor and Shamir’s n out of n VSS scheme is to consider n = 2. This basic 2 out of 2 VSS scheme with 2 subpixels is shown in Figure 1. We can consider a black and white secret image (binary) S which has total m pixels. Now, a dealer can create two binary black and white shares S₁ and S₂ by encoding every single pixel of secret image S. If the pixel of S is black, the dealer randomly chooses (flipping a coin) one of the first two rows of Figure 1. In the same manner, if the pixel p is white, the dealer randomly selects one of the last two rows of Figure 1. Notice, in the case of 2 out of 2 VSS with 2 subpixels each share created by the dealer contains twice more pixels than original image S i.e. total 2m pixels as for each pixel from the image S, associated pixels in S₁ and S₂ are two.

Figure 1:

2 out of 2 VSS with 2 subpixels

From the security perspective, the pixel selection from the dealer is randomly done and probabilities are same for both cases for shares S₁ and S₂. Hence, an attacker looking at a single share cannot able to tell if the secret pixel is black or white. Therefore, this scheme gives us perfect secrecy. At the rightmost column of the figure 1, we can see the results when two participants stack their two shares together. If original secret pixel is black, two black subpixels will appear and if original secret pixel is white, one white subpixel and one black pixel will appear. However, the human visual system will able be differentiate whether the original pixel was black or white. The reason is that the merged two black subpixels will appear black and merged black and white subpixels will appear gray due the contrast between white and black subpixels¹. In this process, the participants can decrypt the whole secret image with their eyes by stacking their shares properly. An example of 2 out of 2 VSS with 4 subpixels is shown in Figure 3.

3.2

VC Model

In this section, we explain the mathematical model behind VC. The secret image here is basically a collection of black and white pixels. Now, the secret image is divided into n shares (transparencies) i.e. each pixel appears one for each share. Furthermore, each share is divided into m subpixels (black and white). The shares can be represented by n × m Boolean matrix S = [s_ij], where

This matrix representing the shares is known as distribution matrix⁷. For example, the distribution matrix for 2 out of 2 VSS scheme with 2 sub-pixels is as follows:

Pixel expansion and contrast are two important parameters in any VC scheme. When the participants stack their shares i₁, i₂, . . ., i_r, together to reconstruct the secret image, the gray level of the combined share is directly proportional to Hamming weight w(V) of m vector V=OR(rows of shares i₁, i₂,..., i_r). Our human eye interprets this gray level with some rules of contrast and decides if the pixel is black or white. This superposition of the pixels is basically an OR operation. Some VC scheme⁶ uses XOR operation for improvement of the reconstructed image but then human visual system cannot perform the decryption anymore. More details about VC model can be found in the literatures ^{3, 7, 9}.

5.1

Realization of Visual Cryptography

First part of the experiment is a realization of visual cryptography. In this exercise, students will learn the concepts of VC technique with a practical hands-on experience. We have implemented a script which performs the basic 2 out of 2 VSS scheme in the python programming language for this exercise. Our implementation uses python image processing library (PIL) for different image processing features. The implementation of basic 2 out of 2 VSS is done with 4 subpixels. The reason for choosing 4 subpixels over 2 subpixels is to maintain the aspect ratio of the original image. As from Figure 1, we can see the pixel expansion is 2. Hence, it could create a stretching of the original image horizontally and may cause some distortion. To avoid this, we can associate each pixel of the original image to a block of (2 x 2) i.e. 4 subpixels as illustrated in Figure 2.

Figure 2:

2 out of 2 VSS with 4 subpixels

The rules of encryption and decryption process are shown in Figure 2 and the idea is same as explained in section 3.1. Each share should have 2 white sub pixels and 2 black subpixels. Therefore, we can have 4C2 i.e. 6 possible combinations. We encode with the same pattern for both shares if the original pixel is black and use opposite pattern if the original pixel is white as shown in Figure 2. The implemented code of 2 out of 2 is VSS is provided to students to perform this exercise. The students can be divided into groups where each group consists of two members. Students can choose any black and white image as an input to the algorithm. For example, of an execution of this exercise is depicted in Figure 3. A binary logo with size 128 x 128 pixels is given as an input to the algorithm. The script will output two binary image shares of size 256 x 256 pixels. Now, each student in the group receives one share and print out on a transparent paper. A student can realize his individual share indeed filled with random pixels and gives no information of the original logo. To decode the original logo, each student has to collaborate with his group mate. When both students stack their transparencies together in front of a light source, the original logo will be visible as shown in Figure 3.

Figure 3:

Example of 2 out of 2 VSS with 4 subpixels

5.2

Digital Watermarking with VC

Second part of the exercise deals with integration of VC in a digital watermarking scheme. Digital watermarking is a technique used for protecting the copyright of any digital media such as images. Watermarks are basically some digital information (Ex: logo) about the owner. Usually watermarks are embedded into images, and extracted when the owner wants to claim his copyright of the image. Currently, many of the watermarking processes are done with transfer domain techniques like discrete wavelet transform (DWT)^4,6 for better security and robustness.

There are two phases of this exercise: i) watermark embedding phase and ii) watermark extraction phase. In our implementation, we have used numpy and pywt packages of python along with PIL library. The implementation uses a VC based watermarking technique proposed by Hsu et al.⁴ and can perform watermarking without a trusted third party. During the embedding phase, a watermark logo can be split with 2 out of 2 VSS. Owner of the host image keeps one of the shares (key) and other (master share) being embedded into the host image in the frequency domain. During the extraction phase, owner can extract the master share from the watermarked image and superimpose with his ownership share to get the watermark.

An illustration of the process involved for watermark embedding with VC is shown in Figure 4. Here, imagine a student would like to embed his own binary watermark W of size 128 x 128 into a gray scale host image H of size 512 x 512. The student can split the watermark W in two shares with 2 out of 2 VSS scheme like in the previous exercise. Each share will have a size of 256 x 256. Out of two, he will use the master share for embedding purpose and ownership share for watermark extraction. On the host image H, he can execute a 2D Haar wavelet transform to convert it into the frequency domain. Then, a square T of size 256 x 256 is extracted starting from any arbitrary point of the host image in frequency domain and divided into non-intersecting blocks of 4 x 4. Now, each block of T will have 4 wavelengths coefficient and each block can be modified according to blocks of master share. After that, the modified T is integrated into the host image in the frequency domain at the specific location where it was before. Finally, the student can perform a 2D inverse Haar wavelet transform to get watermarked image. In Figure 4, we can see there is no major difference in quality between the resulted watermarked image and the host image.

Figure 4:

Watermark embedding phase

The process involved during watermark extraction phase is depicted in Figure 5. The watermarked image is again processed through 2D Haar wavelet transform to extract the modified T. Then, the master share can be reconstructed from modified T according to wavelet values of original T. Finally, a student can stack the reconstructed share and his ownership share to get the watermark and prove his ownership of the image. Comparing watermarks in Figure 5 and 4, we can observe that there is minor quality deterioration in the result of the reconstructed watermark from the original watermark.

Figure 5:

Watermark extraction phase

5.3

Biometric Authentication with VC

Final part of the experiment is the application of VC in biometric authentication. The goal of this part is that the students should realize how VC could help to protect privacy of biometric data in biometric authentication. The idea is this exercise is inspired from the approach proposed by Ross et al.⁸. A usual biometric authentication system compares feature set of raw biometric data (Ex: probe fingerprint) against feature set of biometric templates (Ex: Enrolled image) stored in a central database to verify the identity of a person. However, the privacy of the biometric data can be violated by the owner of the central database. This problem can be prevented by using VC where an enrolled biometric image can be split among different databases. Hence, the database owner can not reveal the original image with his single share.

Figure 6 presents the scheme for biometric authentication with VC exercise. There are two phases of this exercise: i) Enrollment phase, ii) Authentication phase. As the feature extraction from biometric template is quite complex and computer aided process, for simplicity, students are instructed to verify the templates with their visual system. We have downloaded some visually distinguishable fingerprint images from NIST fingerprint database¹⁴. As these images are in gray scale, we converted them into binary. To execute this exercise, we have adopted a collaborative learning approach¹². Students are divided into several groups, consisting 5 or more members in each group. In a specific group, students are allotted with different tasks. For example: one student (student A) can act as a trusted third party, two students (student B and C) are database owners and the rest of the students (student D, F . . .) want to claim their identity in the biometric system. First, we distribute different fingerprint images to the students (D, F. . .) and imagine their fingerprint image represents their identity. During the enrollment phase, D gives his image to the trusted third party (student A) to enroll in a biometric system. However, student F does not enroll to student A but still willing to get accepted by the biometric system. Now, A can apply 2 out of 2 VSS scheme to fingerprint of D and gets two shares. Thereafter, A sends share 1 to database 1 (owner B) and share 2 to database 2 (owner C) to enroll D into the system. Hence, B cannot reveal the fingerprint of D from his share 1 as he will see some random pixels and same applies to C.

Figure 6:

Scheme for Enrollment and Authentication for fingerprint image

During the authentication phase, D and F send their fingerprints (probe fingerprint) to A in order to get identified in the system. Now, A can make a request to B and C to send their shares from their database. When A receives both shares, he can stack the images together to get the target fingerprint. Finally, A visually compares the target fingerprint with the probe fingerprints from D and F. As D’s probe fingerprint matches with target fingerprint, D gets accepted in the biometric system and F fails to get accepted.