3
$\begingroup$

I have some issue to understand the verify round of the KZG polynomial commitment scheme. The following diagram is associated to the scheme. I appreciate any help.

To verify, the verifier should compute the pairing of $e(g^{f(\tau)-f(u)}, g)$ and $e(g^{\tau-u}, g^{q(\tau)})$.

However, to compute these pairings, verifier should compute $g^{f(\tau)-f(u)}$ and $g^{\tau-u}$ first. So, we see that $g^{f(\tau)-f(u)}=g^{f(\tau)}/g^{f(u)}$ and this is division of two points of the elliptic curve! However, the division of two elliptic curve points is not defined! We have the same issue with computing $g^{(\tau-u)}$ which is equal to $g^\tau/g^u$.

enter image description here

$\endgroup$
1
  • $\begingroup$ They are using multiplicative notation even though the Elliptic Curve is an additive group - it's a notation thing & not wrong - check this answer of mine - crypto.stackexchange.com/a/105778/3941 $\endgroup$
    – user93353
    May 20 at 3:38

1 Answer 1

5
$\begingroup$

In this lecture, they use multiplicative notation for the pairing groups instead of additive notation. Thus, division is well-defined. Division is just the inverse of the group operation.

The choice of additive vs multiplicative notation for a group is purely a semantic choice.

I'll translate some of the items to additive notation. The lowercase letters and symbols will be elements of the scalar field of the pairing group $\mathbb{G}$, while the capital $G$ will denote the generator of the group.

  • The commitment $\mathsf{com}_f = f(\tau) G$.
  • The element $vG$
  • The element $(\tau-u)G = \tau G - uG$
  • The subtraction will be $(f(\tau)-v)G = f(\tau)G - vG$.
  • The proof $\pi=q(\tau)G$
  • The pairing check $e\left(\mathsf{com}_f-vG,G\right)=e\left((\tau-u)G, \pi\right)$
$\endgroup$
4
  • $\begingroup$ Thanks for the explanation. If I want to use additive notation instead of multiplicative notation, would you help me to know how the formulas change? $\endgroup$
    – tesoke
    May 20 at 4:05
  • 1
    $\begingroup$ @tesoke I've added some of the notation changes. Does that help you? $\endgroup$
    – Wilson
    May 20 at 4:20
  • $\begingroup$ Thanks, yes it helps. But I think that the pairing should be as e(comf−vG,G)=e((τ−u)G,comq). Am I right? $\endgroup$
    – tesoke
    May 21 at 2:45
  • 1
    $\begingroup$ Yep, edited. Minor typo $\endgroup$
    – Wilson
    May 21 at 3:23

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.