3
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user93353
    Jan 18 at 6:55
  • $\begingroup$ @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$. $\endgroup$
    – Daniel S
    Jan 18 at 7:39
  • $\begingroup$ Thank you for the quick response. $\endgroup$
    – user93353
    Jan 18 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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