Visual Cryptography

VISUAL CRYPTOGRAPHY (a.k.a VISUAL SECRET SHARING SCHEME)

prepared by Antonius Cahya Prihandoko

Visual cryptography is another cryptographical approach to improve DRM capability. This concept provides a simple and powerful method which can accomplish privacy protection in delivering sensitive shared information. This approach can be employed to secure the distributed content.

Visual cryptography is a cryptographic technique which makes opportunity for visual information, such as pictures or text to be encrypted in such a way that the decryption can be performed by human visual system (HVS), without the aid of any computation. This concept was invented by Moni Naor and Adi Shamir in 1994 and is an extended scheme of secret sharing scheme and thus it also be known as visual secret sharing (VSS). Therefore, before advance discussing on visual cryptography, we briefly describe the concept of secret sharing scheme.

Secret Sharing Schemes

Secret sharing refers to mechanism for distributing a secret amongst a group of participants which each of them is given a particular share of the secret. The secret is firstly encrypted into a number of shares, which are then independently distributed to all participants in the group. The secret can be reconstructed only when a sufficient number of shares are combined together.

Formally, in a secret sharing scheme there is one dealer and n players or participants. The dealer has a secret, splits the secret into n shares and gives the shares to all participants. Each participant receives one particular share. Any group of t participants or more can together reconstruct the secret but no group of fewer than t players can do so. Such a system is called a (t,n)-threshold scheme. The formal definition of the scheme can be described as follow.

Definition 1. Let t, n be  positive integers, $t leq n$. A (t,n)-threshold scheme is a method of sharing a key K among a set of n participants (denoted by P), in such a way that any t participants can compute the value K, but no group of t-1 participants can do so.

In the Shamir (t,n)-threshold scheme in $\mathbb{Z}_{p}$, initially the dealer D chooses n distinct non-zero elements of $\mathbb{Z}_{p}={0,1,2,3,...,p-1}$, denoted $x_{i}$, where $1 \leq i \leq n$. This scheme requires that $p \geq n+1$. D then gives the value $x_{i}$ to the participant $P_{i}$, for $1 \leq i \leq n$. The values $x_{i}$ are public. When D wants to share a secret key $K in \mathbb{Z}_{p}$, D secretly chooses, independently at random, t-1 elements of $\mathbb{Z}_{p}$, denoted $a_{1},a_{2},...,a_{t-1}$. D then computes $y_{i}=a(x_{i})$, where $1 \leq i \leq n$ and

$a(x)=K+\sum_{j=1}^{t-1}a_{j}x^{j} \bmod p$

