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