Cryptography Reference
In-Depth Information
h
1
First, we deal with the case of valid Static-DH pairs. It is easy to check that if
h
2
=
Z
1
Z
1
then
Z
2
=
. Furthermore, for any pair
Z
1
,Z
2
∈
G
such that
Z
2
=
one can find
h
1
g
x
.
exactly (
r
−
1) pairs (
w,x
) such that
Z
1
=
h
1
then write
h
1
=
g
b
and
h
2
=
g
c
with
c
On the other hand, if
h
2
=
≡
ab
(mod
r
). For
(
g
y
,g
z
)
G
2
any pair (
Z
1
,Z
2
)
ay
(mod
r
) we must show that (
Z
1
,Z
2
)
can arise from precisely one choice (
w,x
) above. Indeed
y
z
=
∈
such that
z
≡
b
1
ca
w
x
=
and, since the matrix has determinant
ab
−
c
≡
0(mod
r
) one can show that there is a
unique solution for (
w,x
) and that
w
≡
0(mod
r
).
We now tackle the general case of decision Diffie-Hellman.
=
Lemma 21.3.7
Let g have prime order r and let G
g
. Then DDH in G is random
self-reducible.
Proof
Choose 1
=
(
g,g
a
,g
b
,g
c
) define the new tuple (
g
u
,h
1
g
uv
,h
u
2
g
ux
,h
u
3
h
u
1
h
v
2
g
uvx
). One can verify
that the new tuple is a valid Diffie-Hellman tuple if and only if the original input is a valid
Diffie-Hellman tuple (i.e.,
c
≤
u,w < r
and 0
≤
v,x <r
uniformly at random. Given (
g,h
1
,h
2
,h
3
)
ab
). If the original tuple is a valid Diffie-Hellman tuple
then the new tuple is uniformly distributed among all Diffie-Hellman tuples. Finally, we
show that if the original tuple is not a valid Diffie-Hellman tuple then the new tuple is
uniformly distributed among the set of all invalid Diffie-Hellman tuples. To see this, think
of (
h
2
,h
3
) as a DStatic-DH instance with respect to the pair (
g,h
1
). Since (
g
u
,h
1
g
uv
)is
chosen uniformly at random from (
G
=
G
we have a uniformly random DStatic-
DH instance with respect to a uniformly random static pair. The result then follows from
Lemma
21.3.6
.
−{
1
}
)
×
It is easy to turn a DLP oracle that succeeds with noticeable probability
into one that
succeeds with probability arbitrarily close to 1 since one can check whether a solution to
the DLP is correct. It is less easy to amplify the success probability for a non-perfect CDH
oracle.
A natural (but flawed) approach is just to run the CDH oracle on random self-reduced
instances of CDH until the same value appears twice. We now explain why this approach
will not work in general. Consider a Fixed-CDH oracle that, on input (
g
a
,g
b
), returns
g
ab
+
ξ
where
ξ
1
/
log(
r
) and 1
/
log(
r
). Calling the oracle on
instances arising from the random self-reduction of Exercise
21.3.2
one gets a sequence of
values
g
ab
+
ξ
. Eventually, the correct value
g
ab
will occur twice, but it is quite likely that
some other value will occur twice before that time.
We present Shoup's self-corrector for CDH or Fixed-CDH from [
494
].
2
Also see Cash,
Kiltz and Shoup [
112
].
∈ Z
is uniformly chosen between
−
2
Maurer and Wolf [
365
] were the first to give a self-corrector for CDH but Shoup's method is more efficient.
