Breaking Generalized Diffie­Hellman Modulo a Composite is 

no Easier than Factoring 

Eli Biham \Lambda Dan Boneh y Omer Reingold z 

Abstract 

The Diffie­Hellman key­exchange protocol may naturally be extended to k ? 2 parties. 

This gives rise to the generalized Diffie­Hellman assumption (GDH­Assumption). Naor and 

Reingold have recently shown an efficient construction of pseudo­random functions and 

proved its security based on the GDH­Assumption. In this note, we prove that breaking 

this assumption modulo a so called Blum­integer would imply an efficient algorithm for 

factorization. Therefore, both the key­exchange protocol and the pseudo­random functions 

are secure as long as factoring Blum­integers is hard. Our reduction strengthen a previous 

``worst­case'' reduction of Shmuely [6]. 

Keywords: Cryptography, Diffie­Hellman Assumption, Factoring, Key­Exchange, Pseudo­ 

Random Function. 

\Lambda Computer Science Department, Technion, Haifa 32000, Israel. E­mail: biham@cs.technion.ac.il 

y Dept. of Computer Science, Stanford University, Staford, CA, 94305­9045. E­mail: 

dabo@cs.stanford.edu 

z Dept. of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot 76100, 

Israel. Research supported by a Clore Scholars award and by a grant from the Israel Science Foundation 

administered by the Israeli Academy of Sciences. E­mail: reingold@wisdom.weizmann.ac.il. 





1 Introduction 

The Generalized Diffie­Hellman (GDH) Assumption was originally considered in the context 

of a key­exchange protocol for k ? 2 parties (see e.g., [6, 8]). This protocol is an extension 

of the (extremely influential) Diffie­Hellman key­exchange protocol [2]. Given a group G 

and an element g 2 G, the high­level structure of the protocol is as follows: Party i 2 [k] def = 

f1; 2; : : : ; kg chooses a secret value, a i . The parties exchange messages of the form g 

Q 

i2I a i 

