Cryptography Reference
In-Depth Information
Now we assume without loss of generality that the top n k + 1 rows
of B are distinct. Let c be the sum of the k 1 bottom rows of B. For
1 i n k + 1, the sum of c and the i-th row of B contains at most l
ones; that is to say, the i-th row of B has a Hamming distance at most l to
the complement of c. As the nk + 1 top rows of B are distinct, nk + 1 is
at most the number of vectors at distance at most l from the complement of
m
i
l
P
c, so nk + 1
.
i=0
Construction 3
Droste [9] proposed an algorithm to construct a (k;n)-VC scheme under
the OR operation. Liu et al. [13] proved that the basis matrices constructed
by that algorithm are also the basis matrices of a (k;n)-VC scheme under the
XOR operation. Droste's algorithm can be described as follows.
For easy specification, we call a column of a Boolean matrix with an even
number of 1's even and otherwise odd. If B is a Boolean matrix, we dene
P(B) as the multiset of matrices obtained by permuting the columns of B,
i.e., each permutation corresponds exactly to one element of P(B).
The following lemma will be needed later.
Lemma 8 [9] Let B
0
and B
1
be two nm Boolean matrices so that there
exist m 2
k1
column vectors v
1
; ;v
m2
k1
2 f0; 1g
k
with the following
property: for every fi
1
; ;i
k
gf1; ;ng the restriction of B
0
(resp. B
1
) to
the rows i
1
; ;i
k
contains every even (resp. odd) column of length k exactly
once and all columns v
1
; ;v
m2
k1
. Then P(B
0
) and P(B
1
) are a k out of
n secret sharing scheme with relative contrast 1=m; here the contrast is dened
as =
h
m
.
The main idea for construction is to start with an empty matrix (which
n
q
has no columns) and, for various q 2f0; ;ng and all
columns, which
have exactly q 1's. Because of the symmetry of this construction with respect
to rows, all restrictions of such a matrix of k rows contain the same columns.
And one can exactly determine which columns they contain.
n
q
Lemma 9 [9] For q 2f0; ;ng let B be an n
Boolean matrix that
contains every column with q 1's exactly once. Then every restriction of B to
k rows (with k n) contains every column with p 1's exactly
nk
qp
-times
(where p 2 maxf0;q (nk); ; min(q;k)g).
Lemma 9 shows a possibility to expand a matrix, if we add to all its
restrictions every column with p 1's exactly once: just add all columns with
q = p or q = p + nk 1's to the entire matrix. So a subroutine ADD(p, B)
adds to each restriction of k rows of a matrix B every column with p 1's by
adding columns to the entire matrix.
Search WWH ::
Custom Search