Cryptography Reference
In-Depth Information
see the figure below.
−Θ+
d
−Θ− d
Θ+
d
Θ
d
Θ−
d
..
Θ−
d
Θ+
d
−Θ−
d
−Θ+
d
Fig. 2.
The intersection of
A
∗
and
B
∗
with
E
Since the coecient of
M
associated with (
r, s
)in
A
∗
is
m
r−θ
,andthecoe-
cient associated with (
r, s
)in
B
∗
is
m
r
, we know that
m
r
=0forevery
r
in the
union, ((
π
1
(
A
∗
∩
π
1
(
B
∗
∩
E
)
−
θ
)
∪
E
)), where:
π
1
(
A
∗
∩
E
)
−
θ
=[
d
+1
,
−
2
θ
−
∪
−
2
θ
+
d
+1
,
−
θ
−
∪
−
θ
+
d
+1
,n
−
1]
.
(18)
1]
[
1]
[
Notice that
π
1
(
B
∗
∩
E
)and
π
1
(
A
∗
∩
θ
are symmetric with respect to
[
d
+1
,n−
1], and therefore their union is [
d
+1
,n−
1] if and only if the first
“gap”, [
θ, θ
+
d
], of
π
1
(
B
∗
∩
E
)
−
E
) is contained in the first or second subinterval of
π
1
(
A
∗
∩
E
)
−
θ
. This occurs when either
θ
+
d
≤
n
−
2
θ
−
1, which is equivalent
to 3
θ
+
d<n
,or
n
−
2
θ
+
d
+1
≤
θ
, which is equivalent to
n<
3
θ
−
d
;thus,
since by hypothesis
1].
Furthermore, since the boundary of
E
,
∂E
, corresponds to regions at which the
coecient of the right side of (12) is a single
λ
if
,wecanusethecomplementary
technique, checking the coecients corresponding to
∂E
|
n
−
3
θ
|
>d
,wehave
m
r
=0forall
r
∈
[
d
+1
,n
−
−
(
A
∪
B
∪
C
∪
D
), to
reveal that
λ
if
=0for
if
1].
Moreover, we can compare coecients at the intersection of
∂E
and one of
A
∗
,
B
∗
,
C
∗
,or
D
∗
.For
∂E
∈
[
d
+1
,θ
−
1]
∪
[
θ
+1
,n
−
θ
−
1]
∪
[
n
−
θ
+1
,n
−
d
−
A
∗
, we get the relations
λ
if
∩
=
m
d
+
if
for
if
∈
[1
,d
−
1],
B
∗
,weget
λ
if
=
m
if
for
if
and for
∂E
1]. Since we have already
shown that such coecients of
M
are zero,
λ
can only be nonzero for the values
λ
0
,
λ
d
,
λ
θ
,
λ
n−θ
,and
λ
n−d
.
Using this information we can greatly simplify (13), and as a consequence, get
further information about the coecients of
M
. In particular, from collecting
coecients for monomials with indices (
θ, i
), for
if
∩
∈
[
n
−
d
+1
,n
−
∈
[0
,d
], we get the relations
m
q
0
+
m
if
=
λ
0
+
λ
−d
.Thus,
m
if
=
m
0
for
if
≤
d
, and, finally, we see that
M
=
m
0
π
.
The preceding theorem gives us precise criteria for when the space of linear
maps,
S
G
, consists of only projected multiplication maps. Furthermore, it was
stated in [10] and [15] that these multiplication maps satisfy the relation (2)
only if the multiplication commutes with the projection, which happens precisely
