Cryptography Reference
In-Depth Information
21.3 Random self-reducibility and self-correction of CDH
We defined random self-reducibility in Section
2.1.4
. Lemma
2.1.19
showed that the DLP
in a group
G
of prime order
r
is random self-reducible. Lemma
2.1.20
showed how to
obtain an algorithm with arbitrarily high success probability for the DLP from an algorithm
with noticeable success probability.
Lemma 21.3.1
Let g have order r and let G
=
g
. Then CDH in G is random self-
reducible.
G
2
(
g,g
a
,g
b
)
Proof
Let
X
=
(
G
−{
1
}
)
×
Let (
g,h
1
,h
2
)
=
∈
X
be the CDH instance.
≤
≤
Choose
uniformly
at
random
1
u<r
and
0
v,w <r
and
consider
the
triple
(
g
u
,h
1
g
uv
,h
2
g
uw
)
=
(
g
u
,
(
g
u
)
a
+
v
,
(
g
u
)
b
+
w
)
∈
X
X
arises from
exactly one triple (
u,v,w
). Hence, the new triples are uniformly distributed in
. Then every triple in
X
.If
(
g
u
)
(
a
+
v
)(
b
+
w
)
is the solution to the new CDH instance then the solution to the original
CDH instance is
Z
=
Z
u
−
1
(mod
r
)
h
−
1
h
−
2
g
−
vw
.
Exercise 21.3.2
Show that Fixed-CDH is random self-reducible in a group of prime
order
r
.
The following problem
1
is another cousin of the computational Diffie-Hellman problem.
It arises in some cryptographic protocols.
g
a
for some 1
Definition 21.3.3
Fix
g
of prime order
r
and
h
=
≤
a<r
.The
static
to compute
h
1
.
Exercise 21.3.4
Show that the static Diffie-Hellman problem is random self-reducible.
Diffie-Hellman problem
(
Static-DH
)is:given
h
1
∈
g
One can also consider the decision version of static Diffie-Hellman.
g
a
for some 1
Definition 21.3.5
Fix
g
of prime order
r
and
h
=
≤
a<r
.The
decision
static Diffie-Hellman problem
(
DStatic-DH
)is:given
h
1
,h
2
∈
g
to determine whether
h
1
.
h
2
=
We now show that DStatic-DH is random-self-reducible. This is a useful preliminary to
showing how to deal with DDH.
Lemma 21.3.6
Fix g of prime order r and h
=
g
a
for some
1
≤
a<r. Then the decision
static Diffie-Hellman problem is random self-reducible.
Proof
Write
G
=
g
. Choose 1
≤
w<r
and 0
≤
x<r
uniformly at random. Given
(
h
1
g
x
,h
2
h
x
). We must show that if (
h
1
,h
2
) is (respectively,
is not) a valid Static-DH pair then (
Z
1
,Z
2
) is uniformly distributed over the set of all valid
(respectively, invalid) Static-DH pairs.
(
h
1
,h
2
) compute (
Z
1
,Z
2
)
=
1
The Static-DH problem seems to have been first studied by Brown and Gallant [
104
].
