Pedersen Commitment

Protocol Description

Setup

Let $G$ be a (multiplicative) cyclic group of prime order for which the Discrete Logarithm problem is intractable. The key generation procedure publishes randomly chosen generators $g, h ∈ G$, which serve as both the commitment key and verification key.

Commit

To commit to a number $m ∈ \{0, . . . , |G| − 1\}$, committer picks a random $z ∈ \{0, . . . , |G| − 1\}$ and sends $c = g^m · h^z$.

Open

To open a commitment $c$, committer sends $(m, z)$. Verifier checks that $c = g^m · h^z$.

Properties of the commitment:

• perfect hiding

• computational binding

Additive Homomorphism

One important property of Pedersen commitments is that they are additively homomorphic. This means that the verifier can take two commitments $c_1$ and $c_2$, to values $m_1, m_2 ∈ \{0, . . . , |G| − 1\}$ (with $m_1, m_2$ known to the committer but not to the verifier), and the verifier on its own can derive a commitment $c_3$ to $m_3 = m_1 + m_2$, such that the prover is able to open $c_3$ to $m_3$. This is done by simply letting $c_3 = c_1 · c_2$. As for “opening information” provided by the prover, if $c_1 = h^{m_1} · g^{z_1}$ and $c_2 = h^{m_2} · g^{z_2}$, then $c_3 = h^{m_1+m_2} · g^{z_1+z_2}$, so the opening information for $c_3$ is simply $(m_1 + m_2, z_1 + z_2)$. In summary, Pedersen commitments over a multiplicative group $G$ are additively homomorphic, with addition of messages corresponds to group-multiplication of commitments.

Perfect HVZK Proof of Knowledge of Opening

It is possible to the prover to prove that it knows how to open a commitment $c$ to some value, without actually opening the commitment.

Protocol

1. Let $G$ be a (multiplicative) cyclic group of prime order over which the Discrete Logarithm relation is hard, with randomly chosen generators $g$ and $h$.

2. Input is $c = g^m · h^z$. Prover knows $m$ and $z$, Verifier only knows $c, g, h$.

3. Prover picks $d, r ∈ \{0, . . . , |G| − 1\}$ and sends to verifier $a = g^d · h^r$.

4. Verifier sends challenge $e$ chosen at random from $\{0, . . . , |G| − 1\}$.

5. Prover sends $m' = me + d$ and $z' = ze + r$

6. Verifier checks that $g^{m'}· h^{z'} = c^e · a$

Properties of the protocol:

• perfect completeness

• special soundness

• perfect HVZK

Establishing A Product Relationship Between Committed Values

Suppose the committer sends commitments $(c_1, c_2, c_3)$ that is claimed to be a commitments to values $(m_1, m_2, m_1 · m_2)$. Pedersen commitments are not multiplicatively homomorphic but it is possible to the prover to prove to the verifier that $c_3$ indeed commits to $m_1 · m_2$, without actually opening up $c_3$ and thereby revealing $m_1 · m_2$.

Protocol

1. Let $G$ be a (multiplicative) cyclic group of prime order over which the Discrete Logarithm relation is hard.

2. Input is $c_i = g^{m_i} · h^{r_i}$ for $i ∈ \{1, 2, 3\}$ such that $m_3 = m_1 · m_2 \mod |G|$.

3. Prover knows $m_i$ and $r_i$ for all $i ∈ \{1, 2, 3\}$, verifier only knows $c_1, c_2, c_3, g, h$.

4. Prover picks $b_1, . . . , b_5 ∈ \{0, . . . , |G| − 1\}$ and sends to verifier three values:

$$α ← g^{b_1} · h^{b_2}, β ← g^{b_3} · h^{b_4}, γ ← c_1^{b_3} · h^{b_5}.$$

1. Verifier sends challenge $e$ chosen at random from $\{0, . . . , |G| − 1\}$.

2. Prover sends:

$$z_1 ← b_1 + e · m_1, \\ z_2 ← b_2 + e · r_1, \\ z_3 ← b_3 + e · m_2, \\ z_4 ← b_4 + e · r_2, \\ z_5 ← b_5 + e · (r_3 − r_1m_2).$$

1. Verifier checks that the following three equalities hold:

$$g^{z_1} · h^{z_2} = α · c_1^{e}, \\ g^{z_3} · h^{z_4} = β · c_2^e, \\ c_1^{z_3} · h^{z_5} = γ · c_3^e.$$

Properties of the protocol:

• perfect completeness

• special soundness

• perfect HVZK