Cryptography Reference
In-Depth Information
Expanding the right hand side of (12) repeatedly, using the bilinearity of
Df
,
we obtain:
n−
1
λ
i
Df
(
πa, πx
)
q
i
Λ
M
Df
(
πa, πx
)=
i
=0
n−
1
d
d
a
q
j
,
x
q
l
)
q
i
=
λ
i
Df
(
i
=0
j
=0
l
=0
(13)
n−
1
d
d
λ
i
Df
(
a
q
j
,x
q
l
)
q
i
=
i
=0
j
=0
l
=0
λ
i
a
q
θ
+
j
x
q
l
+
a
q
j
x
q
θ
+
l
q
i
.
n−
1
d
d
=
i
=0
j
=0
l
=0
Notice that for each monomial term in this expression, the difference between
the exponent of
q
in the power of
a
and the exponent of
q
in the power of
x
is
l
−
θ
−
j
(mod
n
)or
l
+
θ
−
j
(mod
n
). Also, there is the restriction that
d
. From these facts we can determine which monomials never occur
in the right side of (12).
The monomial
a
q
r
x
q
s
may only occur in the right side of (12) if the difference
between the coordinates, (
s − r
)(
mod n
)
∈
[
−θ − d, −θ
+
d
]
∪
[
θ − d, θ
+
d
],
where we require 2
θ
+2
d<n
, avoiding overlap. Also, implicitly, we have the
restriction that for such an interval, (
u, v
), the positive residues
u
and
v
satisfy
0
≤
l, j
≤
0
1. For all other pairs, (
r, s
),
a
q
r
x
q
s
certainly has a coecient of
zero in the right side of (12). Therefore, we will study the set of pairs of indices,
≤
v
−
u
≤
n
−
E
=
{
(
r, s
)
|
s
−
r
∈
(
−
θ
+
d, θ
−
d
)
∪
(
θ
+
d,
−
θ
−
d
)
}
.
This set is the diagonal band in the space of indices for which the corresponding
coecients have no contribution from the right side of (12); refer to the shaded
region in the figure below.
−Θ+
d
−Θ−
d
Θ+
d
Θ−
d
..
Θ−
d
Θ+
d
−Θ−
d
−Θ+
d
Fig. 1.
The space of indices with the shaded region corresponding to monomials which
cannot occur on the right side of (12)
