Cryptography Reference
In-Depth Information
≤d or i
t
′
−i
t
′
+1
7. i
t+1
−i
t
≤d.
Let us briefly explain the rationale behind Definition 4.7.9.
• For ease of analysis, a dummy index −1 is introduced to the left of index
0.
• Conditions 1 and 4 ensure that the first filter to the right of index −1
and the first filter to the left of index N −1 are at most at a distance d
from indices −1 and N −1 respectively.
• Conditions 2 and 5 guarantee that the distance between any two con-
secutive filters to the left of the left critical filter and to the right of the
right critical filter is at most d.
• Conditions 3 and 6 ascertain that the left and right critical filters are
at most at a distance d from indices
− 1 and N − 1 −
2
respectively.
Consider the first filter i
t+1
to the right of the left critical filter and the
first filter i
t
′
+1
to the left of the right critical filter. At least one of i
t+1
and i
t
′
+1
must exist for a (t,t
′
)-bisequence.
• Finally, Condition 7 ensures that whichever exist (and at least one of
the two, if both exist) is located at most at a distance d from the corre-
sponding critical filter.
Lemma 4.7.10. The number of distinct sequences of indices in
l
2
0,
l
2
N −1−
l
−1
∪
2
,N −2
satisfying the conditions 1 through 6 of Definition 4.7.9 is
c(δ,t)c(δ
′
,t
′
),
δ≤d,δ
′
≤d
t≤
2
−δ,t
′
≤
2
−δ
′
, and c(δ,t) is the coe
cient of
l
2
N −1−
2
− 1 −i
t
, δ
′
= i
t
′
where δ =
−
x
2
−δ−t
in (1 + x + ... + x
d−1
)
t
.
Proof: Let x
1
= i
1
and x
u
= i
u
− 1 for 2 ≤ u ≤ t be the number
of non-filters between two consecutive filters in [0,i
t
]. The total number of
non-filters in the interval [0,i
t
] is
−i
u−1
l
2
i
t
−(t−1)
=
−1−δ
−(t−1)
l
2
=
−δ−t.
0,
2
Thus, the number of distinct sequences of indices in
satisfying con-
ditions 1, 2 and 3 of Definition 4.7.9 is the same as the number of non-negative
integral solutions of
−1
x
1
+ x
2
+ ... + x
t
=
l
2
−δ−t,