Discrete Logarithm Problems with Auxiliary Inputs

Let g be an element of prime order p in an abelian group, and let α∈? _p . We show that if g,g ^α , and \(g^{\alpha^{d}}\) are given for a positive divisor d of p?1, the secret key α can be computed deterministically in \(O(\sqrt{p/d}+\sqrt{d})\) exponentiations by using \(O(\max\{\sqrt{p/d},\sqrt{d}\})\) storage. If \(g^{\alpha^{i}}\) (i=0,1,2,…,2d) is given for a positive divisor d of p+1, α can be computed in \(O(\sqrt{p/d}+d)\) exponentiations by using \(O(\max\{\sqrt{p/d},\sqrt{d}\})\) storage. We also propose space-efficient but probabilistic algorithms for the same problem, which have the same computational complexities with the deterministic algorithm.As applications of the proposed algorithms, we show that the strong Diffie–Hellman problem and related problems with public \(g^{\alpha},\ldots,g^{\alpha^{d}}\) have computational complexity up to \(O(\sqrt{d}/\log p)\) less than the generic algorithm complexity of the discrete logarithm problem when p?1 (resp. p+1) has a divisor d≤p ^1/2 (resp. d≤p ^1/3). Under the same conditions for d, the algorithm is also applicable to recovering the secret key in \(O(\sqrt{p/d}\cdot \log p)\) for Boldyreva’s blind signature scheme and the textbook ElGamal scheme when d signature or decryption queries are allowed.