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




Custom Search