Cryptography Reference
In-Depth Information
where 0 ≤ x
u
≤ d−1,∀u ∈ [1,t]. The number of solutions is given by c(δ,t).
Similarly, the number of distinct sequences of indices in
N −1−
l
2
,N −2
satisfying conditions 4, 5 and 6 of Definition 4.7.9 is c(δ
′
,t
′
). Hence, the
number of distinct sequences of indices in
0,
l
2
N −1−
l
−1
∪
2
,N −2
satisfying the conditions 1 through 6 is
c(δ,t)c(δ
′
,t
′
).
δ≤d,δ
′
≤d
t≤
2
−δ,t
′
≤
2
−δ
′
In Lemma 4.7.10, we have considered all the items except item 7 of Defini-
tion 4.7.9. Subsequent results related to Definition 4.7.9 would consider item
7 separately and would combine Lemma 4.7.10 with that computation.
Theorem 4.7.11. The probability of existence of a d-favorable (t,t
′
)-bisequence
in
[0,l−1]∪[N −1−l,N − 2]
is
0
@
1
0
@
i
′
u
′
∈B
t
′
1
A
A
p
i
′
u
′
π
d
=
p
i
u
q
i
v
t,t
′
F
t
,B
t
′
i
u
∈F
t
i
v
∈
[
0,
2
−1
]
\F
t
0
1
0
1
@
A
@
A
q
i
′
v
′
1−
q
y
,
i
′
v
′
∈
[
N−1−
2
,N−2
]
\B
t
′
y∈
[
2
,i
t
+d
]
∪
[
i
t
′
−d,N−2−
2
]
where the sum is over all t,t
′
,F
t
,B
t
′
such that the sequence of indices F
t
∪
B
t
′
satisfy the conditions 1 through 6 in Definition 4.7.9 and q
y
= q
y
or q
′
y
according as y ∈
2
,i
t
+ d
−d,N −2−
2
respectively.
Proof: Immediately follows from Lemma 4.7.7. The term
0
or
i
t
′
1
@
A
1−
q
y
y∈[i
t
+1,i
t
+d]∪[i
t
′
−d,i
t
′
−1]
accounts for condition 7 of Definition 4.7.9.
Using the definitions of c(δ,t), c(δ
′
,t
′
) introduced in Theorem 4.7.10, one
can approximate the probability expression presented in Theorem 4.7.11 as
follows.
