Cryptography Reference
In-Depth Information
Hence, b y L em ma 1, the number of columns N y (A) in A and the number of
columns N y (B) in B of type y = fy 0 ; ;y t1 g a re e qua l for all binary vectors
y of length t. As a consequence, the matrices A and B are equal up to a col-
umn permutation, which readily implies indistinguishability in the rows under
consideration in the multisets P(A) and P(B).
Construction 1
Now an explicit construction of (k;n) VC schemes for all n and all k
with 1 k n will be given below. According to Theorem 3, it is sucient
to construct (k;n)-pairs for all such n and k. We will obtain such pairs by
concatenation of matrices from a fixed collection of building blocks.
For each n and w with 0 w n, we let the n
n
w
-matrix C w consist
n
w
of all the
dierent 0 1 column vectors of weight w, in any order.
In the sequel, we will need an explicit expression for the weight of the sum
of any j rows from C w . In Lemma 2, we state the result. Here and in what
follows, we will use the standard convention that
n
k
= 0 whenever k < 0 or
k > n.
Lemma 2 [17] The weight of the sum of any j rows, 1 j n, from C w
does not depend on the choice of the rows and is equal to M j;w , where
j
i
nj
wi
M j;w = X
i odd
:
Let = ( 0 ; ; n ) T be a vector of length n + 1 with nonnegative integer
entries. We dene the matrix C() to be the matrix consisting of the concate-
nation of 0 copies of C 0 , 1 copies of C 1 , , n copies of the matrix C n . It is
clear that c 0 (), the number of columns of C(), satises C 0 () = P
w
n
w
w
.
According to Lemma 2, the weight of the sum of any j rows of C() equals
c j (), where
j
i
nj
wi
c j () = X
w
w X
i odd
:
Hence, if we dene c() = (c 0 (); ;c n ()) T , then the above can also be
written as c() = M, where M is the (n + 1) (n + 1) matrix with entries
n
w
the M j;w as dened in Lemma 2 for j 1 and with M 0;w =
. Now
suppose that and are nonnegative integer vectors such that M and M
agree in position 0; 1; ;k 1, but dier in position k. Then (C();C())
is a (k;n) pair of matrices to which we can apply Theorem 2. The way to
nd such vectors and is described in Theorem 5, which uses Lemma 3,
Corollary 4, and Lemma 4 below.
 
Search WWH ::




Custom Search