# In the Kate/KZG Polynomial Commitment Scheme, in which Polynomial Ring should the polynomial to be committed be?

In the Kate Polynomial Commitment scheme, a commitment of a Polynomial $$f(x)$$ at $$x=s$$ is defined as

$$Com_f = f(s).G$$ where $$G$$ is the generator of the Elliptic Curve of prime order which is used.

So the polynomial to be committed, which Polynomial Ring should it be belong to?

Consider an Elliptic Curve $$E$$ defined over $$F_p$$. Let the order of the generator of Elliptic Curve which is used for the Commitment be the prime $$q$$. The Polynomial to be commited should be in $$F_q[x]$$ rather than in $$F_p[x]$$

If the polynomial which is committed is in $$F_p[x]$$ rather than in $$F_q[x]$$, then we run into the following problem.

Let's have

$$f_1 = a_0 + a_1x + ... + a_nx^n \in F_p[x]$$ &

$$f_2 = a_0 + a_1x + ... + a_nx^n \in F_q[x]$$

Let's say the Reference String for the polynomial is sampled at $$s$$ (here again I think $$s \in F_q$$)

Let $$f1(x=s) = v1$$ & $$f2(x=s) = v2$$.

Now $$v1.G$$ will not the be the same as $$(v1 \bmod p).G$$ while

$$v2.G$$ will be the same as $$(v2 \bmod q).G$$ like it should be.

So I think that the polynomial should be in the Ring $$F_q[x]$$. However, I don't find any text of the Kate Polynomial Commitment Scheme which explicitly talks about which ring the polynomial to be committed is in.

A secondary point here is if for the Kate PCS, is it recommended to always use an Elliptic Curve of prime order or is it ok to work with an Elliptic Curve of composite order also as long as you use the generator of a prime order subgroup?

• @fgrieu - I have edited the first line of the question where I incorrectly used $F(x)$ instead of $f(x)$. $F_p[x]$ & $F_q[x]$ are polynomial rings. $f$, $f_1$ & $f_2$ are polynomials. $q$ is the order of the generator $G$ of the Elliptic Curve $\#E(\mathbb F_p)$. My question is the polynomial to be committed $f(x) \in \mathbb F_p[x]$ or $f(x) \in \mathbb F_q[x]$ Jan 31 at 11:28
• @fgrieu - KGZ PCS is also called Kate PCS. The Kate commitment itself uses an Elliptic Curve Group. Verification of the Evaluation of the Polynomial at a different point using the commitment uses a bilinear pairing. I know all rings aren't fields - however, I think polynomial rings over fields are rings & not fields - i.e if $F$ is a field, then $F[x]$ is still a Ring - all elements in $F[x]$ don't have an inverse even if $F$ is a field. I have edited "polynomial ring of order of the Elliptic Curve" to "polynomial ring over the field of order of the Elliptic Curve" - is that satisfactory? Jan 31 at 12:59
• @fgrieu - if $\mathbb G$ is the Elliptic Curve group, then the pairing is $\mathbb G\times\mathbb G \mapsto \mathbb G_T$. The pairing is not used in the commitment part. It's used in the verification part only mainly because $s$ has been destroyed after the trusted setup phase. So the verifier uses the bilinearity property of pairings to rearrange the equation to verify, so he can verify it just by knowing $s^ng$ while not knowing $s$. Jan 31 at 15:05
• Minor comment, I believe you mean the KZG commitment scheme not the KGZ commitment scheme. Jan 31 at 17:51
• For reference, the conference paper is Aniket Kate, Gregory M. Zaverucha & Ian Goldberg's Constant-Size Commitments to Polynomials and Their Applications, in proceedings of Asiacrypt 2010. The extended version is titled Polynomial Commitments.
– fgrieu
Jan 31 at 18:16

An output of the setup algorithm in KZG is a description of a bilinear group which contains a description of three groups $$\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$$ (sometimes $$\mathbb{G}_T$$ is implicit and is omitted) and a pairing map $$e:\mathbb{G}_1\times\mathbb{G}_2\to\mathbb{G}_T$$. These groups all have the same prime order $$q$$. Because the additive groups, $$\mathbb{G}_1$$ and $$\mathbb{G}_2$$, have order $$q$$, the scalars belong to $$\mathbb{F}_q$$. Thus, the polynomial ring for which KZG is defined is $$\mathbb{F}_q[X]$$ (i.e. the univariate polynomial ring over a field of size $$q$$).
You can see this in the constructions given by the original KZG paper. Small note, in the original KZG paper, they use symmetric pairings where $$\mathbb{G}_1=\mathbb{G}_2$$; however, in practice, people use asymmetric pairings which are concretely more efficient. The KZG scheme can operate over either type of pairings so don't let that trip you up.