4
$\begingroup$

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

$\endgroup$
3
$\begingroup$
  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$.
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Similarly, you do not know that 𝑏𝐻 is generated by 𝐺" That's should be do know, right? $\endgroup$ – Maeher Feb 1 at 16:27
  • $\begingroup$ 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. $\endgroup$ – Geoffroy Couteau Feb 1 at 17:16
  • $\begingroup$ Ah, the dreaded double negative. :D $\endgroup$ – Maeher Feb 1 at 17:26
2
$\begingroup$
  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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.