Discrete Logarithm Problems with Auxiliary Inputs

摘要

Let g be an element of prime order p in an abelian group, and let α ∈ Z_p.rnWe show that if g, g~α, and ,g~(α~d) are given for a positive divisor d of p - 1, the secret key α can be computed deterministically in O (p/d)~(1/2) + d~(1/2)) exponentiations byrnusing O(ma{(p/d)~(1/2), d~(1/2)}) storage. If g~(α~i) (i = 0, 1, 2.....2d) is given for a positiverndivisor d of p + 1, α can be computed in O((p/d)~(1/2) + d) exponentiations by using 0*max{(p/d)~(1/2), d~(1/2)}) storage. We also propose space-efficient but probabilistic algorithms for the same problem, which have the same computational complexities with the deterministic algorithm.rnAs applications of the proposed algorithms, we show that the strong Diffie-Hellmanrnproblem and related problems with public g~α.....g~(α~d) have computational complexityrnup to O(d~(1/2)/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((p/d)? log p) for Boldyreva's blind signature scheme and the textbook ElGamal scheme when d signature or decryption queries are allowed.