Score:1

What is the difference between those two KZG Polynomial Commitment Schemes?

cn flag

In short what are the differences (pros & cons) between multiplying by powers of Tau (from this lecture https://youtu.be/tAdLHQVW) from this lecture https://youtu.be/tAdLHQVWlUY

and raising to powers of Tau (from this lecture https://youtu.be/xuGQYEvytxk) from this lecture https://youtu.be/xuGQYEvytxk

I know pairing is used by the verifier in both, and that they deferred the pairing details to the next lecture to get a better understanding of the idea first, but I don't understand why they just switched to raising to powers of Tau instead of multiply; what is the cryptographic implications of that?

Ps

I've got two previous different answers, none was justified or convincing enough for me:

-one from CHATGPT that raising to powers of Tau leads to shorter proofs and less verifier time

-another one that they're both the same thing but different presentation (how come?)

Score:2
et flag

Both represent the same thing. The first one uses the additive notation & the 2nd one uses the multiplicative notation. That is the only difference.

KZG actually uses an Elliptic Curve Group, so in reality, it uses an additive group. However, even the original KZG paper uses the multiplicative notation in spite of the fact they are using an additive group. Note that this is just notation & in reality, the calculations will be done by the additive rules.

Additive Group

In an additive group with generator $G$, adding $G$ $n$ times results in $n\cdot G$

$G + G + G + ... + G = n\cdot G$

$\space\space$ |____ $n$ times ____|

Multiplicative Group

In a multiplicative group with generator $g$, multiplying $g$ $n$ times results in $g^n$

$g \star g \star g\star ... \star g = g^n$

|___ $n$ times ___|

Keeping the above in mind, if you look at your 2 descriptions they are essentially the same.

Take a polynomial $ F(x) = f_0 + f_1x + f_2x^2 + … + f_dx^d$

Commitment in an Additive Group

In an additive group, the commitment for this polynomial will be

$Com(F) = G\cdot F(\tau)$

$ = G\cdot (f_0 + f_1\tau + f_2{\tau}^2 + … + f_d{\tau}^d)$

$ = f_0(G) + f_1(G\cdot \tau) + f_2(G\cdot {\tau}^2) + … + f_d(G\cdot {\tau}^d)$

Even if the prover doesn't know the value of $\tau$, he knows the values of all the $G.{\tau}^n$ terms so he can calculate the commitment & send it to the verifier.

Commitment in a Multiplicative Group

In a multiplicative group, the commitment for this polynomial will be

$Com(F) = g^{F(\tau)}$

$ = g^{(f_0 + f_1\tau + f_2{\tau}^2 + … + f_d{\tau}^d)}$

$ = g^f_0 . g^{f_1\tau} . g^{f_2{\tau}^2} . … . g^{f_d{\tau}^d}$

Even if the prover doesn't know the value of $\tau$, he knows the values of all the $g^{{\tau}^n}$ terms so he can calculate the commitment & send it to the verifier.


KZG commitments actually work in an Elliptic Curve Group which is an additive group. However, sometimes cryptographers & mathematicians use a multiplicative notation when working with a group which has a single operation.

ShAr avatar
cn flag
So there's no added complexity for using the multiplicative group (probably raising to the power takes longer?), or lost security (soundness for example?) in using the additive group? One more thing: such details are in the KZG paper or in the Plonk paper?
et flag
@ShAr - KGZ is always implemented using Elliptic Curve Groups as the input groups. Elliptic Curve groups are additive. KGZ does not use a multiplicative group at all for the input groups. As I said, the paper just uses multiplicative notation to describe it. In a Pairing $G_1\space X\space G_2 \mapsto G_T$, the input groups $G_1$ & $G_2$ are always additive groups.
ShAr avatar
cn flag
You still didn't answer does raising to the powers of Tau (clearly more time complexity) adds more security compared to multiplying by powers of Tau?Or you are saying it is just the way it was done in the original paper, then latter uses found no security loss in multiplying by Tau (instead of raising to its powers) so they used it?
et flag
@ShAr - you cannot take powers of the generator or any elliptic in an Elliptic Curve Group. It doesn't have the multiplication operation at all. The Discrete Log Problem in an elliptic curve group is much harder than that in a multiplicative group of a finite field - this is because Index Calculus doesn't work in an Elliptic Curve Group.
et flag
@ShAr - also as I said, in the KGZ paper, when they write $g^n$, what they actually mean is $n\cdot g$ because the operation $g^n$ is not possible in an Elliptic Curve Group at all. The group doesn't even have a multiplicative operator
et flag
@ShAr - these Q & A explain why many cryptographers & mathematicians use multiplicative notation for groups even if the actual operation is addition - https://math.stackexchange.com/questions/1124996/why-is-multiplicative-notation-used-for-groups-instead-of-additive https://math.stackexchange.com/questions/2467930/groups-multiplicative-notation-in-additive-groups All this is from Abstract Algebra. Abstract Algebra abstracts away the operation - it doesn't matter whether you use the + or x operator
et flag
In an Elliptic Curve Group, addition is something artificially defined as addition - it's not addition like adding numbers - it's actually adding 2 points. Points in reality can't be added or multiplied like numbers are. So in Elliptic Curve Groups, there are complicated formulas on how to add points.
I sit in a Tesla and translated this thread with Ai:

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.