Singapore Management University

Institutional Knowledge at Singapore Management University

Research Collection School Of Computing and School of Computing and Information Systems
Information Systems

10-2003

Variations of Diffie-Hellman problem

Feng BAO
Institute for Infocomm Research

Robert H. DENG
Singapore Management University, [email protected]

Huafei ZHU
Institute for Infocomm Research

Follow this and additional works at: https://ink.library.smu.edu.sg/sis_research

Part of the Information Security Commons

Citation
BAO, Feng; DENG, Robert H.; and ZHU, Huafei. Variations of Diffie-Hellman problem. (2003). Information
and Communications Security: 5th International Conference, ICICS 2003, Huhehaote, China, October
10-13. 2836, 301-312.
Available at: https://ink.library.smu.edu.sg/sis_research/1083

This Conference Proceeding Article is brought to you for free and open access by the School of Computing and
Information Systems at Institutional Knowledge at Singapore Management University. It has been accepted for
inclusion in Research Collection School Of Computing and Information Systems by an authorized administrator of
Institutional Knowledge at Singapore Management University. For more information, please email
[email protected].
 Variations of Diffie-Hellman Problem

Feng Bao, Robert H. Deng, and HuaFei Zhu

Infocomm Security Department, Institute for Infocomm Research.

21 Heng Mui Keng Terrace, Singapore 119613.
{baofeng, deng, huafei}@i2r.a-star.edu.sg

Abstract. This paper studies various computational and decisional

Diffie-Hellman problems by providing reductions among them in
the high granularity setting. We show that all three variations of
computational Diffie-Hellman problem: square Diffie-Hellman problem,
inverse Diffie-Hellman problem and divisible Diffie-Hellman problem, are
equivalent with optimal reduction. Also, we are considering variations of
the decisional Diffie-Hellman problem in single sample and polynomial
samples settings, and we are able to show that all variations are
equivalent except for the argument DDH ⇐ SDDH. We are not able to
prove or disprove this statement, thus leave an interesting open problem.

Keywords: Diffie-Hellman problem, Square Diffie-Hellman problem, In-

verse Diffie-Hellman problem, Divisible Diffie-Hellman problem

1 Introduction
The Diffie-Hellman problem [9] is a golden mine for cryptographic purposes and
is more and more studied. This problem is closely related to the difficult of
computing the discrete logarithm problem over a cyclic group[11]. There are
several works to study classical and variable Diffie-Hellman problems([13], [14],
[21], [18]) in the generic model. For the decisional Diffie-Hellman problem set-
ting, there is alternative, yet equivalent notation, called matching Diffie-Hellman
problem, have been studied by Handschuh, Tsiounis and Yung [10]. These vari-
ations are by now the security of many protocols relying on ([1], [2], [5], [6],[8]).
Tatsuaki Okamoto and David Pointcheval[16] introduce a new notion called the
Gap-Problems, which can be considered as a dual to the class of the decision
problems. While Sadeghi and Steinerhere [19] rigourously consider a set of Diffie-
Hellman related problems by identifying a parameter termed granularity, which
describes the underlying probabilistic space in an assumption.
This paper studies various computational and decisional problems related to
the Diffie-Hellman problems by providing reductions among them in the high
granularity setting, i.e., we consider the variations of Diffie-Hellman problem
defined over some cyclic group with explicit group structure. More precisely,
we are interested in studying relationship among variations of Diffie-Hellman
problem including computational and decisional cases in single and polynomial
setting and try to obtain reductions that are efficient so that an advantage
against one of these problems can be reached against the other one.

S. Qing, D. Gollmann, and J. Zhou (Eds.): ICICS 2003, LNCS 2836, pp. 301–312, 2003.


c Springer-Verlag Berlin Heidelberg 2003
302 F. Bao, R.H. Deng, and H. Zhu

