XOR-Based Visual Cryptography - Visual Cryptography and Secret Image Sharing - page 162

Proof Let S = (C 0 ;C 1 ) be a [(k;n); m;h; 0] VC scheme and let B 2 C 1 .
Denote by 1 ; 2 two arbitrary rows in B. Since n2 k1, B contains (at
least) k 1 more rows. We denote these rows by 3 ; ; k+1 . Since S is a
scheme with l = 0, the XOR of 1 ; 3 ; ; k+1 is the all-one vector, as is the
XOR of 2 ; 3 ; ; k+1 . If follows that 1 = 2 , so all rows of B are equal.
Next, let A 2 C 0 and consider row i and j of A. As k 3, the indistin-
guishability property of Denition 1 implies that there is a B 2 C 1 that agrees
with A in these rows. As all rows of B are equal, the i-th and j-th row of A
are equal. Since i and j are arbitrary, all rows of A are equal, so A = B, a
contradiction.
The second statement follows from an analogous reasoning.
The next two propositions show that XOR-based VC schemes with odd
and even k fundamentally differ.

Proposition 6 [17] Let k be odd, and let k < n. For each > 0, there are
integers m;h, and l such that l=m < and a [(k;n); m;h;l] VC scheme exists.

Proposition 7 [17] Let k be even, and let k < n. If a [(k;n); m;h;l] VC
scheme exists, then l=m 1=(k + 1).

Corollary 7 [17] For even k < n, the contrast of a k out of n VC scheme is
at most k=(k + 2).

Proof Let S be a [(k;n); m;h;l] scheme. By denition, the contrast is equal
to (hl)=(h+l). It is clear that is increasing in h, and so (ml)=(m+l).
As (ml)=(m+l) is decreasing in l, we obtain an upper bound on by plugging
in the upper bound for l from Proposition 7.

Lemma 6 [17] Let k be an even integer. Let B be a binary matrix with n
rows such that the sum of any k rows from B differs from 0. Then B has at
least nk + 2 distinct rows.

Lemma 7 [17] Let (C 0 ;C 1 ) be a [(k;n); m;h;l] VC scheme with k 3, and
let c 1 and c 2 be two rows of a matrix in C 0 and hence also two rows of some
matrix in C 1 . Then, the Hamming distance between c 1 and c 2 satisfies

d(c 1 ;c 2 ) minf2l; 2(mh)g:

Proposition 8 [17] Let k be even, k 4. If a [(k;n); m;h;l] VC scheme

m
i

min(l;2(mh))

P

exists, then nk + 1 .

i=0

Proof Let k be even, k 4, and let S = (C 0 ;C 1 ) be a [(k;n); m;h;l] scheme.
Let B be a matrix in C 1 . As l 6= m, no k rows of B add to the all-zero word.
Lemma 6 implies that B has at least nk + 2 distinct rows. Since according
to Lemma 7, all rows from B have a Hamming distance at most 2(mh) to

m
i

2(mh)

P

its top row, we obtain nk + 2 .

i=0