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

ADD(p,B)
Step 1: If p kp, add all the columns with q = p 1's to B.
Step 2: If p kp, add all the columns with q = p + nk 1's to B.
The subroutine makes it easy to construct basis matrices B 0 (resp. B 1 )
whose restrictions always contain every even (resp. odd) column. But besides
these columns, every restriction of B 0 and B 1 can contain remaining columns
(which are the same for all restrictions of one matrix because of the construc-
tion principle). To be appropriate for a k out of n scheme these remaining
columns have to be the same for B 0 and B 1 (see Lemma 8). So the remaining
columns of every restriction of B 0 , which are not remaining columns of every
restriction of B 1 , called the rest of B 0 , have to be added to every restriction
of B 1 and vice versa. In most cases, these added columns will create new rests
that cause new columns to be added.
Droste's algorithm
Step 1: For all even p 2f0; ;kg, call ADD(p, B 0 ).
Step 2: For all odd p 2f0; ;kg, call ADD(p, B 1 ).
Step 3: While the rests of B 0 and B 1 are not empty:
(a) Add to B 0 all columns adjusting the rest of B 1 by calling ADD.
(b) Add to B 1 all columns adjusting the rest of B 0 by calling ADD.
Theorem 8 shows that Droste's algorithm also generates a (k;n)-VC
scheme under the XOR operation, by Liu et al. [13].
Theorem 8 [13] Droste's algorithm generates the basis matrices of a (k;n)-
VCS, B 0 and B 1 , under the XOR operation.
Proof We need to prove that the basis matrices B 0 and B 1 satisfy the contrast
and security conditions of Definition 1.
First, for the contrast condition, we need to prove that the Hamming
weight of the stacking (XOR operation) of any k out of n rows of B 0 is less than
that of B 1 . Denote B 0 (resp. B 1 ) as the submatrix generated by restricting to
arbitrary k rows of B 0 (resp. B 1 ). According to the Steps 1 and 2 in Droste's
algorithm, it is clear that all the even (resp. odd) columns appear in B 0 (resp.
odd). Denote I 0 (resp.I 1 ) as the matrix whose columns are all the even (resp.
odd) columns of length k. Because Droste's algorithm terminates when the
rests of B 0 and B 1 are empty, it implies that the remaining columns of B 0
and B 1 are the same, that is, B 0 nI 0 = B 1 nI 1 . Denote R as the remaining
columns of B 0 and B 1 , we have B 0 = I 0 [R;B 1 = I 1 [R. Because the XOR
(operation) of the entries of an even (resp. odd) column is 0 (resp. 1), we have