Score:1

Where & how is the 2nd group used in the KZG Commitment Scheme in case the 2 groups are not the same?

et flag

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.

Score:1
tr flag

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.

et flag
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.
Marc Ilunga avatar
tr flag
The proof is generally the same. We just need to use the bilinearity of the pairing. I'll develop this later.
et flag
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$?
Marc Ilunga avatar
tr flag
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.
et flag
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$
Marc Ilunga avatar
tr flag
If you apply the bilinearity of the pairing to both sides of the pairing equality equation what do you get?
et flag
Ok, I think I got it. Thank you.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.