Multiple Discrete Logarithm Problems with Auxiliary Inputs

摘要

Let g be an element of prime order p in an abelian group and let α_1, ..., α_L ∈ Z_p for a positive integer L. First, we show that, if g, g~(α_i), and g~(α_i~d) (i = 1,..., L) are given for d | p - 1, all the discrete logarithms α_i's can be computed probabilistically in O({the square root of}(L·p/d)+{the square root of}(L·d)) group exponentiations with O(L) storage under the condition that L min{(p/d)~(1/4), d~(1/4)}. Let f ∈ F_p [x] be a polynomial of degree d and let ρ_f be the number of rational points over F_p on the curve determined by f(x) - f(y) = 0. Second, if g, g~(α_i), g~(α_i~2),..., g~(α_i~d) are given for any d ≥ 1, then we propose an algorithm that solves all α_i's in O(max{{the square root of}(L· p~2/ρ_f), L · d}) group exponentiations with O({the square root of}(L·p~2/ρf)) storage. In particular, we have explicit choices for a polynomial f when d | p ± 1, that yield a running time of O({the square root of}(L·p/d)) whenever L ≤ p/c·d~3 for some constant c.