The basic tools for relating the complexities of various problems are polyno-
mial reductions and transformations. We say that a problem A reduces in poly-
nomial time to another problem B, denoted by A ⇐ B, if and only if there is an
algorithm for A which uses a subroutine for B, and each call to the subroutine
for B counts as a single step, and the algorithm for A runs in polynomial-time.
The latter implies that the subroutine for B can be called at most a polynomially
bounded number of times. The practical implication comes from the following
proposition: If A polynomially reduces to B and there is a polynomial time al-
gorithm for B, then there is a polynomial time algorithm for A also. Specially,
for considering variation of Diffie-Hellman problem in polynomial time sampling
case, we need to define the conception of efficient constructing algorithm to meet
the requirement of the standard hybrid technique.
Our contributions: In this report, we are considering useful variations of
Diffie-Hellman problem: square computational(and decisional) Diffie-Hellman
problem, inverse computational(and decisional) Diffie-Hellman problem and di-
visible computational(and decisional) Diffie-Hellman problem. We are able to
show that all variations of computational Diffie-Hellman problem are equivalent
to the classic computational Diffie-Hellman problem if the order of a underlying
cyclic group is a large prime. We remark that our reduction is efficient, that is
an advantage against one of these problems can be reached against another one.
Also, we are considering variations of the decisional Diffie-Hellman problem in
single sample and polynomial samples settings, and we are able to show that all
variations are equivalent except for the argument DDH ⇐ SDDH. We are not
able to prove or disprove this statement, thus leave an interesting open problem
in this report.

2 Variations of Computational Diffie-Hellman Problem

Let p be a large prime number such that the discrete logarithm problem defined
in Zp∗ is hard. Let G ∈ Zp∗ be a cyclic group of prime order q and g is assumed
to be a generator of G. Though out this paper, we assume that G is prime
order, and security parameters p, q are defined as the fixed form p=2q + 1 and
ord(g)=q. A remarkable computational problem has been defined on this kind of
set by Diffie and Hellman [9]. More precisely, Diffie-Hellman assumption (CDH
assumption) is referred to as the following statement:
Computational Diffie-Hellman problem (CDH): On input g, g x , g y , comput-
ing g xy .
An algorithm that solves the computational Diffie-Hellman problem is a
probabilistic polynomial time Turing machine, on input g, g x , g y , outputs
g xy with non-negligible probability. Computational Diffie-Hellman assumption
means that there is no such a probabilistic polynomial time Turing machine.
This assumption is believed to be true for many cyclic groups, such as the prime
sub-group of the multiplicative group of finite fields.
 Variations of Diffie-Hellman Problem 303

2.1 Square Computational Diffie-Hellman Assumption

Let G ∈ Zp∗ defined as above, we are interested in the square computational
Diffie-Hellman problem, which has been studied at by a set of researchers already
(see [3], [12],[13], [14] for more details). We remark that the reduction presented
in this section emphasizes its efficient and optimal characteristic. Therefore our
work is non-trivial indeed.
Square computational Diffie-Hellman problem (SCDH): On input g, g x , com-
2
puting g x .
An algorithm that solves the square computational Diffie-Hellman problem
2
is a probabilistic polynomial time Turing machine, on input g, g x , outputs g x
with non-negligible probability. Square computational Diffie-Hellman assump-
tion means that there is no such a probabilistic polynomial time Turing ma-
chine. Fortunately, we are able to argue that the SCDH assumption and CDH
assumption are equivalent.
SCDH ⇐ CDH
Proof: Given an oracle A1 , on input g,g x , g y , outputs g xy , we want to show
2
that there exists an algorithm A2 , on input g x , outputs g x . Given a random
value u := g r , we choose t1 , t2 ∈ Zq at random, and compute u1 = ut1 = g rt1 ,
2
and u2 = ut2 = g rt2 . Therefore we are able to compute v = A1 (u1 , u2 )= g r t1 t2
2
with non-negligible probability. It follows that g r can be computed from v, t1 , t2
immediately with same advantage.
CDH ⇐ SCDH
2
Proof: Given an oracle A2 , on input g, g x , outputs g x , we want to show that
there exists an algorithm A1 , on input g, g x , g y , outputs g xy . Now given g x , we
2
choose s1 , s2 , t1 , t2 ∈ Zq at random and compute v1 := A2 (g x s1 ) =g (xs1 ) , v2 :=
2 2
A2 ((g y )s2 ) =g (ys2 ) . Finally, we compute v3 := A2 (g xs1 t1 +ys2 t2 ) = g (xs1 t1 +ys2 t2 ) .
xy
Since s1 , s2 , t1 , t2 are known already, it follows that g can be computed from
v1 , v2 , v3 , s1 , s2 , t1 , t2 immediately with same advantage.

2.2 Inverse Computational Diffie-Hellman Assumption

