Cryptography Reference
In-Depth Information
3. S
N
[y] = S
y+1
[y], if j
t
= y, ∀t ∈ [y+2,N]. This happens with probability
(
N−1
N
)
N−y−1
.
Multiplying the above three probabilities, we get the result.
Note that the event A
y
implies j
y+1
= S
N
[y] and Proposition 4.7.2 is a
variant of Lemma 3.1.4 that relates j
y+1
and S
N
[y].
Definition 4.7.3. (Event B
y
) For 0 ≤ y ≤ N − 1, event B
y
occurs if and
only if the following three conditions hold.
1. S
y
[y] = y.
2. j
y+1
≤y.
3. S
N
[j
y+1
] = S
y+1
[j
y+1
].
Proposition 4.7.4. For 0 ≤ y ≤ N −1,
N−1
y + 1
N
N −1
N
p
′
y
= P(B
y
) =
.
Proof: Let us analyze the items mentioned in the definition of B
y
.
1. S
y
[y] = y occurs if j
t
= y for 1 ≤ t ≤ y, the probability of which is
(
N−1
N
)
y
.
≤y) =
y+1
N
2. P(j
y+1
.
3. S
N
[j
y+1
] = S
y+1
[j
y+1
], if j
t
= j
y+1
, ∀t ∈ [y + 2,N]. This happens with
probability (
N−1
N
)
N−y−1
.
Multiplying the above three probabilities, we get the result.
Note that the event B
y
implies j
y+1
= S
−
N
[y], 0 ≤ y ≤ N − 1. B
y
is the
same as the event A
1
(y) defined in the proof of Theorem 4.5.1.
Definition 4.7.5. (Filter) An index y in [0,N−1] is called a filter if either
of the following two holds.
1. 0 ≤ y ≤
2
−1 and event A
y
occurs.
N
2
2.
≤ y ≤N −2 and event B
y
occurs.
Definition 4.7.6. (Bisequence) Suppose j
N
is known. Then a sequence of
at least (t + t
′
+ 1) many filters is called a (t,t
′
)-bisequence if the following
three conditions hold.
1. Exactly t many filters
≤
l
2
0 ≤ i
1
< i
2
< ... < i
t
−1
0,
2
exist in the interval
−1
.