Security Analysis of the Strong Diffie-Hellman Problem

摘要

Let g be an element of prime order p in an abelian group and α ∈ Z_p. We show that if g,g~α, and g~(α~d) are given for a positive divisor d of p — 1, we can compute the secret α in O(log p · ((p/d)~(1/2) + d~(1/2))) group operations using O(max{(p/d)~(1/2), d~(1/2)}) memory. If g~(α~i) (i = 0,1, 2,..., d) are provided for a positive divisor d of p + 1, α can be computed in O(log p · ((p/d)~(1/2) + d)) group operations using O(max{(p/d)~(1/2), d~(1/2)}) memory. This implies that the strong Diffie-Hellman problem and its related problems have computational complexity reduced by O(d~(1/2)) 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(p~(1/2)) to O((p/d)~(1/2)) 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.