Cryptography Reference
In-Depth Information
notation is usual for a D-H exchange. In addition, additive notation can also be used,
where P is the generator of the additive group.
In many situations, two related problems exist: a computational problem and a deci-
sion problem. Solving a computational problem is comparable to the process of calculat-
ing a correct answer; if the computational problem is hard, then calculating the correct
answer is hard. A decision problem involves the decision of determining YES or NO as
an answer to a problem. Here, if we want the correct answer to be difficult to guess or
even determine part of the answer, and if the relevant decision problem is hard, then
determining the correct answer is equally hard.
Let us look into computational and decision problems in the context of the Diffie-
Hellman protocol.
4.3.1.1 Computational Diffi e-Hellman Problem
The computational Diffie-Hellman protocol (CDHP) replicates the situation in D-H
exchange. Given g , = r
A
rr
AB Zg . Note that the
CDHP can also be represented using additive notation: Given P , r A P , r B P , calculate
r A r B P . For the sake of simplicity and maintaining regularity, let us use the multiplica-
tive notation instead of additive notation. An adversary could take the obvious way to
determine r B by calculating the discrete logarithm of
, and = r
B
, calculate = AB
t
g
t
g
r
g
. Then he would calculate Z AB
as shown below:
() r
A
=
t
Z
(4.1)
AB
Hence, finding the discrete logarithm of either of the exchanged values would result
in the discovery of the shared secret. However, solving the CDHP is no harder than
solving the discrete logarithm problem. Despite considerable research in the area of
computational complexity theory, the question of whether the D-H problem is as hard
as the discrete logarithm problem still persists (Maurer 1994).
Conversely, given g , t A , and t B , there is no guarantee that an adversary cannot deter-
mine some part of the shared secret ( Z AB ). (For instance, an adversary could determine
several bits of Z AB but not all of the them.) Hence, to avoid such prediction from the
adversary, another problem should be hard: the decision D-H problem.
4.3.1.2 Decision Diffi e-Hellman Problem
The decision Diffie-Hellman problem (DDH) states that it is a hard problem to distin-
guish between a genuine D-H tuple ( t A , t B , Z AB ) and a random tuple ( ¢ ¢ ¢
t
, ,
AB
t
Z ),
B
where ¢
, ¢
¢¢
= AB
zrr are chosen randomly. One obvious but rudimentary
way of solving this problem is to determine r B through the CDHP and then calculate
==
r
r
, and
r
r
r
¢
=
ZZ . Hence solving the DDHP problem
is no more difficult than solving the CDHP. If the DDHP is as hard as the CDHP, then
it is equally hard to distinguish between Z AB and any other element in the group G .
()
t
( )
g
Z
and compare
B
A
B
A
AB
AB
AB
Search WWH ::




Custom Search