We are also interested in such a computational variation of computational Diffie-
Hellman problem, called inverse computational Diffie-Hellman assumption (In-
vCDH assumption) first studied at [17].
Inverse computational Diffie-Hellman problem (InvCDH): On input g, g x ,
−1
outputs g x .
An algorithm that solves the inverse computational Diffie-Hellman problem
−1
is a probabilistic polynomial time Turing machine, on input g, g x , outputs g x
with non-negligible probability. Inverse computational Diffie-Hellman assump-
tion means that there is no such a probabilistic polynomial time Turing machine.
Fortunately, we are able to argue that the SCDH assumption and InvCDH as-
sumption are also equivalent.
InvCDH ⇐ SCDH
2
Proof: Given an oracle A2 , on input g, g x , outputs g x , we want to show that
−1
there exists an algorithm A3 , on input g x , outputs g x . Given a random value
304 F. Bao, R.H. Deng, and H. Zhu

g r , we set h1 ← g r and h2 ← g. Finally, we view (h1 , h2 ) as an input to the

−2 −1
oracle A2 to obtain A2 (h1 , h2 ) = g r r . It follows that g r can be computed
from A2 immediately with same advantage.
SCDH ⇐ InvCDH
−1
Proof: Given an oracle A3 , on input g, g x , outputs g x , we want to show
2
that there exists an algorithm A2 , on input g, g , outputs g x . Now given g, g r ,
x

we set h1 ← g r and h2 ← g. Finally, we view (h1 , h2 ) as an input to the oracle

−1 2
A3 to obtain A3 (h1 , h2 )= A3 (g r , (g r )r ). It follows that g r can be computed
from A3 with the same advantage.

2.3 Divisible Computation Diifie-Hellman Assumption

Yet, there is another variation of CDH assumption, called divisible computa-

