Cryptography Reference
In-Depth Information
(
)
=
∈
of order
t
with len
t
n
and a generator
g
G
, by considering the following
experiment:
Definition 7.4
The
DDH experiment
DDH
A,
Gen
G
(
n
)
is the following:
Gen
G
is run on input 1
n
1.
to obtain
(
G
,
g
)
where
G
is a cyclic group of order
t
,
with len
(
t
)
=
n
and
G
=
g
.
2. A random bit
b
←{
0
,
1
}
and random elements
x
,
y
← Z
t
are chosen and an
g
xy
element
h
∈
G
is defined by
h
:=
if
b
=
0 and
h
←
G
(
h
is a random
element of
G
)if
b
=
1.
and outputs a bit
b
.
4. The output of the experiment is defined to be 1 if
b
g
x
g
y
3.
A
is given
(
G
,
g
,
,
,
h
)
=
b
and 0 otherwise. If
DDH
A
,
Gen
G
(
n
)
=
1 then we say that
A
succeeded.
This leads to the following hardness definition:
Definition 7.5
We say that
the DDH problem is hard relative to
Gen
G
if, for every
PPT algorithm
A
, there exists a negligible function
negl
such that
Pr
(
DDH
A,
Gen
G
(
n
)
=
1
)
≤
1
/
2
+
negl
(
n
).
In Definition 7.2, security of a key agreement protocol was defined by requiring
that an eavesdropper has only negligible probability of distinguishing the key
k
obtained from the protocol from a random string of the same length. This definition
can be modified in the setting of the DH protocol by requiring only that the key output
after the parties run the protocol (which is an element of the cyclic group
G
used
in the DH protocol) be indistinguishable to an eavesdropper from a random element
from
G
(except with negligible probability). Then the following is easily proved and
we leave the details as an exercise:
Exercise 7.2
Prove that if the DDH problem is hard relative to
Gen
G
, then the DH
protocol is secure in the sense that the shared key obtained is indistinguishable from
a random element of
G
.
Example 7.1
We show that the DDH problem may be easy even if the CDH prob-
lem is supposed to be hard, showing that the DH protocol may be insecure even if
recovering the key is hard. Let
p
be a prime number,
G
= Z
p
and
g
a primitive root
modulo
p
. Then the DDH problem is not hard (more precisely, we can say that the
DDH problem is not hard relative to the generating algorithm that, on input 1
n
, picks
a random
n
-bit prime and outputs the pair
(
Z
p
,
, where
g
is a primitive root modulo
p
). Indeed, the generator
g
is, as we have seen, a quadratic non-residue, so that its
g
)
Legendre symbol is
p
g
log
g
v
we can
efficiently compute
p
and
p
using Algorithm 2.7. Then we know that
p
g
log
g
u
and
v
=−
1. Moreover, given
u
=
=
=
g
log
g
u
p
p
log
g
u
log
g
u
and, similarly,
p
log
g
v
. This gives the
parity (or, equivalently, the least significant bit) of both log
g
u
and log
g
v
and hence the
=
=
(
−
1
)
=
(
−
1
)
