Cryptography Reference
In-Depth Information
Lemma 21.1.15
Fixed-Square-DH
≤
R
Fixed-Inverse-DH.
g
a
be the input Fixed-Square-DH instance and let
A
be a perfect oracle for
the Fixed-Inverse-DH problem. Call
A
(
gh
) to get
g
(1
+
a
)
−
1
Proof
Let
h
=
and call
A
(
gh
−
1
) to get
g
(1
−
a
)
−
1
.
Multiplying these outputs gives
g
(1
+
a
)
−
1
g
(1
−
a
)
−
1
g
2(1
−
a
2
)
−
1
.
w
=
=
Calling
A
(
w
2
−
1
(mod
r
)
)gives
g
1
−
a
2
from which we compute
g
a
2
as required.
We can now solve a non-fixed problem using an oracle for a fixed problem.
Lemma 21.1.16
Square-DH
≤
R
Fixed-CDH.
Proof
Let
g
∈
G
be fixed of prime order
r
and let
A
be a perfect Fixed-CDH oracle.
Let
g
1
,g
1
g
a
. We are required to compute
be the input Square-DH problem. Write
g
1
=
g
b
2
1
g
ab
2
.
Call
A
(
g
1
,g
1
) to compute
g
a
2
b
2
. Use the perfect Fixed-CDH oracle as in Lemma
21.1.14
to compute
g
a
−
1
. Then compute
A
(
g
a
2
b
2
,g
a
−
1
) to get
g
ab
2
.
=
Since CDH
≤
R
Square-DH we finally obtain the main result of this section.
Corollary 21.1.17
Fixed-CDH and CDH are equivalent.
Proof
We already showed Fixed-CDH
≤
R
CDH. Now, let
A
be a perfect Fixed-CDH oracle.
Lemma
21.1.16
together with Lemma
21.1.9
gives CDH
≤
R
Square-DH
≤
R
Fixed-CDH
as required.
Now suppose
A
only succeeds with noticeable probability
>
1
/
log(
r
)
c
for some fixed
c
. The reductions CDH
≤
R
Fixed-CDH require
O
(log(
r
)) oracle queries.
We perform self-correction (see Section
21.3
) to obtain an oracle
A
for Fixed-CDH that
is correct with probability 1
≤
R
Square-DH
1
/
(log(
r
)
c
) for some constant
c
; by Theorem
21.3.8
this
requires
O
(log(
r
)
c
log log(
r
)) oracle queries.
−
Exercise 21.1.18
It was assumed throughout this section that
G
has prime order
r
. Suppose
instead that
G
has order
r
1
r
2
where
r
1
and
r
2
are odd primes and that
g
is a generator for
G
. Which of the results in this section no longer necessarily hold? Is Fixed-CDH in
g
g
r
1
equivalent to Fixed-CDH in
?
We end with a variant of the DDH problem.
Exercise 21.1.19
Let
g
have prime order
r
and let
{
x
1
,...,x
n
}⊂Z
/r
Z
. For a subset
A
⊂{
1
,...,n
}
define
g
i
∈
A
x
i
.
g
A
=
The
group decision Diffie-Hellman problem
(GDDH) is: given
g
,
g
A
for all proper
subsets
A
g
c
(where
c
{
1
,...,n
}
, and
h
, to distinguish
h
=
∈ Z
/r
Z
is chosen uniformly
at random) from
g
x
1
x
2
···
x
n
. Show that GDDH
≡
DDH.