tion Diffie-Hellman assumption, which is interesting from point of views of both
theoretical research and practice.
Divisible computation Diifie-Hellman problem (DCDH problem): On random
input g,g x , g y , computing g y/x . We refer this oracle to as divisional computation
Diffie-Hellman problem.
An algorithm that solves the divisible computational Diffie-Hellman problem
is a probabilistic polynomial time Turing machine, on input g, g x , g y , outputs
g x/y with non-negligible probability. Divisible computation Diffie-Hellman as-
sumption means that there is no such a probabilistic polynomial time Turing
machine. As desired, we are able to show that divisible computational Diifie-
Hellman assumption is equivalent to computational Diffie-Hellman assumption:
CDH ⇐ DCDH
Proof: Suppose we are given an divisible computation Diffie-Hellman oracle
denoted by A4 , on input g, g x , g y , outputs g y/x . We want to show that there
exists an algorithm A1 , on input g, g x , g y , outputs g xy . Given g, g x , g y , we choose
s1 , s2 , t1 , t2 ∈ Zq at random, and compute v1 := A4 (g, (g x )s1 , g s2 )=g xs1 /s2 , v2 : =
A4 (g, g t1 , (g y )t2 = g t1 /(yt2 ) . Finally, we compute v := A3 (v1 , v2 ) = g (xys1 t2 )/(s2 t1 ) .
Since s1 , s2 , t1 , t2 are known already, it follows that g xy can be computed from
v, s1 , s2 , t1 , t2 immediately with same advantage.
DCDH ⇐ CDH
Proof: Suppose we are given an computational Diffie-Hellman oracle A1 , on
input g, g x , g y , it outputs g xy . We want to show that there exists an algorithm
A4 , on input g, g x , g y , outputs g y/x . Suppose we are given a triple g, g x , g y
now. By assumption, we are given a computational Diffie-Hellman oracle A1 ,
consequently, we are able to construct an InvCDH oracle A3 . Viewing g, g y as
−1
input to A3 to obtain v := g y . Finally, one views g, g x , v as input to A1 to
obtain g x/y .
We prove the fact that if the underlying group with prime order q, all vari-
ations of computational Diffie-Hellman problem are equivalent, i.e., CDH ⇔
SCDH ⇔ InvCDH ⇔ DCDH.
 Variations of Diffie-Hellman Problem 305

3 Variations of Decisional Diffie-Hellman Problem

In this section, we study variations of decisional Dffie-Hellman problem. It has

been known for years that the various DDH-based problems been published many
times and commented under many angles. Recently reductions were known from
the work of Sadeghi and Steiner [19] in the generic model, but the present paper
provides reductions in the high granularity setting. Before formally study the
relationship among the variation problems, we would like to provide a formal
definitions of the related problems.

3.1 Formal Definitions on Variations of Decisional Diffie-Hellman

Problem

Decisional Diffie-Hellman assumption-DDH: Let G be a large cyclic group of

prime order q defined above. We consider the following two distributions:

– Given a Diffie-Hellman quadruple g, g x , g y and g xy , where x, y ∈ Zq , are

random strings chosen uniformly at random;
– Given a random quadruple g, g x , g y and g r , where x, y, r ∈ Zq , are random
strings chosen uniformly at random.

An algorithm that solves the Decisional Diffie-Hellman problem is a statistical

test that can efficiently distinguish these two distributions. Decisional Diffie-
Hellman assumption means that there is no such a polynomial statistical test.
This assumption is believed to be true for many cyclic groups, such as the prime
sub-group of the multiplicative group of finite fields.
Square decisional Diffie-Hellman assumption-SDDH: Let G be a large cyclic
group of prime order q defined above. We consider the following two distributions:
2
– Given a square Diffie-Hellman triple g, g x and g x , where x ∈ Zq , is a random
string chosen uniformly at random;
– Given a random triple g, g x and g r , where x, r ∈ Zq , are two random strings
chosen uniformly at random.

An algorithm that solves the square decisional Diffie-Hellman problem

(SDDH for short) is a statistical test that can efficiently distinguish these two
distributions. Square decisional Diffie-Hellman assumption means that there is
no such a polynomial statistical test.
Inverse decisional Diffie-Hellman assumption -InvDDH: Let G be a large
cyclic group of prime order q defined above. We consider the following two dis-
tributions:
−1
– Given a inverse Diffie-Hellman triple g, g x and g x , where x ∈ Zq , is a
random string chosen uniformly at random.;
– Given a random triple g, g x and g r , where x, r ∈ Zq , are random strings
chosen uniformly at random.
306 F. Bao, R.H. Deng, and H. Zhu

An algorithm that solves the Inverse decisional Diffie-Hellman problem (In-

vDDH for short) is a statistical test that can efficiently distinguish these two
distributions. Inverse decisional Diffie-Hellman assumption means that there is
no such a polynomial statistical test.
Divisible decision Diffie-Hellman assumption-DDDH: Let G be a large cyclic
group of prime order q defined above. We consider the following two distributions:
– Given a divisible Diffie-Hellman quadruple g, g x , g y and g x/y , where x, y ∈
Zq , are random strings chosen uniformly at random;
– Given a random quadruple g, g x and g y and g r , where x, y, r ∈ Zq , are
random strings chosen uniformly at random.
An algorithm that solves the divisible decision Diffie-Hellman problem
(DDDH for short) is a statistical test that can efficiently distinguish these two
distributions. Divisive decision Diffie-Hellman assumption means that there is
no such a polynomial statistical test.

3.2 Relations among Variations of Decisional Diffie-Hellman

Assumption
Analogous the arguments above, we consider relations among variations of de-
cisional Diffie-Hellman assumption. We first prove the equivalence between In-
vDDH and SDDH assumptions.
InvDDH ⇐ SDDH.
Proof: Given a distinguisher D1 which is able to tell square Diffie-Hellman
triple from a random triple with non-negligible probability, we want to show that
there exists a polynomial distinguisher D2 which is able to tell inverse Diffie-
Hellman triple from a random triple with non-negligible advantage. Now we are
given g, g x and g r , where r is either x−1 or a random string. Setting h1 ← (g r )s ,
2
h2 ← g s and h3 ← (g x )s ), where s ∈ Zq is a random string. We remark that
−1 −1 −1 2 2
if r = x−1 , then h1 = (g x )s , and h2 = (g x )sx , and h3 = (g x )s x . If
g r is a random triple, then (h1 , h2 , h3 ) is also a random triple. We then view
(h1 , h2 , h3 ) as input to the oracle D1 to obtain correct value b ∈ {0, 1} (b=0
if the answer of D1 is SDDH triple, and 0 otherwise). Therefore, we have a
polynomial distinguisher D2 which is able to tell inverse Diffie-Hellman triple
from a random triple with same non-negligible advantage.
SDDH ⇐ InvDDH.
Proof: Given a distinguisher D2 , which is able to tell the inverse decisional
Diffie-Hellman triple from a random triple with non-negligible advantage, we
want to show that there exists a distinguisher D1 that is able to tell the square
decisional Diffie-Hellman triple from a random pair with non-negligible advan-
tage. Given g, g x , g r , where either r = x2 or r ∈ Zq a random string. Setting,
−1
h1 ← g x , h2 ← (g r )s and h3 ← g s . We remark that if r = x2 , then h1 = g x ,
−1
h2 = (g x )xs and h3 = (g x )(xs) . If r is a random string, then h1 , h2 and h3 are
random triple. We view (h1 , h2 , h3 ) as input to inverse decisional Diffie-Hellman
distinguisher D2 to obtain correct value b ∈ {0, 1} (b=0 if the answer of D2 is
 Variations of Diffie-Hellman Problem 307

InvDDH triple, and 0 otherwise). Therefore, we have a polynomial distinguisher