for several proper subsets, I ( [k]. Given these messages, each of the parties can compute 

g 

Q 

i2[k] a i and this value defines their common key (in some publicly known way). Since the 

parties use an insecure (though authenticated) channel, it is essential that the messages 

they exchange do not reveal g 

Q 

i2[k] a i . The GDH­Assumption is even stronger: informally, 

it states that it is hard to compute g 

Q 

i2[k] a i for an algorithm that can query g 

Q 

i2I a i for 

any proper subset, I ( [k] of its choice. The precise statement of the assumption is given 

in Section 2.1. 

Recently, another application to the GDH­Assumption was proposed by Naor and Rein­ 

gold [4]. They showed an attractive construction of pseudo­random functions that is secure 

as long as the GDH­Assumption holds. Motivated by this application, we provide in this 

note a proof that the GDH­Assumption modulo a Blum­integer follows from the assumption 

that factoring Blum­integers is hard. Similar reductions were previously described in the 

context of the standard Diffie­Hellman assumption by McCurley [3] and Shmuely [6]. In 

fact, Shmuely [6] also provided a related reduction for the GDH­Assumption (modulo a com­ 

posite) itself. Her reduction works when the algorithm that breaks the GDH­Assumption 

succeeds in computing g 

Q 

i2[k] a i for every choice of values ha 1 ; a 2 ; : : : ; a k i (which is not suf­ 

ficient for the applications of the GDH­Assumption). In contrast, our reduction works even 

when the algorithm breaking the GDH­Assumption only succeeds for some non­negligible 

fraction of the ha 1 ; : : : ; a k i. 

2 The Assumptions 

In this section we define the GDH­Assumption in Z \Lambda 

N (the multiplicative group modulo 

N ), where N is a so called Blum­integer. We also define the assumption that factoring 

Blum­integers is hard. The restriction to Blum­integers is quite standard and it makes 

the reduction of factoring to the GDH­Problem much simpler. In order to keep our result 

general, we let N (in both assumptions) be generated by some polynomial­time algorithm 

F IG (where F IG stands for factoring­instance­generator): 

Definition 2.1 (F IG) The factoring­instance­generator, F IG, is a probabilistic polynomial­ 

time algorithm such that on input 1 n its output, N = P \Delta Q, is distributed over 2n 

2n 

We note that 2n 

obey some ``safety'' conditions). 

2.1 The GDH­Assumption 

To formalize the GDH­Assumption (which is described in the introduction) we use the 

following two definitions: 

Definition 2.2 Let N be any possible output of F IG(1 n ), let g be any quadratic­residue 

in Z \Lambda 

N and let ~a = ha 1 ; a 2 ; : : : ; a k i be any sequence of k – 2 elements of [N ]. Define the 

function h N;g;~a with domain f0; 1g k such that for any k­bit input, x = x 1 x 2 \Delta \Delta \Delta x k , 

h N;g;~a (x) def = g 

Q 

x i =1 a i mod N 

Define h r 

N;g;~a to be the restriction of h N;g;~a to the set of all k­bit strings except 1 k (i.e., the 

restriction of h N;g;~a to f0; 1g k n f1 k g). 

Definition 2.3 (ffl­solving the GDH k ­Problem) Let A be a probabilistic oracle machine, 

k = k(n) an integer­valued function such that 8n; k(n) – 2 and ffl = ffl(n) a real­valued func­ 

tion. A ffl­solves the GDH k ­Problem if for infinitely many n's 

Pr[A h r 

N;g;~a (N; g) = h N;g;~a (1 n )] ? ffl(n) 

where the probability is taken over the random bits of A, the choice of N according to the 

distribution F IG(1 n ), the choice of g uniformly at random in the set of quadratic­residues 

in Z \Lambda 

N and the choice of each of the values in ~a = ha 1 ; a 2 ; : : : ; a k(n) i uniformly at random in 

[N ]. 

Informally, the GDH­Assumption is that there is no ``efficient'' oracle machine A that 

ffl­solves the GDH k ­Problem for ``non­negligible'' ffl. We formalize this in the standard way of 

interpreting ``efficient'' as ``probabilistic polynomial­time'' and ``non­negligible'' as ``larger 

than 1=poly''. However, our reduction (Theorem 3.1) is more quantitative. 

Assumption 2.1 (The GDH­Assumption Modulo a Blum­Integer) Let A be any 

probabilistic polynomial­time oracle machine and k = k(n) – 2 any integer­valued func­ 

tion that is bounded by a polynomial (and is efficiently­constructible). There is no positive 

constant ff such that A 1 

n ff ­solves the GDH k ­Problem. 

2.2 The Factoring­Assumption 

We formalize the assumption that factoring Blum­integers is hard in an analogous way: 

Definition 2.4 (ffl­factoring) Let A be a probabilistic Turing­machine and ffl = ffl(n) a 

real­valued function. A ffl­factors if for infinitely many n's 

Pr[A(P \Delta Q) 2 fP; Qg] ? ffl(n) 

where the distribution of N = P \Delta Q is F IG(1 n ). 

Assumption 2.2 (Factoring Blum­Integers) Let A be any probabilistic polynomial­time 

oracle machine. There is no positive constant ff such that A 1 

n ff ­factors. 

2 





3 Reducing Factoring to the GDH­Problem 

Theorem 3.1 Assumption 2.1 (the GDH­Assumption) is implied by Assumption 2.2 (Fac­ 

toring). Furthermore, assume that A is a probabilistic oracle machine with running­time 

t = t(n) such that A ffl­solves the GDH k ­Problem (where k = k(n) – 2, is an integer­valued 

function that is efficiently­constructible and ffl = ffl(n) a real­valued function). Then there 

exists a probabilistic Turing­machine A 0 with running time t 0 (n) = poly(n; k(n)) \Delta t(n) that 

ffl 0 ­factors, where ffl 0 (n) = ffl(n)=2 

1 ; a 2 ; : : : ; a k(n) i. The algorithm A 0 can use A to extract 

square­roots in Z \Lambda 

N and consequently A 0 can factor N (as shown in [5]). This is done as 

follows: 

A 0 first samples v uniformly at random in Z \Lambda 

N and computes g = v 2 k 

mod N . Let ` 

be the order of g in Z \Lambda 

N (note that ` is not known to A 0 ). Since N is a Blum­integer and 

