Cryptography Reference
In-Depth Information
Hence, Square-DH
≤
R
Inverse-DH
≤
R
CDH. Finally, we show CDH
≤
R
Square-DH
and so all these problems are equivalent.
Lemma 21.1.9
Let G be a group of odd order. Then CDH
≤
R
Square-DH.
Proof
Let (
g,g
a
,g
b
) be a CDH instance. Let
O
be a perfect oracle for Square-DH. Call
O
(
g,g
a
) to get
g
1
=
g
a
2
,
O
(
g,g
b
) to get
g
2
=
g
b
2
g
a
2
+
2
ab
+
b
2
and
O
(
g,g
a
g
b
) to get
g
3
=
.
Now compute
(
g
3
/
(
g
1
g
2
))
2
−
1
(mod
r
)
,
which is
g
ab
as required.
Exercise 21.1.10
Let
G
be a group of prime order
r
. Show that Inverse-DH and Square-
DH are random self-reducible. Hence, give a self-corrector for Square-DH. Finally, show
that Lemma
21.1.9
holds for non-perfect oracles. (Note that it seems to be hard to give a
self-corrector for Inverse-DH directly, though one can do this via Lemma
21.1.8
.)
Note that the proofs of Lemmas
21.1.5
and
21.1.8
require oracle queries where the first
group element in the input is not
g
. Hence, these proofs do not apply to variants of these
problems where
g
is fixed. We now define the analogous problems for fixed
g
and give
reductions between them.
Definition 21.1.11
Let
g
have prime order
r
and let
G
=
g
. The computational problem
1 to compute
g
a
−
1
(mod
r
)
. Similarly, the computational
problem
Fixed-Square-DH
is: given
g
a
to compute
g
a
2
.
Fixed-Inverse-DH
is: given
g
a
=
Exercise 21.1.12
Show that Fixed-Inverse-DH and Fixed-Square-DH are random self-
reducible.
g
a
and let
Lemma 21.1.13
Let g
∈
G. Let A be a perfect Fixed-CDH oracle. Let h
=
. Then one can compute g
a
n
(mod
r
)
using
n
∈ N
≤
2log
2
(
n
)
queries to A.
g
a
i
(mod
r
)
so that
h
1
=
Proof
Assume
A
is a perfect Fixed-CDH oracle. Define
h
i
=
h
.One
has
h
2
i
=
A
(
h
i
,h
i
) and
h
i
+
1
=
A
(
h
i
,h
). Hence, one can compute
h
n
by performing the
standard square-and-multiply algorithm for efficient exponentiation.
Note that the number of oracle queries in Lemma
21.1.13
can be reduced by using
window methods or addition chains.
Lemma 21.1.14
Fixed-Inverse-DH
≤
R
Fixed-CDH.
G
.Let
O
be a perfect Fixed-CDH oracle. Let
g
a
be the given Fixed-Inverse-
DH instance. Our task is to compute
g
a
−
1
. The trick is to note that
a
−
1
Proof
Fix
g
∈
a
r
−
2
(mod
r
).
Hence, one computes
g
a
r
−
2
using Lemma
21.1.13
. The case of non-perfect oracles requires
some care, although at least one can check the result using
O
since one should have
O
(
g
a
,g
a
−
1
)
=
=
g
.
