Cryptography Reference
In-Depth Information
2. Exactly t
′
many filters
N −1−
l
2
≤ i
t
′
< ... < i
′
1
≤ N −2
N −1−
2
,N −2
exist in the interval
.
2
,l−1
or a filter i
t
′
+1
exist
3. Either a filter i
t+1
exist in the interval
N −1−l,N −2−
2
in the interval
.
0,
2
Lemma 4.7.7. Given a set F
t
of t many indices in
−1
, a set B
t
′
of t
′
N −1−
2
,N −2
l
many indices in
and an index x in
2
,l−1
∪
N −1−l,N −2−
2
, the probability of the sequence of indices F
t
∪B
t
′
∪{x}
to be a (t,t
′
)-bisequence is
0
@
1
0
@
i
′
u
′
∈B
t
′
1
A
p
i
′
u
′
A
p
i
u
q
i
v
i
u
∈F
t
i
v
∈[0,l−1]\(F
t
∪{x})
0
1
@
q
i
′
v
′
A
p
x
,
i
′
v
′
∈[N−1−l,N−2]\(B
t
′
∪{x})
where q
y
= 1−p
y
, q
′
y
= 1−p
′
y
for 0 ≤y ≤ N−1 and p
x
= p
x
or p
′
x
according
as x ∈
2
,l−1
N −1−l,N −2−
2
or
respectively.
∪{x} would be an (t,t
′
)-
bisequence, if the indices in F
t
and B
t
′
and the index x are filters and the
indices in ([0,l−1]∪[N−1−l,N−2])\(F
t
Proof: According to Definition 4.7.6, F
t
∪B
t
′
∪{x}) are non-filters. Hence,
the result follows from Propositions 4.7.2 and 4.7.4.
∪B
t
′
Definition 4.7.8. (Critical Filter) The last filter i
t
within the first
2
indices
and the first filter i
t
within the last
2
indices for an (t,t
′
)-bisequence are called
the left critical and the right critical filters respectively. Together, they are
called the critical filters.
l
Definition 4.7.9. (Favorable Bisequence) For d ≤
2
, a (t,t
′
)-bisequence
is called d-favorable, if the following seven conditions hold.
1. i
1
+ 1 ≤ d.
2. i
u+1
−i
u
≤ d, ∀u ∈ [1,t−1].
l
2
3.
−1−i
t
≤ d.
4. N −1−i
′
1
≤d.
5. i
′
v
−i
′
v+1
≤ d, ∀v ∈ [1,t
′
−1].
N −1−
2
6. i
t
′
−
≤d.