Cryptography Reference
In-Depth Information
The Diffie-Hellman problem
steps require
O
(
√
B
) field operations,
O
(
√
B
log(
r
)) group operations and
O
(
√
B
log(
r
))
Fixed-CDH oracle queries.
Since
i
=
1
e
i
≤
log
2
(
N
) the exhaustive search or BSGS subroutine is performed
O
(log(
r
)) times. A more careful analysis using Exercise
13.2.7
means the complexity
is multiplied by log(
r
)
/
log(
B
). The Chinese remainder theorem and later stages are negli-
gible. The result follows.
Algorithm 26
Maurer reduction
INPUT:
g,h
g
a
,
E
(
=
F
r
)
OUTPUT:
a
1:
Associate to
h
an implicit representation for a point
Q
=
(
X,Y
)
∈
E
(
F
r
)using
Lemma
21.4.9
2:
Compute a point
P
=
i
=
1
l
e
i
∈
F
r
) that generates
E
(
F
r
). Let
N
=
F
r
)
E
(
#
E
(
i
[
N/l
i
]
P
:1
{
≤
≤
≤
≤
e
i
}
3:
Compute explicit representations of
i
k,
1
j
[
N/l
i
]
Q
:1
4:
Compute implicit representations of
{
≤
i
≤
k,
1
≤
j
≤
e
i
}
5:
for
i
=
1to
k
do
u
i
=
0
6:
Reducing DLP of order
l
e
i
i
for
j
=
1to
e
i
do
to cyclic groups
7:
[
N/l
i
]
P
and
Q
0
=
[
N/l
i
]
Q
Let
P
0
=
−
u
i
P
0
8:
if
Q
0
=
O
E
then
9:
Let (
h
0
,x
,h
0
,y
) be the implicit representation of
Q
0
10:
P
=
[
N/l
i
]
P
,
n
=
1,
T
=
P
=
(
x
T
,y
T
)
11:
g
x
T
or
h
0
,y
=
g
y
T
do
while
h
0
,x
=
Exhaustive search
12:
n
=
n
+
1,
T
=
T
+
P
0
13:
end while
14:
nl
j
−
1
u
i
=
u
i
+
15:
16:
end if
17:
end for
18:
end for
19:
Use Chinese remainder theorem to compute
u
u
i
(mod
l
e
i
)for1
≡
≤
i
≤
k
20:
Compute (
X,Y
)
=
[
u
]
P
and hence compute
a
21:
return
a
Remark 21.4.11
We have seen that reductions involving a Fixed-CDH oracle are less
efficient (i.e., require more oracle queries) than reductions using a CDH oracle. A solution
6
to this is to work with projective coordinates for elliptic curves. Line 12 of Algorithm
26
tests whether the point
Q
0
given in implicit representation is equal to the point (
x
T
,y
T
)
given in affine representation. When
Q
0
=
g
x
T
in line 12
(
x
0
:
y
0
:
z
0
) then the test
h
0
,x
=
is replaced with the comparison
=
g
z
0
x
T
.
g
x
0
6
This idea is briefly mentioned in Section 3 of [
362
], but was explored in detail by Bentahar [
39
].
