Cryptography Reference
In-Depth Information
Proof
The idea is to choose uniformly at random 0
≤
α<r
and set
X
=
a
+
α
. An implicit
hg
α
using
O
(log(
r
)) group operations. If we
store
α
then, given
X
, we can compute
a
. Hence, the extra data is
α
.
Given the implicit representation for
X
one determines an implicit representation for
β
representation of
X
can be computed as
h
1
=
=
B
using two oracle queries. Given
g
β
, one can compute (here (
r
)
X
3
+
AX
+
∈{−
1
,
1
}
is the Legendre symbol)
g
(
r
)
g
β
(
r
−
1)
/
2
h
2
=
=
(21.8)
using
O
(log(
r
)) oracle queries. If
h
2
=
g
then
β
is a square and so
X
is an
x
-coordinate of
a point of
E
(
F
r
).
Since there are at least (
r
2
√
r
)
/
2 possible
x
-coordinates of points in
E
(
−
F
r
), it follows
that if one chooses
X
uniformly at random in
F
r
then the expected number of trials until
X
is the
x
-coordinate of a point in
E
(
F
r
) is approximately two.
Onc
e
β
is a square modulo
r
then one can compute an implicit representation for
=
√
β
(mod
r
) using the Tonelli-Shanks algorithm with implicit representations. We use
the notation of Algorithm
3
. The computation of the non-residue
n
is expected to require
O
(log(
r
)) operations in
Y
F
r
and can be done explicitly. The computation of the terms
w
and
b
requires
O
(log(
r
)) oracle queries, some of which can be avoided by storing intermediate
values from the computation in equation (
21.8
). The computation of
i
using a Pohlig-
Hellman-style algorithm is done as follows. First compute the sequence
b,b
2
,...,b
2
e
−
1
using
O
(log(
r
)) oracle queries and the sequence
y,y
2
,...,y
2
e
−
1
using
O
(log(
r
)) group
operations. With a further
O
(log(
r
)) group operations, one can determine the bits of
i
.
Theorem 21.4.10
Let B
∈ N
. Let g
∈
G have order r. Let E be an elliptic curve over
F
r
such that E
(
F
r
)
is known and is
B-smooth. Given a perfect Fixed-CDH oracle with respect to g, one can solve the DLP in
F
r
)
is a cyclic group. Suppose that the order of E
(
using expected O
(log(
r
)
2
log(log(
r
)))
oracle queries.
5
Indeed, there are two variants of the reduction, one using exhaustive search and one
using the baby-step-giant-step algorithm. One can also consider the case of a perfect
CDH oracle. The following table gives the full expected complexities (where the constant
implicit in the O
(
g
·
)
is independent of B). We use the abbreviation l
(
x
)
=
log(
x
)
so that
l
(
l
(
r
))
=
log(log(
r
))
.
Oracle
Reduction
Oracle queries
Group operations
F
r
operations
O
(
l
(
r
)
2
l
(
l
(
r
)))
O
(
Bl
(
r
)
2
/l
(
B
))
O
(
B
l
(
r
)
2
/l
(
B
))
Fixed-CDH
PH only
PH+BSGS O
(
√
Bl
(
r
)
2
/l
(
B
)
+
l
(
r
)
2
l
(
l
(
r
)))
O
(
√
Bl
(
r
)
2
/l
(
B
))
O
(
√
Bl
(
r
)
2
/l
(
B
))
Fixed-CDH
O
(
Bl
(
r
)
2
/l
(
B
))
O
(
B
l
(
r
)
2
/l
(
B
))
CDH
PH only
O
(
l
(
r
)
l
(
l
(
r
)))
PH+BSGS O
(
√
Bl
(
r
)
/l
(
B
)
l
(
r
)
l
(
l
(
r
)))
O
(
√
Bl
(
r
)
2
/l
(
B
))
O
(
√
Bl
(
r
)
2
/l
(
B
))
CDH
+
=
i
=
1
l
e
i
.
g
a
). Write
N
Proof
Let the discrete logarithm instance be (
g,h
=
=
#
E
(
F
r
)
We assume that affine coordinates are used for arithmetic in
E
(
F
r
). Let
P
be a generator
of
E
(
F
r
).
5
This is improved to
O
(log(
r
) log log(
r
)) in Remark
21.4.11
.
