Cryptography Reference
In-Depth Information
Expanding the left hand side of (12), similarly:
S
f
(
M, π
)(
a, x
)=
Df
(
Ma,πx
)+
Df
(
πa, Mx
)
n−
1
n−
1
m
i
a
q
i
,πx
)+
Df
(
πa,
m
i
x
q
i
)
=
Df
(
i
=0
i
=0
Df
(
m
i
a
q
i
,πx
)+
Df
(
πa, m
i
x
q
i
)
n−
1
=
i
=0
⎛
⎝
Df
(
m
i
a
q
i
,
⎞
⎠
n−
1
d
d
x
q
j
)+
Df
(
a
q
j
,m
i
x
q
i
)
=
i
=0
j
=0
j
=0
Df
(
m
i
a
q
i
,x
q
j
)+
Df
(
a
q
j
,m
i
x
q
i
)
n−
1
d
=
i
=0
j
=0
m
q
θ
i−θ
a
q
j
x
q
i
.
n−
1
d
i−θ
a
q
i
x
q
j
+
m
i
a
q
i
x
q
θ
+
j
+
m
i
a
q
θ
+
j
x
q
i
+
m
q
θ
=
i
=0
j
=0
(14)
Now, to analyze which monomials of the form
a
q
r
x
q
s
, have nontrivial coecients
for the pair of “indices” (
r, s
), we construct four index sets,
A
,
B
,
C
,and
D
,
relative to the four monomials in the above expression, respectively. We have:
A
=[0
,n
−
1]
×
[0
,d
]
B
=[0
,n
−
1]
×
[
θ, θ
+
d
]
(15)
C
=[
θ, θ
+
d
]
×
[0
,n
−
1]
D
=[0
,d
]
×
[0
,n
−
1]
.
We can see that only the pairs (
A, C
), (
A, D
), (
B, C
), and (
B, D
) have non trivial
intersections. Isolating the index pairs occurring in only one of these index spaces
we can find relations on the coecients of
M
and
Λ
M
which involve only one
m
i
.
If, furthermore, the index pair occurs in
E
, then the corresponding coe
cient
from
Λ
M
is zero. Let
denote the operation of taking one of these sets minus
the union of the other three. We notice that:
A
∗
=([
d
+1
,θ
∗
−
1]
∪
[
θ
+
d
+1
,n
−
1])
×
[0
,d
]
(16)
B
∗
=([
d
+1
,θ
−
1]
∪
[
θ
+
d
+1
,n
−
1])
×
[
θ, θ
+
d
]
if
d<θ
.
For both
A
∗
and
B
∗
, the first coordinate is the index associated with the
coe
cient of
M
in (14); we are, therefore, interested in which values of the first
coordinate are possible in
A
∗
∩
E
and
B
∗
∩
E
. Equivalently, we want to discover
π
1
(
A
∗
∩
E
)and
π
1
(
B
∗
∩
E
), where
π
1
is the projection mapping onto the first
coordinate. By a simple calculation, we have:
π
1
(
A
∗
∩
E
)=[
θ
+
d
+1
,
−
θ
−
1]
∪
[
−
θ
+
d
+1
,n
−
1]
∪
[
d
+1
,θ
−
1]
(17)
π
1
(
B
∗
∩
E
)=[
d
+1
,θ
−
1]
∪
[
θ
+
d
+1
,
2
θ
−
1]
∪
[2
θ
+
d
+1
,n
−
1]
,
