An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations

A new protocol is presented that allows A to convince B that she knows a solution to the Discrete Log Problem—i.e. that she knows an x such that αx ≡ β (mod N) holds—without revealing anything about x to B. Protocols are given both for N prime and for N composite.We also give protocols for extensions of the Discrete Log problem allowing A to show possession of: multiple discrete logarithms to the same base at the same time, i.e. knowing x₁, . . . , x_K such that $$ \alpha ^{x_1 } \equiv \beta _1 ,...,\alpha ^{x_K } \equiv \beta _K $$;several discrete logarithms to different bases at the same time, i.e. knowing x₁, . . . , x_K such that the product $$ \alpha _1^{x_1 } \alpha _2^{x_2 } \cdot \cdot \cdot \alpha _K^{x_K } \equiv \beta $$;a discrete logarithm that is the simultaneous solution of several different instances, i.e. knowing x such that α₁x≡β₁,...α_Kx≡β_K.We can prove that the sequential versions of these protocols do not reveal any “knowledge” about the discrete logarithm(s) in a well-defined sense, provided that A knows (a multiple of) the order of α.