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?

  • 1
    $\begingroup$ @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]$ $\endgroup$
    – user93353
    Jan 31 at 11:28
  • 1
    $\begingroup$ @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? $\endgroup$
    – user93353
    Jan 31 at 12:59
  • 1
    $\begingroup$ @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$. $\endgroup$
    – user93353
    Jan 31 at 15:05
  • 1
    $\begingroup$ Minor comment, I believe you mean the KZG commitment scheme not the KGZ commitment scheme. $\endgroup$
    – Wilson
    Jan 31 at 17:51
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Jan 31 at 18:16

1 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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