Cryptography Reference
In-Depth Information
In other words, if one can solve Fixed-CDH then one can compute multiplication modulo
r
using implicit representatives.
Exercise 21.4.4
Prove Lemmas
21.4.2
and
21.4.3
.
Lemma 21.4.5
Let g have order r. Let h
1
be an implicit representation of a such that
h
1
=
1
(in other words, a
≡
0(mod
r
)
).
1. Given a perfect CDHoracle, one can compute an implicit representation fora
−
1
(mod
r
)
using one oracle query.
2. Given a perfect Fixed-CDH oracle with respect to g, one can compute an implicit
representation for a
−
1
(mod
r
)
using
≤
2log
2
(
r
)
oracle queries.
g
a
−
1
Proof
Given a perfect CDH oracle
A
one calls
A
(
g
a
,g,g
)
=
(mod
r
)
. Given a perfect
Fixed-CDH oracle one computes
g
a
r
−
2
(mod
r
)
as was done in Lemma
21.1.14
.
Z
=
F
r
, given a perfect CDH or Fixed-CDH oracle then one
can perform all field operations in
To summarise, since
Z
/r
F
r
using implicit representations. Boneh and Lipton [
78
]
call the set of implicit representations for
Z
/r
Z
a
black box field
.
21.4.2 The den Boer reduction
We now present the
den Boer reduction
[
156
], which applies when
r
1 is smooth. The
crucial idea is that the Pohlig-Hellman and baby-step-giant-step methods only require the
ability to add, multiply and compare group elements. Hence, if a perfect CDH oracle is
given then these algorithms can be performed using implicit representations.
−
∈
Theorem 21.4.6
Let g
G have prime order r. Suppose l is the largest prime factor of
−
r
1
. Let A be a perfect oracle for the Fixed-CDH problem with respect to g
.
Then one
can solve the DLP in
usingO
(log(
r
) log(log(
r
)))
oracle queries, O
(log(
r
)(
√
l/
log(
l
)
g
+
F
r
and O
(
√
l
log(
r
)
2
/
log(
l
))
operations inG (where the constant
log(
r
))
multiplications in
implicit in the O
(
·
)
does not depend on l).
g
a
.If
h
Proof
Let the challenge DLP instance be
g,h
=
=
1 then return
a
=
0. Hence, we
∈ F
r
in
O
(log(
r
) log(log(
r
)))
now assume 1
≤
a<r
. We can compute a primitive root
γ
operations in
F
r
(see Section
2.15
). The (unknown) logarithm of
h
satisfies
γ
u
(mod
r
)
a
≡
(21.5)
for some integer
u
. To compute
a
it is sufficient to compute
u
.
3
The idea is to solve the
DLP in equation (
21.5
) using the implicit representation of
a
. Since
r
1 is assumed to
be smooth then we can use the Pohlig-Hellman (PH) method, followed by the baby-step-
giant-step (BSGS) method in each subgroup. We briefly sketch the details.
−
3
It may seem crazy to try to work out
u
without knowing
a
, but it works!
