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

Question

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

Answer 1

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.