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.