# Pedersen commitment in elliptic curves

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$$

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

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

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

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

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

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.

1. $$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.

1. 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$$.

1. 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$$.

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.

• "Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right? – Maeher Feb 1 '19 at 16:27
• It should have been "you do not know that it is not generated by $G$", since that was OP's question. Thanks for pointing it out, I will correct that. – Geoffroy Couteau Feb 1 '19 at 17:16
• Ah, the dreaded double negative. :D – Maeher Feb 1 '19 at 17:26
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.