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
.
Search WWH ::




Custom Search