1
$\begingroup$

This is about the KZG Polynomial Commitment Scheme

In Section 2, it's written

We use the notation $e : \mathbb G \times \mathbb G \mapsto \mathbb G_T$ to denote a symmetric (type 1) bilinear pairing.The choice of type 1 pairings was made to simplify presentation, however, our constructions can easily be modified to work with pairings of types 2 and 3 as well.

The above uses only one Elliptic Curve Group whose generator $\mathbb G$.

In the appendix where the document describes Bilinear Pairings, this is the description.

For three cyclic groups $\mathbb G,\widehat{\mathbb G}$ and $\mathbb G_T$ (all of which we shall write multiplicatively) of the same prime order $p$, a bilinear pairing $e$ is a map $e : \mathbb G \times \widehat{\mathbb G} \mapsto \mathbb G_T$

Note that here 2 different elliptic curve groups $\mathbb G$ & $\widehat{\mathbb G}$ respectively are used (instead of $\mathbb G$ being used as both the first & second group in the earlier description).

And this is not just for type 1 pairings, but all 3 types of pairings can have different generators.

I am a little confused about how the proof would work if the 2 generators were different.

For e.g. if we have to prove

$Q(x) = \frac {F(x) - c} {x-b}$,

This is how we do it.

$Q(x)(x-b) = F(x) -c$

Evaluating at $x=a$

$Q(a)(a-b) = F(a) - c$

Now we multiply both sides by $G$ (which is the generator of the group $\mathbb G$ & this becomes

$Q(a).G.(a-b) = F(a).G - c$

Now $C_Q = Q(a).G$ (commitment of $Q$) &

$C_F = F(a).G$ (commitment of $F$)

From here, it's easy to prove that if $e(Q(a)G, (a-b)G) \stackrel{?}{=} e((F(a)-c)G, G)$ is true, then the original statement $Q(x)(x-b) = F(x) -c$ is true. (This proof is also given in the KGZ paper in multiplicative notation). However, I am not able to derive the proof for $G_1 \ne G_2$ - how do I derive the proof for the above in case I am using two different groups with generators $G_1$ & $G_2$.

Now this easy converting of a polynomial into it's commitment by multiplying both sides by the single generator is key to using pairings to prove without knowing the polynomial itself.

I am not sure how this translates to the two groups being different $\mathbb G$ & $\widehat{\mathbb G}$ because they would then have different generators & you won't be able to multiply both sides by the same generator to convert the polynomial into it's commitment so as to verify a proof without knowing the polynomial itself (and just knowing the SRS).

So where exactly is the generator of the 2nd Group $\widehat{\mathbb G}$ used & how does one convert the polynomials into their respective commitments in that case.

$\endgroup$

1 Answer 1

1
$\begingroup$

Pairings allow to do "multiplications in the exponent". Therefore, a good candidate for where $G_2$ comes in is where there's multiplication. The winner is $$Q(x)(x-b) = F(x) -c.$$ The polynomial equality required for verification can be computed by: $$e(Q(a)G_1, (a-b)G_2) \stackrel{?}{=} e((F(a)-c)G_1, G_2).$$

Correctness: Assuming $$e(Q(a)G_1, (a-b)G_2) = e((F(a)-c)G_1, G_2),$$

then, by the bi-linearity of the pairing we have $$Q(a)*(a-b)e(G_1, G_2) = (F(a) - c)e(G_1, G_2).$$ Which holds if and only if $Q(a)(a-b) = F(a) - c$ (over the appropriate field) as desired.

This version of the KZG in the asymmetric paring setting requires that the setup algorithm produces $aG_2$ as well.

$\endgroup$
7
  • $\begingroup$ I can prove that if $e(Q(a)G, (a-b)G) \stackrel{?}{=} e((F(a)-c)G, G)$ is true, then the original statement $Q(x)(x-b) = F(x) -c$ is true - note that I am using $G_1 = G_2$ - this proof is given in the KGZ paper & it can be proven easily. However, I am not able to derive the proof for $G_1 \ne G_2$ - that's my question. $\endgroup$
    – user93353
    Aug 21, 2023 at 0:18
  • $\begingroup$ The proof is generally the same. We just need to use the bilinearity of the pairing. I'll develop this later. $\endgroup$ Aug 21, 2023 at 5:59
  • $\begingroup$ But in the case where $G_1 = G_2 = G$, converting the polynomial into a commitment involves multiplying both sides of the equation to be proved with $G$ at $x = a$ which converts the polynomial into a commitment of the polynomial - i.e. if there is a $Q(x)$ on one side then $Q(a).G$ is the commitment of the Polynomial $Q$. How would you do this if $G_1 \ne G_2$? $\endgroup$
    – user93353
    Aug 21, 2023 at 6:10
  • $\begingroup$ As written in the answer any commitment is computed with $G_1$. In other words, polynomial evaluation at $a$ will use group elements from the first group. But that is a separate question than Correctness. $\endgroup$ Aug 21, 2023 at 6:39
  • $\begingroup$ I understand that commitments will use $G_1$. My question is about proof of correctness. I am able to derive proof of correctness when $G_1 = G_2$. I am unable to derive the same when $G_1 \ne G_2$ $\endgroup$
    – user93353
    Aug 21, 2023 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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