ZKP The Chaum-Pedersen Protocol

2023-12-28 22:35:36

The Chaum-Pedersen Protocol

Introduction

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?

  1. For the first definition, e ( g α , g β ) = e ( g γ , g ) e(g^{\alpha}, g^{\beta}) = e(g^{\gamma}, g) e(gα,gβ)=e(gγ,g).
  2. For the second definition, we set u = g α u = g^{\alpha} u=gα. Left side = e ( u , g β ) = e ( g α , g β ) = e(u, g^{\beta}) = e(g^{\alpha}, g^{\beta}) =e(u,gβ)=e(gα,gβ). Right side = e ( u β , g ) = e ( g α β , g ) = e ( g γ , g ) = e(u^{\beta},g) = e(g^{\alpha \beta}, g) = e(g^{\gamma},g) =e(uβ,g)=e(gαβ,g)=e(gγ,g). Left side = = = Right side.

Protocol Details

  • Prover: ( β , ( u , v , w ) ) (\beta, (u, v, w)) (β,(u,v,w))
  • Verifier: ( u , v , w ) (u, v, w) (u,v,w)
  • The prover computes β t ← Z q \beta_t \leftarrow \mathbb{Z}_q βt?←Zq?, v t ← g β t v_t \leftarrow g^{{\beta}_t} vt?←gβt?, w t ← u β t w_t \leftarrow u^{\beta_t} wt?←uβt? and sends the commitment v t v_t vt? and w t w_t wt? to the verifier.
  • The verifier computes a random c c c and sends the challenge c c c to the prover.
  • The prover computes β z ← β t + β c \beta_z \leftarrow \beta_t + \beta c βz?←βt?+βc sends the response β z \beta_z βz? to the verifier.
  • The verifier checks if g β z = v t ? v c g^{\beta_z} = v_t \cdot v^c gβz?=vt??vc and u β z = w t ? w c u^{\beta_z}= w_t \cdot w^c uβz?=wt??wc. if so, the verifier outputs “accept”; otherwise, the verifier outputs “reject”.

在这里插入图片描述

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.

文章来源:https://blog.csdn.net/weixin_45347752/article/details/135279089
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。