D2 which is able to tell square Diffie-Hellman triple from a random triple with
same non-negligible advantage.
Based on the above arguments, we know the fact that SDDH ⇔ InvDDH.
Then we consider the equivalence between DDDH and DDH.
DDDH ⇔ DDH.
Proof: Given (g, g x , g y , g x/y ), one simply submits (g, g y , g x/y , g x ) to DDH to
decide the divisible format of the quadruple;
DDH ⇔ DDDH
Conversely, given (g, g x , g y , g xy ), one queries DDDH with (g, g xy , g y , g x ) and
return DDDH’s answer (plus, queries can be easily randomized if needed).
Therefore, we know the fact that DDDH ⇔ DDH.
Finally, we consider the problem whether DDH ⇔ SDDH or not. Firstly, we
show the fact below:
SDDH ⇐ DDH.
Proof: Given a distinguisher D, which is able to tell the standard deci-
sional Diffie-Hellman triple from the random triple with non-negligible advan-
tage, we want to show that there exists a distinguisher D1 that is able to
tell the square decisional Diffie-Hellman triple from a random triple with non-
negligible advantage. Suppose we are given a triple (g, g x , g z ), where g z is either
2
of the form g y or g x , we then choose two strings s, t at random, and compute
u ← (g x )s ,v ← (g x )t , w ← (g z )st . We remark that if (g, g x , g z ) is square Diffie-
Hellman triple then (g, u, v, w) is a Diffie-Hellman quadruple and if (g, g x , g z )
is random triple then (g, u, v, w) is a random quadruple. Finally, we view the
quadruple (g, u, v, w) as an input to the distinguisher D to obtain correct value
b ∈ {0, 1} (b=0 if the answer of D is DDH quadruple, and 0 otherwise). There-
fore if D1 is able to distinguish a Diffie-Hellman quadruple or random quadruple
with non-negligible advantage then there is a square Difie-Hellman distinguisher
D1 that is able to tell the square decisional Diffie-Hellman triple from a random
triple with same non-negligible advantage.
Unfortunately, we are not able to show that DDH ⇐ SDDH. This leaves
an interesting research problem. Recall that the computational Diffie-Hellman
problem (CDH assumption) equivalents the square computational Diffie-Hellman
problem (SCDH assumption), we believe this conjecture true if the underlying
group G ∈ Zp∗ , e.g., |G| = q and p = 2q + 1.
Conjecture: Under the assumption of group structure of G, DDH is equivalent
to SDDH.

3.3 Polynomial Samples Setting

We are interested in generalized variations of Diffie-Hellman problem. These as-
sumptions play central role for the construction of dynamic group protocols([1],
[3], [6], [7], [19], [20]). In this section, we are considering variations of the de-
cisional Diffie-Hellman problem in polynomial samples setting. We study those
generalized variations of Diffie-Hellman problem by first provided some related
notions, then we present optimal reductions from one to another.
308 F. Bao, R.H. Deng, and H. Zhu

Generalized Decisional Diffie-Hellman assumption: for any k, the following

