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

Example 3 Take = (0; ; 0; 1; 2; ;nk;nk + 1) T . As = S, we
have by definition

(1) v ni
v

n X

i = (vk + i + 1):

v=ki1

If k = 3, then = (2 n; 1; 0; 0; ;1;n 2). Consequently, =
(0; 1; 0; ; 0;n 2) and = (n 2; 0; ; 0; 1; 0). That is to say, A = C()
consists of the n n identity matrix and n 2 columns of weight n, while
B = C() consists of n 2 all-zero columns and furthermore contains each
column of weight n 1 once. It is clear that A and B both contain 2n 2
columns. Straightforward computations show that a 1 = b 1 = n1, a 2 = b 2 = 2,
a 3 = n+1, b 3 = n3. As a consequence, we obtain a [(3;n); 2n2;n+1;n3]
VC scheme with = 2=(n 1).

Construction 2
In general, it seems hard to give manageable expression for the physical
parameters of the schemes obtained with Construction 1. Tuyls [17] gave an-
other explicit construction of a (k;n) VC scheme that has the virtue that the
physical parameters of these schemes can readily be computed in Reference
[17]. For constructing these matrices, they used maximum distance separable
(MDS) codes over GF(q), the nite eld with q elements. An [n;k] MDS code
over GF(q) consists of q k vectors of length n with entries from GF(q) such
that any two codewords have a Hamming distance of at least nk + 1. It
is known that such a code exists whenever q + 1 n. Therefore, we choose
q n 1.

Lemma 5 [17] Let C be an [n;k] MDS code over GF(q). In any set of k
positions, each of the q k possible patterns occurs in exactly one of the words
of C.

Proof Fix k positions, two codewords that agree in these positions, differ
in at most nk positions. We conclude that each of the q k patterns agrees
with at most one codeword. As the number of patterns equals the number
of codewords, each pattern agrees with exactly one codeword in the given
positions.
Let C be an [n;k] MDS code over GF(q). Let U(C) be an nq k matrix
over GF(q) in which each word from C occurs as a column once, and let A(C)
be the binary nq k matrix obtained from U(C) by replacing each nonzero
symbol in GF(q) by a `1,' and the zero symbol in GF(q) by a `0.'

Proposition 3 [17] Let 1 j k, the sum of any j rows of A(C) has weight
1

2 q kj [q j (2 q) j ].

Proof Consider j rows from U(C). Lemma 5 implies that each of the q j pos-
sible patterns occurs in these j positions in q kj words from C. The number