Cryptography Reference
In-Depth Information
x+m−1
x+m−1
Event 1:
S
r
[r] =
S
x
[r].
r=x
r=x
The equality holds necessarily when S
r
[r] = S
x
[r], for r = x,...,x +
m− 1. This means that for d = 1,...,m− 1, j
x+d
cannot take values
from {x + d,...,x + m− 1}, i.e., cannot take exactly m−d different
values. Hence, Event 1 happens with a minimum probability of
m−1
m−1
N −(m−d)
N
N −d
N
=
.
d=1
d=1
Event 2: S
x+m−1
[j
x+m
] = S
x
[j
x+m
].
If neither i
r
nor j
r
visits j
x+m
, the value at the index j
x+m
remains
unchanged during the rounds r = x + 1,...,x + m− 1. During these
m−1 rounds, i
r
takes m−1 distinct values, none of which equals j
x+m
with probability
N−m+1
N
. Also, None of j
r
's equal j
x+m
with probability
(
N−1
N
)
m−1
. Thus, Event 2 occurs with a minimum probability of
m−1
N −m + 1
N
N −1
N
.
When both the above event occurs, we have
S
x+m
[x + m−1]
= S
x+m−1
[j
x+m
]
(due to swap in round x + m)
= S
x
[j
x+m
]
(due to Event 2)
x+m−1
= S
x
j
x
+
(S
r
[r] + K[r])
(by Equation (7.9))
r=x
x+m−1
= S
x
j
x
+
(S
x
[r] + K[r])
(due to Event 2)
r=x
or in other words,
x+m−1
−
x+m−1
K[r] = S
−1
x
[S
x+m
[x + m−1]]−j
x
S
x
[r].
(7.10)
r=x
r=x
A lower bound of the probability of Equation (7.10) is given by
m−1
m−1
N −m + 1
N
N −1
N
N −d
N
α
m
=
.
(7.11)
d=1
Similar to Case I in Section 7.4, S
x+m−2
[x + m−1] = S
x+m
[x + m−1] with
probability (
N−
N
)
N−2
. When this holds along with Equation (7.10), then due
to the Glimpse bias (Corollary 5.2.2), x+m−1−z
x+m−1
equals S
x+m
[x+m−1]