distributions are indistinguishable:
– The distribution R2k of any random tuple (g1 , · · · , gk , u1 , · · ·,uk ) ∈ G2k ,
where g1 , · · · , gk , and u1 , · · · , uk are uniformly distributed in G2k ;
– The distribution D2k of tuples (g1 , · · · , gk , u1 , · · · , uk ) ∈ G2k , where g1 , · · · , gk
are uniformly distributed in Gk , and u1 = g1r , · · · , uk = gkr for random r ∈ Zq
chosen at random.
An algorithm that solves the generalized decisional Diffie-Hellman problem
is a statistical test that can efficiently distinguish these two distributions. Gen-
eralized decisional Diffie-Hellman assumption means that there is no such a
polynomial statistical test.
Similarly, one can extend the variation of decisional Diffie-Hellman problem
to the general case of other types.
Generalized square decisional Diffie-Hellman assumption (GSDDH): Let G
be a large cyclic group of prime order q defined above. We consider the following
two distributions:
– The distribution R3k of any random tuple (g1 , · · · , gk , g1 x1 , · · · , gk xk , u1 ,
· · · , uk ) ∈ G3k , where g1 , · · · , gk , x1 , · · · , xk and u1 , · · · , uk are uniformly
distributed in G3k ;
– The distribution D3k of tuples (g1 , · · · , gk , g1 x1 , · · · , gk xk , u1 , · · · , uk ) ∈ G3k ,
where g1 , · · · , gk , g1 x1 , · · · , gk xk are uniformly distributed in Gk while u1 =
2 2
g1x1 , · · · , uk = gk xk for each xi uniformly distributed in Zq .
An algorithm that solves the generalized square decisional Diffie-Hellman
problem is a statistical test that can efficiently distinguish these two distribu-
tions. Square decisional Diffie-Hellman assumption means that there is no such
a polynomial statistical test.
Generalized inverse decisional Diffie-Hellman assumption (GInvDDH): Let G
be a large cyclic group of prime order q defined above. We consider the following
two distributions:
– The distribution R3k of any random tuple (g1 , · · · , gk , g1 x1 , · · · , gk xk , u1 ,
· · · , uk ) ∈ G3k , where g1 , · · · , gk , x1 , · · · , xk and u1 , · · · , uk are uniformly
distributed in G3k ;
– The distribution D3k of tuples (g1 , · · · , gk , g1 x1 , · · · , gk xk , u1 , · · · , uk ) ∈ G3k ,
where g1 , · · · , gk , g1 x1 , · · · , gk xk are uniformly distributed in Gk while u1 =
−1 −1
g1 x1 , · · · , uk = gk xk for each xi uniformly distributed in Zq .
An algorithm that solves the generalized inverse decisional Diffie-Hellman
problem (GInvDDH for short) is a statistical test that can efficiently distinguish
these two distributions. Generalized inverse decisional Diffie-Hellman assumption
means that there is no such a polynomial statistical test.
Now we are able to show that the generalized decisional Diffie-Hellman as-
sumption is true even in the polynomial sampling setting. The argument is by
mathematics induction.
 Variations of Diffie-Hellman Problem 309

6-DDH ⇐ 4-DDH.
Proof: Let us consider a machine M that can get a non-negligible advantage

between D4 and R4 . We define a 6-DDH distinguisher M  , which runs as follows:
Given any six-tuple (g1 , g2 , g3 , u1 , u2 , u3 ), which comes from either R6 or D6 , M 
runs M on the quadruple (g1 g2 , g3 , u1 u2 , u3 ) and simply forwards the answer. As
explained by the equations presented below, that if (g1 , g2 , g3 , u1 , u2 , u3 ) follows
the distribution D6 , then (g1 g2 , g3 , u1 u2 , u3 ) follows the distribution D4 . It is also
the same between R6 and R4 . As a consequence, our new machine gets the same
advantage
in distinguishing D6 and R6 with the help of M in distinguishing
D4 and R4 , performing just one more multiplication in G, where G is assumed
to be a cyclic group of order q, and g is assumed to be a generator of this group.
We denote the output of M (respectively M  )as follows: If the input comes from
D4 (D6 respectively), it outputs 1 and 0 if the input tuple comes from R4 (R6
respectively).

P r[M (g1 g2 , g3 , u1 u2 , u3 ) = 1|(g1 , g2 , g3 , u1 , u2 , u3 ) ∈ R6 ]

= P r[M (g x1 +x2 , g x3 , g x4 +x5 , g x6 ) = 1|x1 , x2 , x3 , x4 , x5 , x6 ∈ Zq ]
= P r[M (g x , g y , g z , g r ) = 1|x, y, z, r ∈ Zq ]
= P r[M (g1 , g2 , u1 , u2 ) = 1|(g1 , g2 , u1 , u2 ) ∈ R4 ]
and
P r[M (g1 g2 , g3 , u1 u2 , u3 ) = 1|(g1 , g2 , g3 , u1 , u2 , u3 ) ∈ D6 ]
= P r[M (g x1 +x2 , g x3 , g r(x1 +x2 ) , g rx3 ) = 1|x1 , x2 , x3 , r ∈ Zq ]
= P r[M (g x , g y , g rx , g ry ) = 1|x, y, r ∈ Zq ]
= P r[M (g1 , g2 , u1 , u2 ) = 1|(g1 , g2 , u1 , u2 ) ∈ D4 ]
4-DDH ⇐ 6-DDH
Let us consider a machine M that can get a non-negligible advantage

