Cryptography Reference
In-Depth Information
Proof: First, we prove item (1). For 0 ≤ u ≤ N − 1, let x u = 1, if u
does not occur in T w ; otherwise, let x u = 0. Hence, the number of values in
N−1
Z N that do not occur at all in T w is given by X =
x u . A value u does
u=0
not occur in T w , if and only if it does not occur in any G
w τ . For u = κ[w],
according to item 1 of Theorem 4.5.4,
M w τ
n w
P(x u = 1) =
(1−p w τ x ).
τ=1
x=1
Assuming that each g w τ x , 1 ≤ x ≤ M w τ , takes each value u ∈
Z N
\{κ[w]}
with equal probabilities, we have
= 1−p w τ x
N −1
= q w τ x .
P(g w τ x = u)
So, for u ∈
Z N
\{κ[w]},
M w τ
n w
P(x u = 1) =
(1−q w τ x ).
τ=1
x=1
We compute
N−1
E(X)
=
E(x u )
u=0
= E(x κ[w] ) +
E(x u ),
u∈Z N \{κ[w]}
where E(x u ) = P(x u = 1). The expected number of distinct values ∈
Z N
occurring in T w is then given by N −E(X).
Next, we come to item (2). Here, let x u = 1, if u occurs exactly c times in
T w ; otherwise, let x u = 0. Hence, the number of values from Z N that occurs
exactly c times in T w is given by
N−1
X =
x u .
u=0
Now, u occurs exactly c times in T w , if and only if it occurs once in exactly
c out of n w many G
w 's and it does not occur in any of the remaining n w
−c
many G
w 's. For u = κ[w], P(x u = 1) is given by item (2) of Theorem 4.5.4. In
the same expression, p w τ r x would be replaced by q w τ r x , when u= κ[w]. Since
N−1
E(x u ) = P(x u = 1), and E(X ) =
E(x u ), we get the result by adding the
u=0
individual expectations.
Search WWH ::




Custom Search