Join Log in
Score:2
avatar Crypto

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

et flag
user93353

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?

253
1 + 5
et flag
user93353
@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]$
1
Reply
et flag
user93353
@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?
1
Reply
et flag
user93353
@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$.
1
Reply
Wilson avatar
se flag
Wilson
Minor comment, I believe you mean the KZG commitment scheme not the KGZ commitment scheme.
1
Reply
fgrieu avatar
ng flag
fgrieu
For reference, the conference paper is Aniket Kate, Gregory M. Zaverucha & Ian Goldberg's [_Constant-Size Commitments to Polynomials and Their Applications_](https://link.springer.com/content/pdf/10.1007/978-3-642-17373-8_11.pdf?pdf=inline%20link), in [proceedings of Asiacrypt 2010](https://doi.org/10.1007/978-3-642-17373-8_11). The extended version is titled [_Polynomial Commitments_](https://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf).
0
Reply
Score:3
Wilson avatar Crypto
se flag
Wilson

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

+ 0
ธงชาติไทย
Elon Musk
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.