Secret Visual Information Sharing Scheme

    Good day, Habrausers!

    Visual cryptography [1] was first introduced by Moni Naor and Adi Shamir in 1994 [3]. It is used to encrypt an image or text represented as an image. The main idea of ​​the visual cryptography model is to split the original image into several encrypted (“shadow” images, shadow images), each of which does not give any information about the original image except, perhaps, its size (the image is a la “white noise” ) When encrypted images are superimposed on each other, you can get the original image. Thus, decoding does not require special knowledge, high-performance computing, or even a computer (in case you print shadow images on transparent films). In the case of using this algorithm in computer systems, You can superimpose all parts of the image on each other using the logical operations AND, OR, XOR (or by setting a higher degree of transparency in the graphics editor). This technology has cryptographic stability due to the fact that when dividing the original image into many cipher images, it happens randomly.


    Figure 1. Possible pixel states in the (2, 2) -visual scheme of secret exchange.

    An application of such technologies is copy protection and authentication (copyright, watermarking ), tracking electronic forms during remote voting, encryption of financial documents, management of access keys and sharing use of passwords.

    Visual cryptography algorithm

    Naor and Shamir demonstrated a ( k, n ) -visual scheme of secret exchange, where the image was divided into n parts, so that anyone with any k parts could decrypt it, while any k-1 parts did not give no information about the content of the original image. When all k parts are superimposed on each other, we will see the original image [3].

    In order to split the original black and white image into n parts, each image pixel is represented as a number of smaller parts ( subpixels) The number of white and black parts is always the same. If the pixel is divided into two parts, it turns out one white and one black block. If the pixel is divided into four equal parts, then we get two white and two black blocks.

    Consider the (2, 2) -visual scheme of secret exchange, i.e. the original image is divided into two shadow images, each of which is an image of white noise, but when superimposed, they give the original image. Each pixel of the original image will be divided into four parts, so if the size of the original image was M × N , then the size of the shadow images would be 2M × 2N .

    Figure 1 shows that a pixel divided into four parts can have six different states.

    If the pixel on the first layer has one position, the pixel on the second layer, in turn, can have two positions: identical or inverted to the pixel of the first layer. If the pixel of part 2 is identical to the pixel of part 1, then the pixel obtained by superimposing both shadow images will be half white and half black. Such a pixel is called gray or empty. If the pixels of part 1 and part 2 are opposite, then the pixel resulting from the overlay will be completely black. It will be informational.

    Let us describe the process of obtaining shadow images for the original image for the scheme (2, 2): for each pixel of the original image, for the first shadow image randomlyone of the six possible pixel states shown in Figure 1 is selected. The pixel state of the second shadow image is selected identical or symmetrical to the pixel state of the first “shadow”, depending on whether it was white or black in the original image, respectively. In a similar way, one can construct any ( k, n ) visual scheme of secret exchange [3].

    Theoretically, this algorithm can be effectively used for secure messaging over the network if the set of possible messages is not very large (for example, many different alarms). Implement such an exchange as follows.

    Suppose that on the side of the message source there are only all the first shadow images from the pair (images 1), and on the side of the message receiver there are only all second images from the pair of shadow images (images 2). Each shadow image is completely random and, if it falls into the hands of an attacker individually (without a second image from a pair), does not provide any information. Upon receipt of one of the shadow images 1, the receiver sequentially superimposes it on images from its set and finds the first semantically loaded image message (a specific alarm signal coming from the message source).

    Matlab implementation of the algorithm

    Matlab-function that performs the separation of the source binary image into two shadow “forehead”, using 4 (out of 6 possible, see Fig. 6) pixel states will have the following form:
    function [S1,S2] =getShdwImg(Img)
    % получение теневых изображений S1 и S2 из исходного бинарного изображения (Img)
    % 
    % получаем размер исходного изображения
    [m,n] = size(Img);
    % запасаемся памятью для каждого теневого изображения :)
    S1= zeros(2*m,2*n);
    S2= zeros(2*m,2*n);
    % для каждого пикселя исходного изображения - действуем согласно Рис. 1
    % Примечание:
    for i=1:m-1
        for j=1:n-1
            r = randi(4);
            if(Img(i,j)==1)
                switch r
                case 1,
                    S1(2*i,2*j)=1;
                    S1(2*i+1,2*j)=1;
                    S1(2*i,2*j+1)=0;
                    S1(2*i+1,2*j+1)=0;
                    S2(2*i,2*j)=1;
                    S2(2*i+1,2*j)=1;
                    S2(2*i,2*j+1)=0;
                    S2(2*i+1,2*j+1)=0;
                case 2,
                    S1(2*i,2*j)=0;
                    S1(2*i+1,2*j)=0;
                    S1(2*i,2*j+1)=1;
                    S1(2*i+1,2*j+1)=1;
                    S2(2*i,2*j)=0;
                    S2(2*i+1,2*j)=0;
                    S2(2*i,2*j+1)=1;
                    S2(2*i+1,2*j+1)=1;
                case 3,
                    S1(2*i,2*j)=0;
                    S1(2*i+1,2*j)=1;
                    S1(2*i,2*j+1)=1;
                    S1(2*i+1,2*j+1)=0;
                    S2(2*i,2*j)=0;
                    S2(2*i+1,2*j)=1;
                    S2(2*i,2*j+1)=1;
                    S2(2*i+1,2*j+1)=0;
                case 4,
                    S1(2*i,2*j)=1;
                    S1(2*i+1,2*j)=0;
                    S1(2*i,2*j+1)=0;
                    S1(2*i+1,2*j+1)=1;
                    S2(2*i,2*j)=1;
                    S2(2*i+1,2*j)=0;
                    S2(2*i,2*j+1)=0;
                    S2(2*i+1,2*j+1)=1;
                end
            else
                switch r
                case 1,
                    S1(2*i,2*j)=1;
                    S1(2*i+1,2*j)=1;
                    S1(2*i,2*j+1)=0;
                    S1(2*i+1,2*j+1)=0;
                    S2(2*i,2*j)=0;
                    S2(2*i+1,2*j)=0;
                    S2(2*i,2*j+1)=1;
                    S2(2*i+1,2*j+1)=1;
                case 2,
                    S1(2*i,2*j)=0;
                    S1(2*i+1,2*j)=0;
                    S1(2*i,2*j+1)=1;
                    S1(2*i+1,2*j+1)=1;
                    S2(2*i,2*j)=1;
                    S2(2*i+1,2*j)=1;
                    S2(2*i,2*j+1)=0;
                    S2(2*i+1,2*j+1)=0;
                case 3,
                    S1(2*i,2*j)=0;
                    S1(2*i+1,2*j)=1;
                    S1(2*i,2*j+1)=1;
                    S1(2*i+1,2*j+1)=0;
                    S2(2*i,2*j)=1;
                    S2(2*i+1,2*j)=0;
                    S2(2*i,2*j+1)=0;
                    S2(2*i+1,2*j+1)=1;
                case 4,
                    S1(2*i,2*j)=1;
                    S1(2*i+1,2*j)=0;
                    S1(2*i,2*j+1)=0;
                    S1(2*i+1,2*j+1)=1;
                    S2(2*i,2*j)=0;
                    S2(2*i+1,2*j)=1;
                    S2(2*i,2*j+1)=1;
                    S2(2*i+1,2*j+1)=0;
                end
            end
        end
    end
    

    The function getShdwImgsplits the original image as shown in Fig. 1, with the only difference being that in the Matlab binary images, the black pixels of the image are equal to zero, and the white ones, respectively, are equal to one.
    Below is the Matlab script code that demonstrates the operation of the algorithm for sharing classified visual information.

    close all
    % считываем исходное RGB-изображение и преобразуем его в бинарное
    biImg = imread('nordavind_logo.jpg'); 
    biImg = rgb2gray(biImg);
    level = graythresh(biImg);      % пороговая фильтрация по Отсу (Otsu)
    biImg = im2bw(biImg,level);
    % выводим результат на экран
    figure(1)
    imshow(biImg);
    title(['Original binary image']);
    % получаем два теневых изображения
    [S1,S2] =getShdwImg(biImg);
    % выводим их на экран
    figure(2)
    imshow(S1);
    title(['Shadow image S1']);
    % 
    figure(3)
    imshow(S2);
    title(['Shadow image S2']);
    % выводим на экран результат их наложения друг на друга 
    % различными способами
    figure(4)
    % imshow(or(S1, S2));
    % imshow(and(S1,S2));
    imshow(~xor(S1, S2));      % операция “~”(NOT) используется, чтобы получить черный текст на белом фоне, а не наоборот
    title(['Superimposed image']);
    

    results

    Below are the results of the operation of encoding and decoding the original "secret" image. Various combining operations obtained from the original shadow images are considered: using XOR (Fig. 6), AND (Fig. 7) and OR (Fig. 8).


    Figure 2. Original image


    Figure 3. After converting the image to b / w


    Figure 4. Shadow image 1


    Figure 5. Shadow image 2


    Figure 6. Result for NOT (XOR (S1, S2))


    Figure 7. Result for AND (S1, S2)


    Figure 8. Result for OR (S1, S2)

    Conclusion

    The ( k, n ) -visual scheme for sharing classified information is cryptographic until k parts of the image fall into the hands of the attacker. If less than k parts are intercepted , then decryption of the original image is impossible.
    If in the process of using this system a random approach to breaking pixels into blocks is fully respected, visual cryptography offers absolute reliability and secrecy.
    The classic algorithm for visual cryptography was considered here. Today, there are many improved models of this algorithm, for example, for encoding color images [4, 6], or schemes where, instead of shadow images in the form of white noise, semantically significant images are used [5], as well as visual cryptography schemes based on steganography technician [2, 7].

    References

    1. en.wikipedia.org/wiki/Visual_cryptography
    2. ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%B3%D0%B0%D0%BD%D0%BE% D0% B3% D1% 80% D0% B0% D1% 84% D0% B8% D1% 8F
    3. M. Naor and A. Shamir. Visual cryptography In EUROCRYPT'94. - Springer-Verlag Berlin, 1995.
    4. D. Jin, WQ Yan, and MS Kankanhalli. Progressive color visual cryptography. In Journal Of Electronic Imaging, 2005.— Vol. 14, Issue 3.
    5. Feng Liu and ChuanKun Wu. Embedded extended visual cryptography schemes. - China, 2006.
    6. YC Hou. Visual cryptography for color images. In Pattern Recognition, 2003.
    7. Ritesh Murherjee, Nabin Ghoshal. Steganography based visual cryptography. - Berlin: Springer-Verlag, 2013.

    Also popular now: