Cryptography Reference
In-Depth Information
Moreover, π
0
= P(j
1
= h
0
(S
0
,K)) = 1. For y ≥ 1,
h
y
(S
0
,K)
= u(y,h
y−1
(S
0
,K),S
0
[y],S
0
[y−1],K[y],K[h
y−1
(S
0
,K)])
= h
y−1
(S
0
,K) + S
0
[y] + K[y]
= h
y−1
(S
0
,K) + y + K[y].
Solving the recurrence, we get
y
h
y
(S
0
,K) =
y(y + 1)
2
+
K[x].
x=0
From the analysis in the proof of Lemma 3.1.7, we see that in the recurrence
of h
y
, S
y
[y] has been replaced by S
0
[y] and j
y
has been replaced by h
y−1
(S
0
,K).
Hence, we would have
π
y
= P(S
y
[y] = S
0
[y])P(j
y
= h
y−1
(S
0
,K))
y
π
y−1
.
N −1
N
=
Solving this recurrence, we get
y(y+1)
2
y
x
N −1
N
N −1
N
π
y
=
=
.
x=0
Example 3.1.10. Consider the update rule
u(y,j
y
,S
y
[y],S
y
[j
y
],K[y],K[j
y
]) = j
y
+ S
y
[j
y
] + K[j
y
].
Here,
h
0
(S
0
,K)
= u(0,0,S
0
[0],S
0
[0],K[0],K[0])
= 0 + 0 + K[0]
= K[0]
and π
0
= P(j
1
= h
0
(S
0
,K)) = 1. For y ≥ 1,
h
y
(S
0
,K)
= u(y,h
y−1
(S
0
,K),S
0
[y],S
0
[y−1],K[y],K[h
y−1
(S
0
,K)])
= h
y−1
(S
0
,K) + S
0
[y−1] + K[h
y−1
(S
0
,K)]
= h
y−1
(S
0
,K) + (y−1) + K[h
y−1
(S
0
,K)].
From the analysis in the proof of Lemma 3.1.7, we see that in the recurrence of
