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

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$$?

## 1 Answer

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.

• 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. Jan 18 at 6:55
• @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$. Jan 18 at 7:39
• Thank you for the quick response. Jan 18 at 7:41