Security Analysis of the Strong Diffie-Hellman Problem

Let

g

be an element of prime order

p

in an abelian group and

$\alpha\in {{\mathbb Z}}_p$

. We show that if

g

,

g

α

, and

$g^{\alpha^d}$

are given for a positive divisor

d

of

p

–1, we can compute the secret

α

in

$O(\log p \cdot (\sqrt{p/d}+\sqrt d))$

group operations using

$O(\max\{\sqrt{p/d},\sqrt d\})$

memory. If

$g^{\alpha^i}$

(

i

=0,1,2,...,

d

) are provided for a positive divisor

d

of

p

+1,

α

can be computed in

$O(\log p \cdot (\sqrt{p/d}+d))$

group operations using

$O(\max\{\sqrt{p/d},\sqrt d\})$

memory. This implies that the strong Diffie-Hellman problem and its related problems have computational complexity reduced by

$O(\sqrt d)$

from that of the discrete logarithm problem for such primes.

Further we apply this algorithm to the schemes based on the Diffie-Hellman problem on an abelian group of prime order

p

. As a result, we reduce the complexity of recovering the secret key from

$O(\sqrt p)$

to

$O(\sqrt{p/d})$

for Boldyreva’s blind signature and the original ElGamal scheme when

p

–1 (resp.

p

+1) has a divisor

d

≤

p

1/2

(resp.

d

≤

p

1/3

) and

d

signature or decryption queries are allowed.