Visual cryptography

In this scheme, the image is divided into n parts so that someone with k parts can decrypt it, and any k-1 parts do not give any information about the original image. When all k parts are superimposed, the original image becomes available.

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 ^[1] .

In order to split the original black and white image into n parts, it is necessary to represent each pixel in the image as a number of smaller parts. The number of white and black parts is always the same. If the pixel is divided into 4 parts, then 2 white and 2 black blocks are obtained. If it is 2, then one is white and one is black. ^[7]

In this example, the image was divided into 2 components. Each of them has a pair of pixels for each pixel in the original image. These pixel pairs are shaded in black or white according to the following rule: if the pixel in the original image is black, the pixel pairs must complement each other. One ■ □ and another □ ■ are randomly selected. When these complementary pairs overlap, they turn dark gray. On the other hand, if the pixel in the original image was white, its pairs should be the same. Both ■ □ or both □ ■. When applied, it will turn light gray.

Therefore, when the two image components overlap, the original image appears. However, individually considered components do not show any information about the original image; it is indistinguishable from a random set of pairs of the form ■ □ / □ ■. In addition, if there is one component of the image, you can use the rules above to create a fake of the second part of the image, which in combination with the first can give any image at all.

This is a case of sharing a secret by an arbitrary number of people N so that at least 2 of them are needed to decode the secret. This scheme was presented to the public by Moni Naor and Adi Shamir in 1994. In this scheme, there is a secret image that is encoded in N parts printed on a transparent film. The parts are arbitrary and do not contain information about the decryption of secret information, however, if any 2 parts are superimposed on each other, the secret image becomes decrypted for the human eye.

Each pixel from the secret image is encoded into several subpixels in each part of the image using a matrix that determines the color of the pixel. In the (2, N) case, the white pixel in the secret image is encoded using the matrix from the following set, in which each row gives a subpixel pattern for one of the components:

all column permutations:

While the black pixel in the secret image is encoded using the following matrix:

all column permutations:

For example, in the (2, 2) case (the secret is divided into 2 parts and both parts are necessary for decoding the secret), an additional matrix for black pixels and an identical matrix for white pixels are used. Having done operations with all pixels, we get all subpixels. Linked to black pixels are now associated with black, while 50% of the sub-pixels associated with white remain white.

Horng et al. Proposed a method that allows N-1 conspiring parties to deceive an honest party ^[8] . They win by knowing the underlying law of the distribution of pixels in parts in order to create new parts that are combined with existing ones to create a new secret message of the choice of deceivers.

We know that two parts are enough to decrypt a secret message using human vision. But the considered 2 parts also give information about the third part. For example, conspiring participants can look at their parts to determine in which cases they both have black pixels, and use this information to determine that the other participant will also have a black pixel in this place. Knowing where the black pixel is in other parts, they can create a new part, which will be created on the basis of previously obtained assumptions, and will give a new secret message. In this case, a set of parts of conspiring people is enough to create a secret code-deception of other honest participants.

There is a simple algorithm for binary (black and white) visual cryptography, which creates 2 encrypted images from the original. The algorithm is as follows: first, an image is formed from random pixels of the same size and type as in the original image. Then a second image of the same size and type as the first is created, but where the pixels of the original image, the same as in the corresponding first encrypted one, change color to the opposite, and the pixel, which in the first encrypted message does not match the original, becomes the corresponding pixel of the first encrypted one second encrypted image. Two random images can now be combined using exclusive or (XOR) to restore the original image.

The following is Python code that implements an algorithm that creates two “shadow” images that are superimposed using an “exclusive or” (XOR).

Initial image

In [1]:

  import random

  import numpy as np

  from PIL import Image, ImageDraw

  import matplotlib.pyplot as plt

  import matplotlib

  import matplotlib.cm as cm

  % matplotlib inline

  dpi = 150

  matplotlib.rc ("savefig", dpi = dpi)

In [2]:

  def show_image (img, plot = True):

  plt.imshow (img, cmap = cm.Greys_r)

  if plot:

  plt.show ()

In [3]:

  image = Image.open ("image.jpg")

  img = np.asarray (image)

  show_image (img)

  image.save ("1.jpg", "JPEG")

Binary

In [4]:

  def rgb2gray (rgb):

  r, g, b = rgb [:,:, 0], rgb [:,:, 1], rgb [:,:, 2]

  gray = 0.2989 * r + 0.5870 * g + 0.1140 * b

  return gray

In [5]:

  img_grey = rgb2gray (img)

  print (img_grey.shape)

  show_image (img_grey)

(448, 640)

In [6]:

  t = 64 # 0 <= t <= 256

  img_b = np.copy (img_grey)

  img_b [img_grey> t] = 255

  img_b [img_grey <= t] = 0

  show_image (img_b)

2 shadow images

In [7]:

  patterns = np.array ([

  [[1, 0], [1, 0]],

  [[0, 0], [1, 1]],

  [[1, 0], [0, 1]],

  [[0, 1], [1, 0]],

  [[1, 1], [0, 0]],

  [[0, 1], [0, 1]]]). Astype (np.bool)

  #patterns

In [8]:

  def concat (img):

  return np.vstack ([np.hstack (line) for line in img])

In [9]:

  rand_mask = np.random.randint (0, 6, size = img_b.shape)

  images = []

  images.append (patterns [rand_mask])

  images.append (patterns [rand_mask])

  image_mask = img_b.astype (np.bool)

  images [1] [image_mask] = patterns [5 - rand_mask] [image_mask]

In [10]:

  images = list (map (concat, images))

In [11]:

  show_image (images [0])

In [12]:

  show_image (images [1])

Sum 2 shadow images

In [13]:

  show_image ((images [0] ^ images [1]) [:: 2, :: 2])