The Chaum-Pedersen protocol allows a prover to convince a skeptical verifier that a given triple is
a DH-triple, without revealing anything else to the verifier.
Let G \mathbb{G} G be a cyclic group of prime order q q q generated by g ∈ G g \in \mathbb{G} g∈G. For α , β , γ ∈ Z q \alpha, \beta, \gamma \in \mathbb{Z}_q α,β,γ∈Zq?, we say that ( g α , g β , g γ ) (g^{\alpha}, g^{\beta}, g^{\gamma}) (gα,gβ,gγ) is a DH-triple if α β = γ \alpha\beta = \gamma αβ=γ. Equivalently, ( u , v , w ) (u, v, w) (u,v,w) is a DH-triple if and only if there exists β ∈ Z q \beta \in \mathbb{Z}_q β∈Zq? such that v = g β v = g^{\beta} v=gβ and w = u β w = u^{\beta} w=uβ
Explain: Why the two definitions are equivalent?
Why is it correct?
Explanation: The correctness of the Chaum-Pedersen Protocol is established through two key checks. Firstly, the verification “ g β z = v t ? v c g^{\beta_z} = v_t \cdot v^c gβz?=vt??vc” ensures that the correlation between v v v and β \beta β mirrors that of v t v^t vt and β t \beta^t βt. Similarly, the second verification “ u β z = w t ? w c u^{\beta_z} = w_t \cdot w^c uβz?=wt??wc” confirms that the relationship between w w w and β \beta β aligns with that of w t w^t wt and β t \beta^t βt. Since the prover is assumed to be honest, the veracity of v t ← g β t v_t \leftarrow g^{\beta_t} vt?←gβt? and w t ← u β t w_t \leftarrow u^{\beta_t} wt?←uβt? holds. Consequently, the relationships among ( u , v , w ) (u, v, w) (u,v,w) are analogous, implying that ( u , v , w ) (u, v, w) (u,v,w) forms a DH-triple.