g is a quadratic­residue we have that ` is odd. This implies that 2 2 Z \Lambda 

` and therefore 

2 

g 2 

d N . Under this notation we have for every 0 ! i ! k that g 2 

N;g;~a (x) for any x 6= 1 k (if exactly i ! k bits of x 

are 1 we have that h N;g;~a (x) = g 2 

outputs 

the value u = h N;g;~a (1 n ) = g 2 

2 which enables A 0 to 

factor N . The complete proof follows the same lines along with additional ``randomization'' 

of the a i 's (achieved by taking a i = 2 

­bit Blum­integer. Given N as its input, 

A 0 performs the following basic steps (we later describe how these steps can be carried out 

in the required running time): 

1. Sample v uniformly at random in Z \Lambda 

N . Compute k = k(n) and g = v 2 k 

mod N . Denote 

by ` the order of g in Z \Lambda 

N (note that ` is not known to A 0 ). 

As mentioned above, since N is a Blum­integer and g is a quadratic­residue we have 

that ` is odd. This implies that 2 2 Z \Lambda 

` and therefore 2 

r i + 2 

of A with the value h r 

N;g;~a (q). 

3 





4. Given that A outputs the correct value --- h N;g;~a (1 n ), compute u = g 2 

v 2 mod N . If u 6= \Sigmav mod N , output gcd(u 

The Running­Time of A 0 : 

Steps (1) and (2) can easily be carried out in time poly(n; k(n)). For steps (3) and (4) to 

be carried out in time t 0 (n) = poly(n; k(n)) \Delta t(n) it is enough to show that: 

a. For every query q 2 f0; 1g k n f1 k g the value h N;g;~a (q) can be computed in time 

poly(n; k(n)). 

b. Given h N;g;~a (1 n ), the value g 2 

t denotes the value 2 

this notation, for every i the value g 2 

1, this is implied by the fact that both g 2 

squaring is a permutation 

over the set of quadratic­residues in Z \Lambda 

N (for any Blum­integer, N) we must have that g 2 

k 6= 1 k : 

h N;g;~a (q) = g 

Q 

q i =1 a i = g 

Q 

q i =1 (r i +2 

olynomials (in the variable x) 

Q 

q i =1 (r i +x) and P k 

i=1 a i = g 

Q k 

i=1 (r i +2 

easily be computed in time poly(n; k(n)). We now get that 

(b) holds since: 

g 2 

ffl(n)=2 

hard to verify that: 

Pr[A 0 (N) 2 fP; Qg] = Pr 

h 

(u 6= \Sigmav mod N) and 

i 

A h r 

N;g;~a (N; g) = h N;g;~a (1 n ) 

ji 

Note that A h r 

N;g;~a (N; g) does not depend on v itself but rather on v 2 . Therefore, A h r 

N;g;~a (N; g) 

is equally distributed for any two assignments, w and ¯ 

w, of v as long as w 2 = ¯ 

w 2 mod N . 

4 





This follows from the fact that all the values of h r 

N;g;~a (including g = h r 

N;g;~a (0 n )) only depend 

on v 2 : For every q = q 1 q 2 : : : q k 6= 1 k the value h N;g;~a (q) was shown above to be 

v 

P k ff j 

0 (N) 2 fP; Qg] = 1=2 \Delta Pr[A h r 

N;g;~a (N; g) = h N;g;~a (1 n )] 

Let N be chosen from F IG(1 n ). We need to show that for infinitely many n's 

Pr[A 0 (N) 2 fP; Qg] ? ffl 0 (n) 

Which is equivalent to showing that for infinitely many n's 

Pr[A h r 

N;g;~a (N; g) = h N;g;~a (1 n )] ? ffl(n) 

Definition 3.1 Let X and Y be two random variables over D. The statistical difference 

between X and Y is defined to be 

1 

2 

X 

a2D 

j Pr[X = a] 

Z 

\Lambda 

N . 

Reason: v 2 is a uniformly distributed quadratic­residue in Z \Lambda 

N and squaring is a 

permutation over the set of quadratic­residues in Z 

\Lambda 

N (since N is a Blum­integer). 

Fact 2 Let r and a 0 be uniformly distributed in [N ] and denote by a the value r+2 

same as the distribution of a 0 mod ` con­ 

ditioned on the event that a 0 2 [(Q 

P 

ffl­solves 

the GDH k ­Problem and given Fact 1, we have that: 

Pr[A h r 

N;g; ~ 

a 0 (N; g) = h N;g; ~ 

a 0 (1 n )] ? ffl(n) 

Given Fact 2, it is easy to verify that the two random variables h N;g;~a and h N;g; ~ a 0 are of 

statistical distance O(k(n) \Delta 2 

2 

5 





4 Conclusions 

We showed that breaking the generalized Diffie­Hellman assumption modulo a Blum­integer 

is at least as hard as factoring Blum­integers. This implies that the security of the general­ 

ized Diffie­Hellman key­exchange protocol (which is mentioned in the introduction) can be 

based on the assumption that factoring is hard. In addition, as shown in [4], it implies the 

existence of efficient pseudo­random functions which are at least as secure as factoring. 

A possible line for further research is the study of the generalized Diffie­Hellman assump­ 

tion in other groups and the relation between the generalized Diffie­Hellman assumption 

and the standard Diffie­Hellman assumption. It is interesting to note that the decisional 

version of the generalized Diffie­Hellman assumption is equivalent to the decisional version 

of the standard Diffie­Hellman assumption (as shown in [8]). Two examples of results that 

support the validity of the decisional version of the standard Diffie­Hellman can be found in 

the work of Boneh and Venkatesan [1] and in the work of Shoup [7]. Boneh and Venkatesan 

showed that computing the k (ß p 

log P ) most significant bits of g a\Deltab (given hg; g a ; g b i) is 

as hard as computing g a\Deltab itself. Shoup showed that the DDH­Problem is hard for what he 

calls a ``generic'' algorithm. 

Acknowledgments 

We thank Moni Naor for many helpful discussions and the anonymous referees for many 

helpful comments. 

References 

[1] D. Boneh and R. Venkatesan, Hardness of computing most significant bits in secret keys in 

Diffie­Hellman and related schemes, Advances in Cryptology ­ CRYPTO '96, LNCS, vol. 1109, 

Springer, 1996, pp. 129­142. 

[2] W. Diffie and M. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 

vol. 22(6), 1976, pp. 644­654. 

[3] K. McCurley, A key distribution system equivalent to factoring, J. of Cryptology, vol 1, 1988, 

pp. 95­105. 

[4] M. Naor and O. Reingold, Number­Theoretic constructions of efficient pseudo­random functions, 

Proc. 38th IEEE Symp. on Foundations of Computer Science, 1997. 

[5] M. O. Rabin, Digitalized signatures and public­key functions as intractable as factorization, 

Technical Report, TR­212, MIT Laboratory for Computer Science, 1979. 

[6] Z. Shmuely, Composite Diffie­Hellman public­key generating systems are hard to break, Techni­ 

cal Report No. 356, Computer Science Department, Technion, Israel, 1985. 

[7] V. Shoup, Lower bounds for discrete logarithms and related problems, Proc. Advances in Cryp­ 

tology ­ EUROCRYPT '97, LNCS, Springer­Verlag, 1997, pp. 256­266. 

[8] M. Steiner, G. Tsudik and M. Waidner, Diffie­Hellman key distribution extended to group 

communication, Proceedings 3rd ACM Conference on Computer and Communications Security, 

1996, pp. 31­37. 

6