0
$\begingroup$

Going through the literature led me to think I understood the difference between these two things, but thinking about I am not actually certain. Could you help me correct my definitions of these two things (or provide some more detail that aids understanding)?

Polynomial Commitment: This is an object created by evaluating the polynomial at a specific point. We are in a sense committed to the polynomial because the object was created using the structure of the polynomial.

Polynomial Opening: Revealing what a polynomial is, we open up the polynomial to be seen. We can for example use this to check a commitment.

For some context, taking the KZG polynomial commitment scheme, a polynomial commitment to $f(X)$ is $C = g^{f(\alpha)}$, where $\alpha$ is random and $g$ is the generator of some group. A polynomial opening is then just a presentation of $f(X)$?

$\endgroup$
1
  • $\begingroup$ Can you provide references to relevant papers that use these concepts? What is KZG? $\endgroup$
    – Mikero
    Feb 11 at 17:59
3
$\begingroup$

A Polynomial Commitment is a cryptographic object that binds a party, typically the prover, to a single polynomial. This object could be

  • an elliptic curve point, such as in KZG or Bulletproofs
  • en element of a group of unknown order, such as in DARK
  • the root of a Merkle tree of a Reed-Solomon codeword, such as in FRI.

The point is that underlying this cryptographic object there is a polynomial $f(X)$ that cannot be changed.

A Polynomial Opening of a commitment is the raw polynomial that the commitment represents, together with any auxiliary information needed to verify that the commitment is well formed and indeed a commitment to the given polynomial. The auxiliary information could be a randomizer in the case of semantically secure commitments, or information that is specific to the mechanics and mathematics of the commitment scheme.

The notions Polynomial Commitment and Polynomial Opening suffice to define the desired security property: Binding. Informally, it states that no realistic adversary can produce one commitment with two openings to different polynomials. More formally, for all probabilistic polynomial time adversaries $\mathcal{A}$, the probability that $\mathcal{A}$ outputs $(C, f_1(X), \mathit{aux}_1, f_2(X), \mathit{aux}_2)$ such that $f_1(X) \neq f_2(X)$ and $\mathsf{Verify}(C, f_1(X), \mathit{aux}_1) = \mathsf{True}$ and $\mathsf{Verify}(C, f_2(X), \mathit{aux}_2) = \mathsf{True}$, is negligible as a function of the security parameter.

Polynomial commitment schemes are only interesting when they come with an Evaluation Proof, which is a proof system that establishes that the value of the polynomial $f(X)$ in a point $z$ equals $y$, i.e., $f(z)=y$, where $f(X)$ is the polynomial that the given commitment $C$ commits to. Note that the verifier in this proof system does not need to know a full description of $f(X)$. In fact, polynomial commitment schemes are used precisely in a context where it would be too expensive for the verifier to read $f(X)$ from a complete description, let alone verify $f(z) = y$ directly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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