between D6 and R6 . We define a 4-DDH distinguisher M  , which runs as
follows: on a given quadruple (g1 , g2 , u1 , u2 ), M  runs M on the six-tuple
(g1 , g2 , g1s g2t , u1 , u2 , us1 ut2 ), for randomly chosen s and t in Zq , and simply for-
wards the answer. Once again, the advantage of our new distinguisher M  is
exactly the same as the advantage of M , with very few more computations: we
assume again g to be a generator of G, and we insist on the fact that Zq is a
field.

P r[M  (g1 , g2 , u1 , u2 ) = 1|(g1 , g2 , u1 , u2 ) ∈ D4 ]

= P r[M (g x1 , g x2 , g sx1 +tx2 , g rx1 , g rx2 , g srx1 +trx2 ) = 1|x1 , x2 , r, s, t ∈ Zq ]
= P r[M (g x1 , g x2 , g x3 , g rx1 , g rx2 , g rx3 ) = 1|x1 , x2 , x3 , r ∈ Zq ]
= P r[M (g1 , g2 , g3 , u1 , u2 , u3 ) = 1|(g1 , g2 , g3 , u1 , u2 , u3 ) ∈ D6 ]
and
310 F. Bao, R.H. Deng, and H. Zhu

P r[M  (g1 , g2 , u1 , u2 ) = 1|(g1 , g2 , u1 , u2 ) ∈ R4 ]

= P r[M (g x1 , g x2 , g sx1 +tx2 , g y1 , g y2 , g sy1 +ty2 ) = 1|x1 , x2 , s, t, y1 , y2 ∈ Zq ]

= P r[M (g x1 , g x2 , g x3 , g y1 , g y2 , g y3 ) = 1|(x1 , x2 , x3 , y1 , y2 , y3 ) ∈ Zq 6 ]

= P r[M (g1 , g2 , g3 , u1 , u2 , u3 ) = 1|(g1 , g2 , g3 , u1 , u2 , u3 ) ∈ R6 ]

Based on the above argument, we obtain the useful result: the Decisional
Diffie-Hellman Problems, 4-DDH and 6-DDH, are equivalent.
We known that the obtained reductions are optimal since an advantage
against one of these problems can be reached against the other one. There-
fore, under the sole classical Decisional Diffie-Hellman assumption, for any k,
the generalized decisional Diffie-Hellman assumption is indistinguishable.
With the same technique above, the generalized square decisional Diffie-
Hellman assumption and the generalized inverse decisional Diffie-Hellman as-
sumption can be easily proved. We also remark that the standard hybrid tech-
nique provides alternative approach to prove the Decisional Diffie-Hellman prob-
lem in the polynomial sampling setting.

4 Conclusions

We have studied the relationship among variations of Diffie-Hellman problem in-

cluding the computational and decisional cases with efficient reductions. We show
that all four variations of computational Diffie-Hellman problem are equivalent
if the order of a underlying cyclic group is large prime. Also, we are considering
variations of the decisional Diffie-Hellman problem in single sample and poly-
nomial samples setting. We are able to show that all variations are equivalent
except for the argument DDH ⇐ SDDH, and thus leave an interesting open
problem.

References

1. Eli Biham, Dan Boneh, and Omer Reingold. Breaking generalized Diffie Hellman
modulo a composite is no easier than factoring. Information Processing Letters,
70:83–87, 1999.
2. Bresson, Chevassut and Pointcheval, The Group Diffie-Hellman Problems, SAC’02.
3. Mike Burmester, Yvo Desmedt, and Jennifer Seberry. Equitable key escrow with
limited time span (or, how to enforce time expiration cryptographically). In K.
Ohta and D. Pei, editors, Advances in Cryptology – ASIACRYPT ’98, number
1514 in Lecture Notes in Computer Science, pages 380–391. Springer Verlag, Berlin
Germany, 1998.
4. D.Beaver: Foundations of Secure Interactive Computing. CRYPTO 1991: 377–391.
5. Dan Boneh. The Decision Diffie-Hellman problem. In Third Algorithmic Number
Theory Symposium, number 1423 in Lecture Notes in Computer Science, pages
48–63. Springer Verlag, Berlin Germany, 1998.
 Variations of Diffie-Hellman Problem 311

6. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Con-
stantinople: Practical asynchronous Byzantine agreement using cryptography. In
Proceedings of the 19th Annual ACM Symposium on Principles of Distributed
Computing, Portland, Oregon, July 2000. ACM. Full version appeared as Cryptol-
ogy ePrint Archive Report 2000/034 (2000/7/7).
7. Jan Camenisch, Ueli Maurer, and Markus Stadler. Digital payment systems with
passive anonymity evoking trustees. In E. Bertino, H. Kurth, G. Martella, and E.
Montolivo, editors, Proceedings of the Fourth European Symposium on Research
in Computer Security (ESORICS), number 1146 in Lecture Notes in Computer
Science, pages 33–43, Rome, Italy, September 1996. Springer Verlag, Berlin Ger-
many.
8. Ronald Cramer and Victor Shoup. A practical public key cryptosystem provably
secure against adaptive chosen ciphertext attack. In Hugo Krawczyk, editor, Ad-
vances in Cryptology-CRYPTO’98, number 1462 in Lecture Notes in Computer
Science, pages 13–25. International Association for Cryptologic Research, Springer
Verlag, Berlin Germany, 1998.
9. Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE Trans-
actions on Information Theory, IT No.2(6):644–654, November 1976.
10. Helena Handschuh, Yiannis Tsiounis, and Moti Yung. Decision oracles are equiv-
alent to matching oracles. In International Workshop on Practice and Theory in
Public Key Cryptography ’99 (PKC ’99), number 1560 in Lecture Notes in Com-
puter Science, Kamakura, Japan, March 1999. Springer Verlag, Berlin Germany.
11. Kevin S. McCurley. The discrete logarithm problem. In Carl Pomerance, editor,
Cryptology and Computational Number Theory, volume 42 of Proceedings of Sym-
posia in Applied Mathematics, pages 49–74, Providence, 1990. American Mathe-
matical Society.
12. Ueli M. Maurer and Stefan Wolf. Diffie-Hellman oracles. Neal Koblitz, editor.
Advances in Cryptology-CRYPTO ’96, number 1109 in Lecture Notes in Com-
puter Science, pages 268–282. International Association for Cryptologic Research,
Springer Verlag, Berlin Germany, 1996.
13. Ueli M. Maurer and Stefan Wolf. Lower bounds on generic algorithms in groups.
In Kaisa Nyberg, editor, Advances in Cryptology-EUROCRYPT ’98, number 1403
in Lecture Notes in Computer Science, pages 72–84. International Association for
Cryptologic Research, Springer Verlag, Berlin Germany, 1998.
14. Ueli M. Maurer and Stefan Wolf. Diffie-Hellman, Decision Diffie-Hellman, and
discrete logarithms. In IEEE Symposium on Information Theory, page 327, Cam-
bridge, USA, August 1998.
15. Moni Naor and Omer Reingold. Number theoretic constructions of efficient pseudo-
random functions. In 38th Symposium on Foundations of Computer Science
(FOCS), pages 458–467. IEEE Computer Society Press, 1997.
16. Tatsuaki Okamoto and David Pointcheval, The Gap-Problems: a New Class of
Problems for the Security of Cryptographic Schemes. Proceedings of the 2001
International Workshop on Practice and Theory in Public Key Cryptography
(PKC’2001)(13-15 February 2001, Cheju Island, South Korea) K. Kim Ed., pages
104–118, LNCS 1992, Springer-Verlag, 2001.
17. Birgit Pfitzmann and Ahmadeza Sadeghi. Anonymous fingerprinting with direct
non-repudiation. T. Okamoto, editor. Advances in Cryptology – ASIACRYPT
’2000, number 1976 in Lecture Notes in Computer Science, Kyoto, Japan, 2000,
pages 401–414. International Association for Cryptologic Research, Springer Ver-
lag, Berlin Germany.
312 F. Bao, R.H. Deng, and H. Zhu

18. Victor Shoup. Lower bounds for discrete logarithms and related problems. In
Walter Fumy, editor, Advances in Cryptology-EUROCRYPT’97, number 1233 in
Lecture Notes in Computer Science, pages 256–266. International Association for
Cryptologic Research, Springer Verlag, Berlin Germany, 1997.
19. Ahmad-Reza Sadeghi, Michael Steiner: Assumptions Related to Discrete Loga-
rithms: Why Subtleties Make a Real Difference; Eurocrypt 2001, LNCS 2045,
Springer-Verlag, May 2001, 243–260.
20. Michael Steiner, Gene Tsudik, and Michael Waidner. Key agreement in dynamic
peer groups. IEEE Transactions on Parallel and Distributed Systems, 11(8):769–
780, August 2000.
21. Stefan Wolf. Information theoretically and Computationally Secure Key Agreement
in Cryptography. PhD thesis, ETH Zurich, 1999.