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

random grids.) We focus on pixel t = 0 in S V (or t 2 S V (0)) only. Its corre-
sponding pixels r w+1 2 R w+1 ;r w+2 2 R w+2 ;:::;r u 2 R u should all be trans-
parent, i.e., r w+1 = r w+2 = = r u = 0. Consequently, its corresponding
pixel a u 2 A u becomes

a u = f(r u ;f(r u1 ;:::;f(r w+1 ;f(r w ;f(r w1 ;:::;f(r 2 ;r 1 )) :::))))
= f(0;f(0;:::;f(0;f(r w ;f(r w1 ;:::;f(r 2 ;r 1 )) :::))))
= f(r w ;f(r w1 ;:::;f(r 2 ;r 1 ) :::)):
From Lemma 6, we have t (a u ) = 1=2. In summary, if t = 0 in S V (or
t 2 S V (0)), then t (a u ) = 1=2; therefore,T(A u [S V (0)]) = 1=2.
Lemmas 5{7 investigate the properties of u =

fR 1 ;R 2 ;:::;R u g and another u random grids A 1 ;A 2 ;:::;A u produced by
formula (7.12) with respect to

random grids in U

for u > 2. Now we pay attention to Algo-
rithm 4. Give a secret image B and n participants, Algorithm 4 first produces
a set of n 1 independent random grids, namely

U

= fR 1 ;R 2 ;:::;R n1 g,
based upon which A 1 ;A 2 ;:::;A n1 are generated, and then R n is produced
according to A n1 and B. We claim that R n is a random grid and the super-
imposed result of any group of less than n shares is also a random grid.

R

Lemma 8 Give a secret image B and a set of independent random grids
R = fR 1 ;R 2 ;:::;R n1 g;

(1) R n generated by formula (7.13) is a random grid with T (R n ) = 1=2; and

(2) S D is a random grid with T (S D ) = 1=2 d where D = fR i 1 ;R i 2 ;:::;R i d g

R [fR n g and S D = R i 1 R i 2 R i d :

Proof
(1) By setting u = n1 in Lemma 6, we know that A n1 is a random grid
withT(A n1 ) = 1=2 (or t (a n1 ) = 1=2) for a n1 2 A n1 . For r n 2 R n [B(0)],
r n = f(0;a n1 ) = a n1 ; while r n 2 R n [B(1)], r n = f(1;a n1 ) = a n1 . It
implies that both R n [B(0)] and R n [B(1)] are areas of random grids with
R n [B(0)] = 1=2 = R n [B(1)]. By the principle of combination, R n is a random
grid with (R n ) = 1=2.

(2) Since the generation of R n is different for R 1 ;R 2 ;:::;R n1 (in fact, R n
is generated from B and A n1 which depends upon R 1 ;R 2 ;:::;R n1 (see for-
mulae (7.12) and (7.13))), there are two cases with regard to the constituents
of

T

D : Case 1: R n 2 D ; and Case 2: R n 2 D .

are independently generated, S D
is a random grid according to Lemma 5 with

For Case 1, since all random grids in D

(S D ) = (S D [B(0)]) = T T

(S D [B(1)]) = 1=2 d .
Regarding Case 2, assume that

T

D = fR i 1 ;R i 2 ;:::;R i d1 ;R n g. Let L =

[fR n g) and S L = R i 1 R i 2 R i d1 .
From Lemma 5, we realize that S L is a random grid with

fR i 1 ;R i 2 ;:::;R i d1 g (i.e., D = L

(S L ) = 1=2 d1 .
Besides, by setting u = n 1 and v = d 1 in Lemma 7(2), we obtain

T