Join Log in
Score:3
avatar Crypto

Question about the soundness of using a pairing map in the Kate Polynomial Commitment Scheme

et flag
user93353

I am looking at the paper on Kate Polynomial Commitments.

On Page 7, VerifyEval, the verifier checks the following to verify commitment.

$e(\mathcal C, g) \stackrel {?}{=} e(w_i, \frac {g(\alpha)}{g(i)})e(g, g)^{\phi(i)}$

In the next line, the paper explains why this equality will be true if the commitment is in fact honest.

I understand the completeness part of the proof, but I am not convinced about the soundness part.

Let the pairing map be

$e: G\space \times \space G \mapsto G_T$

Let $h_1, h_2, h_3, h_4$ be elements of $G$

Let $r_1$ & $r_2$ be elements of $G_T$.

$e(h_1, h_2) = r_1$

$e(h_3, h_4) = r_2$

If $h_1 = h_3$ & $h_2 = h_4$, then

$r_1 = r_2$

What we are checking in Commitment Scheme's VerifyEval is if $r_1 \stackrel {?}{=} r_2$

I agree this proves the completeness of the commitment.

However, I am not sure if it's proves the soundness.

Can't 2 different sets of elements when used as input to the pairing map end up with the same output element?

In the case where

$h_1 \ne h_3$ & $h_2 \ne h_4$, can't the output of the 2 mappings still be the same?

i.e. can't this be true still?

$e(h_1, h_2) = e(h_3,h_4)$

What property of elliptic curve pairings proves that the probability of $e(h_1, h_2)$ being equal to $e(h_3,h_4)$ is negligible in case $h_1 \ne h_3$ & $h_2 \ne h_4$?

99
1 + 0
Score:2
Daniel S avatar Crypto
ru flag
Daniel S

The chance of $e(h_1,h_2)$ equalling $e(h_3,h_4)$ for $h_1$, $h_2$, $h_3$ and $h_4$ selected independently and uniformly at random from $\mathbb G$ is $1/p$ where $p$ is the prime order of the groups in the pairing. This is because the output is uniform.

More germanely, if an adversary could reliably construct $\hat w$ and $\hat\phi$ such that $$e\left(\hat w,\frac{g^\alpha}{g^{i}}\right)e(g,g)^{\hat\phi}=e\left( w_i,\frac{g^\alpha}{g^{ i}}\right)e(g,g)^{\phi(i)}$$ then they would be able to convert this conctruction into a means to solve the Strong Diffie-Hellman (SDH) problem for the group $\mathbb G$. Solving this problem is believed to be hard in the group used in pairing-based cryptography. A demonstration of this is given in the appendix section C.1 in the Evaluation Binding subsection on pages 19 and 20.

+ 3
et flag
user93353
The notations used in your reply & in the document itself is a little confusing. Am I right in assuming that there are now two polynomials $\phi(x)$ & $\hat \phi(x)$ & both are evaluated at $\alpha$ & $i$ or is there also a different sampling value $\hat i$? Because your denominator of the left hand side, you also use $g$ raised to $\hat i$. In the Kate document, I don't see this.
0
Reply
Daniel S avatar
ru flag
Daniel S
@user93353 Apologies, the adversary would not have control of the $i$ value and so it should be the same on both sides. Their goal would be to create fake values for $\phi(i)$ and $w_i$ which I have labelled $\hat\phi$ and $\hat w$. I've edited out the $\hat i$.
0
Reply
et flag
user93353
Thank you for the quick response.
0
Reply
ธงชาติไทย
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.