Discrete Logarithm Problems with Auxiliary Inputs
Let g be an element of prime order p in an abelian group, and let a is an element of Z(p). We show that if g, g(alpha), and gad are given for a positive divisor d of p - 1, the secret key a can be computed deterministically in O(root p/d + root d) exponentiations by using O(max{root p/d, root d}) storage. If g(alpha i) (i = 0, 1, 2, ... , 2d) is given for a positive divisor d of p + 1, a can be computed in O(root p/d + d) exponentiations by using O(max{root p/d, root 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), ... , g(alpha d) have computational complexity up to O(root 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(root p/d . log p) for Boldyreva's blind signature scheme and the textbook ElGamal scheme when d signature or decryption queries are allowed.
discrete logarithm auxiliary inputs strong diffie-hellman blind signature baby-step giant-step pollard's kangaroo algorithm elgamal encryption