Pedersen commitment in elliptic curves

Question

I try to understand Pedersen commitment in elliptic curves over finite fields. I could use some clarification.

Let's say we have two generators $G$ and $H$.

1. Is that required that $G$ and $H$ are two different generators of the same group?

Pedersen Commitment $C$ will look like that.

$$C = aG + bH$$

2. $C$ is a point on the curve, right?

Now in the situation when $a=0$ we have

$$C = 0G + bH = bH$$

3. How do I know that $bH$ is generated by $H$ without revealing $b$?

4. How do I know that $bH$ is not generated by $G$?

Answer 1

1. Is that required that $G$ and $H$ are two different generators of the same group?

Yes. Pedersen commitment uses random public generators $G$ and $H$ of a suitable large group where the Discrete Logarithm is hard, thus $G$ and $H$ can safely be assumed distinct. Also, that condition implies no integer $w$ such that $G=w\,H$ can be found by anyone. These facts are assumed or stated.

2. $C=a\,G+b\,H$ is a point on the curve

Yes, though at some implementation level, it is a bitstring describing a point on the curve.

3. How do I know that $b\,H$ is generated by $H$ without revealing $b$?

Anyone given a bitstring alleged to describe a point generated by $H$ can check that assertion, simply by checking that the bitstring indeed describes a point on the curve (which is feasible since the curve's equation and bitstring convention is public). Being generated by $H$ follows, since all points on the curve are generated by any generator (by definition of a generator), and $H$ is a generator.

Also: since the first-person locutor in this question cares about not revealing $b$, s/he knows $b$, thus can compute $b\,H$, which by construction is generated by $H$. If s/he makes that computation privately, that's an alternate way of making the verification without disclosing $b$.

4. How do I know that $b\,H$ is not generated by $G$?

Point $b\,H$ is generated by $G$, even though it may not have been obtained by computation of $x\,G$ for some integer $x$. Obtaining integer $x$ such that $x\,G=b\,H$ not knowing random $b$ would be as hard as the discrete logarithm problem for $G$.

---

My guess is that the intended question 3 is:

How do I know that the alleged $C=b\,H$ was obtained by computation of $b\,H$ without being revealed $b$?

As a verifier in a Pedersen commitment, you don't know that the alleged $C=b\,H$ was obtained by computation of $b\,H$ until being given $b$ by the prover, which is how s/he demonstrates $a=0$.

As rightly pointed in an other answer, there are different interactive protocols (when Pedersen commitment is not) allowing a prover to demonstrate knowledge of integer $b$ such that $b\,H$ is a certain public point, without revealing $b$. Schnorr protocol does so, as:

• prover generates random integer $r$, computes and sends point $T\gets r\,H$
• verifier generates and sends random integer $i$
• prover computes and sends integer $s\gets i\,b+r\bmod n$, where $n$ is the (public) order of the curve
• verifier knowing point $b\,H$ computes point $i\,(b\,H)$, then point $i\,(b\,H)+T$; computes point $s\,H$; and ensures $i\,(b\,H)+T=s\,H$.

Answer 2

Typically, Pedersen commitments will have $G$ and $H$ being generators of the same group. In fact, there exists variants where $G$ and $H$ do not span the same group - but these will usually not be called "Pedersen commitments". So yes, it's required in Pedersen commitments that $G$ and $H$ are different generators of the same group - although it's not an absolute necessity for this design principle to lead to a secure commitment scheme.

If you compute $C = aG+bH$, it will be a point on the curve by construction. When $C = bH$, you always "know" that $bH$ is generated by $H$... Because this is a trivial statement. Since $H$ is a generator, it generates all points of the curve: for any point $P$ on the curve, there is an integer $p$ such that $P = pH$. Similarly, you do not know that $bH$ is not generated by $G$... Because it is. There always exists a $q$ such that $bH = qG$.

Intuitively, this is because Pedersen commitments are only computationally binding: when you commit to $m$ with randomness $r$, as $C = mG+rH$, there exists many alternative openings (in fact, there are valid openings for every possible message) because $C$ does not information-theoretically bind you to a unique pair $(m,r)$. However, it is computationally hard (under the discrete logarithm assumption) to find incorrect openings.

Answer 3

1. Yes. Also the creator of the commitment C should not know the discrete log of one with respect to other, so he should not know that $x$ such that $xG = H$ or he the commitment won't be binding meaning he can lie that he committed to a value by committing to another.
2. Yes.
3. Do a Schnorr protocol for proof of knowledge of a discrete logarithm.
4. I think you are asking that can you prove that given a $G$, $H$ and a commitment $C$, it commits to 0. You cannot prove it with only this much information.