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

The importance of this definition stems from the following theorem.

Theorem 2 [17] If (A;B) is a (k;n)-pair of n m matrices, then
(P(A);P(B)) is a [(k;n); m;h;l] VC scheme with h = max(ma k ;mb k )
and l = min(ma k ;mb k ). Here, a k and b k denote the weight of the sum
of any k rows from A and B, respectively.

Some notations are given here for later use. For a binary vector v of length
m, we define Z(v) as the number of zeros in v, and H(v) as its number of ones.
Moreover, we dene the unbalance (v) of v by (v) = Z(v) H(v). Note
that (v) = m2H(v). For later use, we also observe that (v) =

P

(1) v j .

j=1

With each binary nm matrices A we associate two vectors (A) and N(A)
of length 2 n , with the components indexed by binary vectors of length n.
For each binary vector x of length n, the x-th component x (A) of (A) is
dened as x (A) = (x T A), the unbalance of the sum of the rows in A whose
index i satisfies xi i = 1; also, the x-th component N x (A) of N(A) is defined
as the number of columns of A that are equal to x. Lemma 1 will show that
the vectors (A) and N(A) can be computed from each other. To make this
precise, define the 2 n 2 n matrix H by H(x; y) = (1) (x;y) , where x, y are
binary vectors of length n and (x; y) =

P

x i y i denotes the inner product of
x and y. Then we have the following lemma:

i=1

Lemma 1 [17]

The matrix H is a Hadamard matrix, that is, HHT T = 2 n I. 1.

2. The vectors (A) and N(A) are related by (A) = HN(A).

We are now in the position to prove a generalization of Theorem 2. Before
stating it, we need one more notation: if A is a n m matrix, then w(A I )
denotes the weight of the sum of the rows of A indexed by I. Note that
w(A I ) =

1
2 (m (I) (A)), where (I) is the characteristic vector of the set I.

Theorem 3 [17] Let A and B be n m matrices such that for each I
f1; 2; ;ng of size at most k 1, w(A I ) = w(B I ). Assume moreover that
there exist integers h and l such that h > l and that for each I f1; 2; ;ng
of size k, m w(A I ) h and m w(B I ) l. Then (P(A);P(B)) is a
[(k;n); m;h;l] VC scheme.

Proof The only nontrivial thing we have to prove is the indistinguish ab ility.
Le t I = fi 1 ; ;i t g be a subset of f1; 2; ;ng of size t < k. Let A and
B denote the restrictions of A and B to the t rows indexed by I. Let x =
fx 1 ; ;x t g be a binary vector of length t, and let x be the binary vector of
length n for which entry i j is equal t o x j for j = 1; 2; ;t, and whose other
entries equal zero. It is clear that x (A) = ~x ( A ). As x h as weight at most t,
we find, using properties of A and B, that x (A) = x (B).