D finally gives the shares $y_{i}$ to participant $P_{i}$, for $1 \leq i \leq n$. Thus, each participant $P_{i}$ receives a pairs of $(x_{i},y_{i}$ .

In order to be able to reconstruct the secret, K, it requires that all possible $x_{i}$, i.e all non-zero elements of $\mathbb{Z}_{p}$, have each multiplication inverse in $\mathbb{Z}_{p}$. Thus, $\mathbb{Z}_{p}$ must be a field, i.e p has to be a prime number.

Example 1 :

Let the dealer D works on (3,7)-threshold scheme in $\mathbb{Z}_{23}$. Initially, D chooses 7 distinct non-zero elements of $\mathbb{Z}_{23}$, say 6, 3, 8, 11, 5, 2, 4, and denotes them $x_{1},x_{2},...,x_{7}$, respectively. Let he has the secret value K = 9, and wants to share the secret to 7 participants, then he has to secretly choose 2 random elements of $\mathbb{Z}_{23}$. Let the chosen secret random values are 5 and 3, and be denoted $a_{1}$ and $a_{2}$, respectively. With these values, D then computes $y_{i}=a(x_{i})$, for $1 \leq i \leq n$ and

$a(x) = 9 + 5x + 3x^{2}$

This computation will give the shares $(x_{i},y_{i})$ for 7 participants $P_{i}$ as follows.

$P_{1}$       $P_{2}$       $P_{3}$       $P_{4}$       $P_{5}$       $P_{6}$       $P_{7}$
x       6        3        8        11        5        2        4
y       9        5        11       13        17      8        8

In the secret reconstruction, any group of 3 participants can reveal the secret K. Suppose that participants $P_{2}$, $P_{6}$, and $P_{7}$ pool their shares, which are (3,5), (2,8), and (4,8), respectively. Writing the polynomial y=a(x) as

$a(x)=a_{0}+a_{1}x+a_{2}x^{2},$

and computing a(3), a(2), and a(4), the following three linear equations in $\mathbb{Z}_{23}$ are obtained:

$a_{0}+3a_{1}+9a_{2} = 5$
$a_{0}+2a_{1}+4a_{2} = 8$
$a_{0}+4a_{1}+16_{2} = 8$

This system has a unique solution in $\mathbb{Z}_{23}$, i.e $a_{0}=9$, $a_{1}=5$, and $a_{2}=3$. The secret is therefore $K=a_{0}=9$.

Another approach to compute the secret K from an adequate number of shares is by meant the Lagrange interpolation as the following equation.

$K=\sum_{j=1}^{t} y_{i_{j}} \prod_{1 \leq k \leq t, k \neq j}\frac{x_{i_{k}}}{x_{i_{k}}-x_{i_{j}}}$

Suppose we define

$b_{j}=\prod_{1 \leq k \leq t, k \neq j} \frac{x_{i_{k}}}{x_{i_{k}}-x_{i_{j}}}$

for $1 \leq j \leq t$.

Then we have

$K=\sum_{j=1}^{t} b_{j}y_{i_{j}}$

Hence, the key K is a linear combination of the t shares. To illustrate this approach, let recompute K from previous example.

Example 2:

The participants ${P_{2},P_{6},P_{7}}$ can compute $b_{1}$, $b_{2}$, and $b_{3}$ according formula given above.

$b_{1} = \frac{x_{6}.x_{7}}{(x_{6}-x_{2})(x_{7}-x_{2})} \bmod 23 = 2 \times 4 \times (-1)^{-1} \times 1^{-1} \bmod 23 = 15$

$b_{2} = \frac{x_{2}.x_{7}}{(x_{2}-x_{6})(x_{7}-x_{6})} \bmod 23 = 3 \times 4 \times 1^{-1} \times 2^{-1} \bmod 23 = 6$
$b_{3} = \frac{x_{2}.x_{6}}{(x_{2}-x_{7})(x_{6}-x_{7})} \bmod 23 = 3 \times 2 \times (-1)^{-1} \times (-2)^{-1} \bmod 23 = 3$

Then given shares $y_{2}=5$, $y_{6}=8$, $y_{7}=8$, they would obtain

$K=15 \times 5 + 6 \times 8 + 3 \times 8 \bmod 23 = 9,$

as before.

In the case when n=t, the protocol of (t,t)-threshold scheme in $\mathbb{Z}_{m}$ is as follows. Suppose the dealer D wants to share the secret, K, to t participants. Initially, D, secretly and independently determine at random t-1 elements of $\mathbb{Z}_{m}$, denoted $y_{1}, y_{2}, ..., y_{n-1}$. D then computes the $t^{th}$ y using the equation:

$y_{t}=K-\sum_{i=1}^{t-1} y_{i} \bmod m$

and finally gives the share $y_{i}$ to participant $P_{i}$, for $1 \leq i \leq t$.

In order to reveal the secret, K, all those t participants have to combine their shares together and reconstruct the secret K using the formula:

$K=\sum_{i=1}^{t} y_{i} \bmod m$

It is clear that any group of t-1 participants or less can not reconstruct K as they receive t-1 independent random numbers as their shares. Those t-1 participants may sum their shares, i.e

$y_{1}+y_{2}+y_{3}+...+y_{t-1}$

and yield

$K-y_{t}$

However, they have no information about the random value $y_{t}$, and hence, unsuccessfully reveal the secret, K.

Unlike (t,n)-threshold scheme, this (t,t)-threshold scheme do not require m to be a prime number as all elements of $\mathbb{Z}_{m}$ have each addition inverse that are necessary for reconstructing K. Let us consider the following example to simulate this protocol.

Example 3:

Let the dealer, D, uses (8,8)-threshold scheme in $\mathbb{Z}_{16}$ to share his secret, K,  say 5. Suppose the 7 independent random numbers secretly determined by D are 1, 6, 3, 12, 5, 8, 3, then the $8^{th}$ share will be

$y_{8}=K-\sum_{i=1}^{7} y_{i} \bmod 16 = 5-1-6-3-12-5-8-3 \bmod 16 = 15.$

D then distributes the shares 1, 6, 3, 12, 5, 8, 3, 15 to 8 participants.

To reveal the secret, all 8 participants have to present their shares and sum them together, yielding

$1+6+3+12+5+8+3+15 \bmod 16 = 5$,  i.e the secret, K.

Shamir’s Visual Sharing Scheme

Unlike a regular secret sharing scheme, that the secret reconstruction typically involves computation in a finite field, in a visual sharing scheme the secret can be reveal visually without any computations. Figure 1 illustrates this concept. The original gray scale image {em cameraman} is encrypted into two shares which are appeared as random images. The information of the original image can only be revealed by combining these two shares. In the printing application, each share can be printed on a separate transparency. The decryption step is performed by superimposing those share transparencies, and the original image or its approach would be appear.

Fig. 1 Example of visual cryptography (2,2)

The illustration depicted in figure 1  is an implementation of (2,2)-visual threshold scheme (VTS). In this scheme, a secret image is encrypted into two shares: each of them appears as a black and white random image. In order to reveal the secret image, those two shares have to be combined together. In this case, the secret is also a black and white image and the encryption scheme is visualized in figure 2. For each pixel of the secret image, if the pixel is white then the first two rows are randomly chosen to encode the pixel, and if the pixel is black then the last two rows are the choice for encoding.

Fig. 2 Example of splitting pixel in the (2,2) – threshold scheme

In the printing application, however, the reconstructed image is not as exactly same as the original secret one due to the human visual system. The human visual system performs a boolean “OR”, while the expected operation in order to reveal the secret image is “XOR”. Suppose black is associated with 1 and white with 0. All superimposing are agree with boolean operation “XOR” and “OR” except superimposing black and black that will yield black instead of white, thus it is agree with “OR” but not “XOR”. Therefore, the decrypted image is an approach of the original one.

In general implementation, that is (t,n)-VTS, the secret image is encrypted into n shares and in the decryption process, at least t shares have to be combined together in order to reveal the secret, while t-1 or fewer shares will have no information about the secret.

Stinson’s Model of Visual Cryptography

Stinson (1996) have improved Shamir’s scheme, in the term of qualified sets: the sets of participants that can recover the secret image. Unlike in Shamir’s (t,n)-VTS, that any group of t or more participants can recover the secret image, in Stinson’s model the qualified groups are restricted. For example, let $\mathcal{P}=\{1,2,3\}$ is the set of participants and let that qualified sets are all subset of $\mathcal{P}$ containing at least one of two sets $\{1,2\}$ and  $\{2,3\}$. Then the family of qualified sets is

$\Gamma_{Qual}=\{\{1,2\},\{2,3\},\{1,2,3\}\},$

while the remaining subsets of $\mathcal{P}$ are forbidden.

Originally, share images in Stinson’s model, $(\Gamma_{Qual},\Gamma_{Forb})$, look like random patterns, as those in Shamir’s scheme. However, in the extended visual cryptography scheme, $(\Gamma_{Qual},\Gamma_{Forb},m)$-EVCS, Stinson et al developed a technique to encode the secret image into n innocent looking images in such a way that any set, $X \in \Gamma_{Qual}$, can reveal the secret, while any set, $X \in \Gamma_{Forb}$, can recover nothing.

Townsville, 27 February 2013