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

Question

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?

Answer 1

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.

To answer your second question, KZG typically does not use "an elliptic curve of prime order." The most popular family of elliptic curves for pairings is BLS, and the pairing operates over prime order subgroups of composite order curve groups. The prime order part of a bilinear group is not to describe the order of the underlying elliptic curve, but to describe the order of the abstract groups in the pairing. A bilinear group makes no mention of an elliptic curve (even though the only constructions we know of come from elliptic curves).