Cryptography Reference
In-Depth Information
Exercise 21.3.9
Show that if the conjecture of Stolarsky (see Section 2.8) is true then one
can compute
g
a
n
in log
2
(
n
)
+
log
2
(log
2
(
n
)) Fixed-CDH oracle queries.
21.4 The den Boer and Maurer reductions
The goal of this section is to discuss reductions from DLP to CDH or Fixed-CDH in groups
of prime order
r
. Despite having proved that Fixed-CDH and CDH are equivalent, we
prefer to treat them separately in this section. The first such reduction (assuming a perfect
Fixed-CDH oracle) was given by den Boer [
156
] in 1988. Essentially, den Boer's method
involves solving a DLP in
F
r
, and so it requires
r
1 to be sufficiently smooth. Hence,
there is no hope of this approach giving an equivalence between Fixed-CDH and DLP for
all groups of prime order.
The idea was generalised by Maurer [
362
] in 1994, by replacing the multiplicative
group
−
F
r
by an elliptic curve group
E
(
F
r
). Maurer and Wolf [
365
,
366
,
368
] extended the
result to non-perfect oracles. If #
E
(
F
r
) is sufficiently smooth then the reduction is efficient.
Unfortunately, there is no known algorithm to efficiently generate such smooth elliptic
curves. Hence, Maurer's result also does not prove equivalence between Fixed-CDH and
DLP for all groups. A subexponential-time reduction that conjecturally applies to all groups
was given by Boneh and Lipton [
78
]. An exponential-time reduction (but still faster than
known algorithms to solve DLP) that applies to all groups was given by Muzereau, Smart
and Vercauteren [
402
] and Bentahar [
39
,
40
].
21.4.1 Implicit representations
Definition 21.4.1
Let
G
be a group and let
g
∈
G
have prime order
r
.For
a
∈ Z
/r
Z
we
g
a
an
implicit representation
of
a
.
call
h
=
In this section we call the usual representation of
a
∈ Z
/r
Z
the
explicit representation
of
a
.
Lemma 21.4.2
There is an efficient (i.e., computable in polynomial-time) mapping from
Z
Z
given in implicit representation. If h
1
is an implicit representation of a and h
2
is an implicit
representation of b then h
1
h
2
is an implicit representation of a
/r
Z
to the implicit representations of
Z
/r
Z
. One can test equality of elements in
Z
/r
b and h
−
1
1
+
is an implicit
representation of
−
a.
In other words, we can compute in the additive group
Z
/r
Z
using implicit representa-
tions.
Lemma 21.4.3
If h is an implicit representation of a and b
∈ Z
/r
Z
is known explicitly,
then h
b
is an implicit representation of ab.
Let O be a perfect Fixed-CDH oracle with respect to g. Suppose h
1
is an implicit
representation of a and h
2
is an implicit representation of b. Then h
=
O
(
h
1
,h
2
)
is an
implicit representation of ab.
