Cryptography Reference
In-Depth Information
Lemma 3 [17] For 1 j n, 1 w n, we have that M
j;w
=
P
(2)
k1
j
k
nk
wk
.
k1
The following corollary is a direct consequence of Lemma 3.
nk
wk
Corollary 4 Let R and L be the matrices defined as R
k;w
=
for
0 k, w n and L
0;0
= 1;L
i;0
= L
0;i
= 0 if i > 0, and L
j;k
= (2)
k1
j
k
if 1 j;k n. Then M = LR.
We dene the (n + 1) (n + 1) matrix S by S
i;j
= (1)
i+j
ni
j if
.
Lemma 4 [17]The matrices R and S are inverses of each other.
Theorem 5 [17] Let 1 k n 1. Let = (
0
;
1
; ;
n
) be an integer-
valued vector such that
j
= 0 if 0 j k 1, and
k
6= 0, and let := S.
For 0 j n, we dene
j
= max(0;
j
) and
j
= min(0;
j
):
Then and are vectors with nonnegative integer entries, and (C();C()) is
a (k;n) pair. The parameters of the corresponding [(k;n); m;h;l] VC scheme
satisfy the following equations:
n
w
X
1
2
;hl = 2
k1
j
k
j;
m =
j
w
j
w=0
(1)
i
k
i
nk
will
X
j
w
j
X
i
1
2
and h + l = m +
:
w=0
Proof As S has integer entries, has integer entries, hence and have
nonnegative integer entries. Using Corollary 4, Lemma 4, and the fact that
= , we nd that
c() c() = MM = M() = M = LRS = L:
As L is a lower triangular matrix, and
j
= 0 if j < k, it follows that c
j
()
c
j
() if 0 j k 1, and that
hl = jc
k
() c
k
()j = jL
k;k
k
j = 2
k1
j
k
j:
Moreover, 2m = c
0
() + c
0
() = c
0
( + ) = c
0
(jj), and similarly (mh) +
(ml) = c
k
( + ) = c
k
(jj).
We will give an example to illustrate the construction.
Search WWH ::
Custom Search