Cryptography Reference
In-Depth Information
j
w
(q 1)
w
. Each such pat-
of patterns with w nonzero elements equals
tern yields a column in A(C) with exactly w ones in the j prescribed rows.
Consequently, the number of ones in the sum of the j rows from A(C) under
consideration equals
j
w
q
kj
X
w odd
1
2
q
kj
((q 1 + 1)
j
(1)
j
(q 1 1)
j
):
(q 1)
w
=
2q
(q
k+1
1
Proposition 4 [17] The sum of any k+1 rows of A(C) has a weight
(2 q)
k+1
)
q1
q
2
k
.
Proof Consider k + 1 positions in C. Any two distinct words from C differ
in at least two of these positions. That is, restricted to these k + 1 positions,
C is a [k + 1;k; 2] code over GF(q). The number of words of weight w in such
a code equals
k + 1
w
(1)
j
w 1
j
w
X
q
w2j
b
w
=
(q 1)
j=0
k + 1
w
(q1)
w1
(1)
w1
q
=
:
The weight of the sum of the rows of A(C) corresponding to the k + 1 chosen
positions is obtained by summing the above expressions of b
w
over all odd w.
Theorem 6 [17] Let 2 k n 1, and let q be a prime power not smaller
than n1. There exists a [(k;n); q
k
;
2
(q
k
+ (1)
k
(q2)
k
+ (q1)2
k
);
2
(q
k
+
(1)
k
(q 2)
k
)] VC scheme with contrast (q 1)2
k1
=[q
k
+ (1)
k
(q 2)
k
+
(q 1)2
k1
].
Proof Let C be an [n;k] MDS code over GF(q), and let D be an [n;k 1]
MDS code over the same field. In the notation of this section, let A equal
A(C), and let B equal the concatenation of q copies of A(D). By combining
the above results, (A;B) is a (k;n) pair, and (P(A);P(B)) is a VC scheme
with parameters as claimed in the theorem.
Bounds on the parameters m;h and l
Tuyls provided bounds on the parameters of a (k;n)-VC scheme. We start
by proving that maximal contrast schemes (l = 0) do not exist. We note that
for OR-based schemes maximal contrast schemes can always be constructed.
Proposition 5 [17] Let 3 k < n. There exists neither a [(k;n); m;h; 0] VC
scheme, nor a [(k;n); m;m;l] VC scheme.
Search WWH ::
Custom Search