Visual Cryptography and Random Grids - Visual Cryptography and Secret Image Sharing - page 193

we first find a random grid R 1 with T (R 1 ) = 1=2. Then, we dene R k for

2 6 k 6 n as follows:

r k = f r 1

if b = 0;

(7.9)

random pixel() otherwise,

for each pixel r k 2 R k where r 1 ;r 2 ;:::;r n are corresponding pixels of b 2 B.
It is easy to see that all R k 's are random grids and when b = 0, t(r i r j ) =
t (r 1 r 1 ) = t (r 1 ) = 1=2; while b = 1, t (r i r j ) = 1=4 by Lemma 1 for
each pair of i and j where 1 6 i 6= j 6 n. That is, T (R i [B(0)]R j [B(0)]) =

1=2 > 1=4 = (R i [B(1)]R j [B(1)]). As a result, fR 1 ;R 2 ;:::;R n g produced

in this way is a set of two out of n visual cryptograms of random grids. Yet,
it is not a set of (n;n)-VCRG, since Condition 2 in Denition 2 fails.
Let us extract some informative features from the idea in Algorithm 1. Let
B = f0; 1g be a binary set. We introduce a function f :B

T

B ! Bdened

as follows to transcribe the basic idea in Algorithm 1:

f(x; s) = f s if x = 0;
s otherwise,

(7.10)

for x;s;s 2 where s is the inverse value of s. We may say that function

f(x;s) preserves the value of s if x = 0, and reverses it otherwise (x = 1). In
the subject of sequential circuits, the behavior of f(x;s) is equivalent to that of
a T ip-op where s, x and f(x;s) are the current state, toggle input, and next
state, respectively. In the area of logical operations, f(x;s) can be implemented
by using the Exclusive-OR operation ( ), that is, f(x;s) = xs.
Let B be a binary image and R 1 be a random grid with

B

(R 1 ) = 1=2. By
introducing function f, the essential idea of Algorithm 1 for generating each
pixel r 2 2 R 2 corresponding to r 1 2 R 1 and b 2 B can be formulated as

T

r 2 = f(b;r 1 ): (7.11)

Note that when b = 0, r 2 = r 1 ; while b = 1, r 2 = r 1 . This is exactly the same
as the manipulation of Step 2 in Algorithm 1.

This critical observation is emphasized as a corollary as follows.

Corollary 2 If R 1 is a random grid with (R 1 ) = 1=2 and the corresponding

pixel r 2 2 R 2 of r 1 2 R 1 is obtained by r 2 = f(b;r 1 ) for each r 1 2 R 1 with
any b 2

T

B , then R 2 is a random grid with T (R 2 ) = 1=2.

=
fR 1 ;R 2 ;:::;R n g) with respect to B is now introduced as follows. We rst
generate n 1 random grids R 1 ;R 2 ;:::;R n1 independently with

By using function f, our rst construction of a set of (n;n)-VCRG ( E

(R k ) =
1=2 for 1 6 k 6 n 1. That is, for every pixel b 2 B its n 1 corresponding
pixels r 1 ;r 2 ;:::;r n1 are totally random where r k 2 R k for 1 6 k 6 n 1.
Based upon r 1 ;r 2 ;:::;r k , we compute a k for 1 6 k 6 n 1 by using the
recursive formula:

T