Cryptography Reference
In-Depth Information
In this topic the acronym CDH will always refer to the case where
g
is allowed to vary.
Hence, an algorithm for CDH will always take three inputs (formally we should also include
a description of the underlying group
G
, but we assume this is implicit in the specification
of
g
), while an algorithm for Fixed-CDH will always take two inputs.
It is trivial that Fixed-CDH
≤
R
CDH, but the reverse implication is less obvious; see
Corollary
21.1.17
below.
Analogously, given
g
∈
G
one can define Fixed-DLP (namely, given
h
to find
a
such that
g
ab
). Though Fixed-
DLP is equivalent to DLP (see Exercise
21.1.2
) it is not expected that DDH is equivalent
to Fixed-DDH (see Section 5.3.4 of [
495
]).
g
a
) and Fixed-DDH (given (
g
a
,g
b
,g
c
) determine whether
g
c
h
=
=
Exercise 21.1.2
Prove that Fixed-DLP is equivalent to DLP.
Exercise 21.1.3
Let
G
be a cyclic group of prime order
r
.Let
h
1
,h
2
,h
3
∈
G
such that
h
j
=
1for
j
=
1
,
2
,
3. Show there exists some
g
∈
G
such that (
g,h
1
,h
2
,h
3
)isaDiffie-
Hellman tuple.
We now introduce some other variants of CDH. These are interesting in their own right,
but are also discussed as they play a role in the proof of equivalence between CDH and
Fixed-CDH.
Definition 21.1.4
Let
G
be a group or algebric group quotient of prime order
r
.The
computational problem
Inverse-DH
is: given a pair
g,g
a
∈
G
−{
1
}
of elements of prime
order
r
in
G
to compute
g
a
−
1
(mod
r
)
. (Clearly, we must exclude the case
a
=
0fromtheset
of instances.)
Lemma 21.1.5
Inverse-DH
≤
R
CDH.
g
a
) be the given
Proof
Suppose
O
is a perfect oracle for solving CDH. Let (
g,g
1
=
Inverse-DH instance. Then
g
a
−
1
g
=
1
.
O
(
g
1
,g
a
−
1
1
,g
a
−
1
)gives
g
a
−
2
1
Calling
O
(
g
1
,g,g
)
=
. Finally
1
g
a
−
2
1
(
g
a
)
a
−
2
g
a
−
1
=
=
as required.
Definition 21.1.6
Let
G
be an AG or AGQ. The computational problem
Square-DH
is:
given (
g,g
a
) where
g
G
has prime order
r
to compute
g
a
2
.
∈
Exercise 21.1.7
Show that Square-DH
≤
R
CDH.
Lemma 21.1.8
Square-DH
≤
R
Inverse-DH.
g
a
) be given. If
Proof
Let
O
be a perfect oracle that solves Inverse-DH and let (
g,g
1
=
g
1
=
1 then return 1. Otherwise, we have
O
(
g
1
,g
a
−
1
g
a
2
.
g
1
=
(
g
a
)
a
O
(
g
1
,g
)
=
)
=
=
1
