Question

Discrete Logarithm and Diffie Hellman Problems [20 Marks]

(a) Let G be a cyclic group of prime order q generated by g∈G. Let h∈G be an arbitrary group element. For u∈G, a representation (relative to g and h ) of u is a pair (α,β)∈Z²ᵩ such that g^α h^β =u. For any given u∈G there are many representations (in fact, there are q of them). Show that, given two different representations of the same group element u, we can efficiently compute DLog (h) (the discrete log of h with respect to generator g ). Use this fact to suggest, under the Discrete Log assumption, a collisionresistant hash function H(α,β) defined over Z²ᵩ for a given group G and elements g,h∈G.
(b) Let G be a group generation algorithm that on input 1ⁿ, outputs a cyclic group G, its order q( with ∥q∥=n ) and a generator g. Prove, by employing a suitable reduction, that the hardness of the Computational Diffie Hellman (CDH) problem relative to G implies the hardness of the Discrete-Logarithm problem relative to G.

Answer 1

To compute the discrete logarithm of h with respect to generator g given two different representations of the same group element u, subtract the representations and use the fact that g^α₁-α₂ = h^β₂-β₁. This allows us to efficiently compute DLog(h) = β₂ - β₁. A suggested collision-resistant hash function H(α, β) can be defined as H(α, β) = g^α h^β based on the hardness of the discrete log problem. To prove that the hardness of the CDH problem implies the hardness of the Discrete-Logarithm problem, employ a suitable reduction from the CDH problem to the Discrete-Logarithm problem.

Step-by-step explanation:

To show that we can efficiently compute the discrete logarithm of h with respect to generator g, given two different representations of the same group element u, we can use the fact that g^α h^β = u. Let's assume we have two representations (α₁, β₁) and (α₂, β₂) of the same u. Subtracting the two equations, we get g^(α₁-α₂) h^(β₁-β₂) = 1.

Since G is a cyclic group of prime order q, we have g^q = 1. Therefore, we can rewrite the equation as g^(α₁-α₂) h^(β₁-β₂) = g^(0) h^(0) = 1. Rearranging the equation, we get g^(α₁-α₂) = h^(β₂-β₁).

Now, we can easily compute the discrete log of h with respect to generator g by using the difference in the exponents. In other words, DLog(h) = β₂ - β₁.

Based on the fact that we can efficiently compute the discrete logarithm, we can suggest a collision-resistant hash function H(α, β) defined over Z²ᵩ. We can define H(α, β) = g^α h^β. Since the discrete log problem is believed to be hard, this hash function would be considered collision-resistant.

Regarding part (b), to prove that the hardness of the Computational Diffie Hellman (CDH) problem relative to G implies the hardness of the Discrete-Logarithm problem relative to G, we can employ a suitable reduction. Let's assume we have a hypothetical algorithm that can efficiently solve the CDH problem in group G. We can use this algorithm to construct another algorithm that can efficiently solve the Discrete-Logarithm problem in group G. Therefore, the hardness of the CDH problem implies the hardness of the Discrete-Logarithm problem.