Cryptography Reference
In-Depth Information
(
)(
)
parity of their product
log
g
u
log
g
v
allowing the easy computation of the Legen-
g
(
log
g
u
)(
log
g
v
)
p
dre symbol
DH
g
(
u
,
v
)
p
)
(
log
g
u
)(
log
g
v
)
. The knowledge of
=
=
(
−
1
its Legendre symbol serves to distinguish DH
g
(
u
,
v
)
from a random element of
G
, computes
DH
g
(
u
,
v
)
p
p
p
because the adversary, once given
(
G
,
g
,
u
,
v
,
h
)
=
and
p
. If both Legendre symbols have the same value, the adversary guesses
that
h
, otherwise it guesses that
h
is random. Its success probabil-
ity is, by Proposition 2.1 (i), Pr
=
DH
g
(
u
,
v
)
(
DDH
A,
Gen
G
(
n
)
=
1
)
=
Pr
(
DDH
A,
Gen
G
(
n
)
=
1
1
2
1
1
1
2
3
4
1
|
h
is random
)
·
2
+
Pr
(
DDH
A,
Gen
G
(
n
)
=
1
|
h
=
DH
g
(
u
,
v
))
·
=
2
·
2
+
1
·
=
and hence its advantage is
4
, which is non-negligible.
Despite the DDH problem being easy relative to the group generating algorithm
considered here, both the discrete logarithm and the CDH problems are thought to
be hard for the groups
DL problem in these groups are subexponential). Thus, as stated above, the hardness
of the CDH problem is insufficient to guarantee the security of the DH protocol.
The DL problem and its derivatives, the CDH and DDH problems, are especially
useful for cryptography because of a characteristic that we now briefly describe. First
we give an informal definition:
Definition 7.6
A computational problem is
random self-reducible
if there exists a
polynomial-time algorithm that transforms any given instance of the problem into a
uniformly distributed random instance such that the solution of the original instance
can be obtained in polynomial time from the solution of the new instance.
Random self-reducibility means that the existence of an efficient algorithm to
solve the problem in the average case implies the existence of an efficient algorithm
to solve it in theworst case. In other words, if the problem is hard in theworst case then
it is also hard on average, a feature which makes these problems especially useful for
cryptography. The lack of this property is what makes, for example, the subset sum
problem (given a set of positive integers and a target integer
s
, is there a subset whose
sum is precisely equal to
s
?) inadequate for cryptographic use. This problem is
-
complete and hence it is thought to be hard in the worst case but there are efficient
algorithms to solve many instances of the problem. Thus all cryptographic schemes
based on this problem, such as the original Merkle-Hellman knapsack cryptosystem,
were eventually broken (a survey of these schemes is [150]).
NP
Exercise 7.3
Prove that the DL problem on a finite cyclic group
G
is random self-
reducible. (Hint: given an element
a
∈
G
=
g
whose logarithm to the base
g
is to
, and consider the element
ag
r
be computed, choose
r
← Z
t
, where
t
=|
G
|
∈
G
.)
The CDH problem and the DDH problem are both well suited for cryptographic
use in the sense just mentioned because both can be shown to be random self-
reducible. For example, in the case of the former problem we have:
