Exploring KZG polynomial commitments

Review: Constant-Size Commitments to Polynomials and Their Applications

This note answers a basic question: why should we use polynomial commitment schemes instead of existing commitment schemes like Pedersen commitments? While Pedersen commitments are well-suited for committing to message strings, they prove inefficient when we need to hide an entire polynomial while revealing only specific evaluation values. Moreover, if we commit to polynomial coefficients individually, the commitment size grows proportionally to the polynomial degree—a significant drawback. In essence, polynomial commitments address a crucial need in cryptographic protocols: hiding not just single values but entire collections of data or functions themselves while still proving their properties. Before examining polynomial commitment schemes, we need to understand Pedersen commitments.

1. Pedersen Commitment Scheme

"Individually..." Essentially, this is a commitment for single values—to commit to n values, you must create n independent commitments.

Assuming we have n messages m₁, m₂, ..., mₙ, we can express this as follows:

\begin{align} C_1 &= g^{m_1}h^{r_1} \ C_2 &= g^{m_2}h^{r_2} \ &\vdots \ C_n &= g^{m_n}h^{r_n} \end{align}

This generates n commitments (C₁, C₂, ..., Cₙ). To prove that mᵢ is correct, one must reveal rᵢ and verify that it matches Cᵢ.

Security Properties

Each Pedersen commitment fundamentally possesses hiding and binding properties:

• Hiding

  • From commitment $C_i$ alone, no information about message $m_i$ can be obtained.
  • Since one can select a different random value $r'_i$ to create $g^{m'_i}h^{r'_i} = C_i$ for $m'_i$, it's impossible to infer what $m_i$ is.

• Binding

  • The committed message $m_i$ is fixed based on the DLP. That is, changing $m_i$ to $m'_i$ while maintaining the same commitment $C_i$ is considered computationally infeasible.

• Opening and Verifying

  • To prove that $m_i$ is correct, the committer reveals the random value $r_i$ used along with the message $m_i$
  • The verifier checks whether $C_i = g^{m_i}h^{r_i}$ holds
  • Since each commitment is independent, opening or verifying one commitment has no effect on the commitments of other messages.

Limitations

This becomes particularly problematic when committing to polynomial coefficients. For example, if we individually commit to the coefficients $\varphi_0, \dots, \varphi_t$ of a polynomial $\varphi(x)$ of degree $t$, the total commitment size grows to $t+1$ group elements—increasing proportionally to the polynomial degree. This results in inefficient performance for certain cryptographic applications that require constant-size commitments (such as when revealing only polynomial evaluations while keeping the entire polynomial hidden). These limitations led to the emergence of new polynomial commitment schemes (PolyCommit_DL, PolyCommit_Ped).

2. Understanding the Concept

Why Are Pairings Necessary?

Without Pairings

Consider a typical ECC group $G$ with generator $g$. We can easily compute values like $g^a, g^b$.

1. What we can do: Verify addition/subtraction relationships in the exponent

   • We can check if $g^c$ equals $g^a \cdot g^b$ → This verifies the relationship $c = a + b$

2. What we cannot do: Verify multiplication/division relationships in the exponent

   • There's no direct way to verify if $g^c$ equals $g^{ab}$
   • Computing $g^{ab}$ from only $g^a, g^b$ without knowing $a, b$ is called the Computational Diffie-Hellman (CDH) problem—a very hard problem

In other words, we have no way to verify non-linear relationships like multiplication/division between values hidden in exponents.

With Pairings

$e(g^a, g^b) = e(g, g)^{ab}$ → The pairing of $g^a$ and $g^b$ equals the $ab$-th power of the pairing of $g$ with itself.

Verifying Multiplication Relationships in Exponents

Suppose someone claims "I know $a, b, c$ and these three numbers satisfy $c = ab$." They give the verifier $g^a, g^b, g^c$.

• Without pairings → We can only trust this claim
• With pairings → We can verify:
  • Compute $e(g^a, g^b)$ (result is $e(g,g)^{ab}$)
  • Compute $e(g, g^c)$ (result is $e(g,g)^c$)
  • Compare the two results

If they're equal, then $e(g,g)^{ab} = e(g,g)^c$, so we can be confident that $ab = c$ holds.

Bilinear Pairings

Next, let's examine bilinear pairings. The choice of pairing affects not only theoretical distinctions but also implementation efficiency and security models.

The notation we'll use:

• G (Source Group): The source group. Elements are typically represented as points on an elliptic curve
• $G_T$ (Target Group): The target group
• g: Generator of group G, meaning all elements of G can be created by repeated operations on g (e.g., g, g², g³, ...)
• e: A function that takes two elements from group G and outputs one element in group $G_T$

Bilinear pairings are broadly classified into three types.

Type 1: Symmetric Pairing

$e: G × G → G_T$ (e is a function that takes two elements from G and outputs one element in G_T)

Both input values $(P, Q)$ of the pairing function $e$ come from the same group G. That is, $P \in G$ and $Q \in G$. This is sometimes expressed as $G_1 = G_2 = G$.

Conceptually, the function $e: G × G → G_T$ must satisfy three properties:

Bilinearity

• For arbitrary integers $a, b$: $e(P^a, Q^b) = e(P, Q)^{ab}$ for all $P, Q \in G$
• Specifically with generator $g$: $e(g^a, g^b) = e(g, g)^{ab}$
• This property enables verification of multiplication relationships between values in exponents.

Non-degeneracy

• $e(g, g)$ is not the identity element of $G_T$. That is, $e(g, g) \neq 1$.
• Ensures pairing results don't always produce meaningless values
• Non-degeneracy guarantees that operation results aren't fixed to a meaningless 1, ensuring cryptographically significant values can be generated

Computability

• For given $P, Q \in G$, we can compute $e(P, Q)$ in polynomial time.

Type 2: Asymmetric Pairing

Type 1 can have inferior performance (element size, operation speed) compared to asymmetric pairings. Type 2 addresses these limitations.

$e: G₁ × G₂ → G_T$ (where $G₁ ≠ G₂$). This function takes one element from group G₁ and one element from group G₂ as inputs.

Type 2's special feature is the existence of an isomorphism $ψ: G₂ → G₁$ (psi takes an element from group $G₂$ and maps it to the corresponding element in G₁). This means elements from G₂ can be easily converted to elements in $G₁$.

The notation we'll use:

• $G₁, G₂$ (source groups): Two different groups
• $G_T$ (target group): The group containing pairing results
• $e$ (pairing function): $e(P, Q)$ where $P \in G_1, Q \in G_2$
• $ψ$ (isomorphism function)
  • $ψ: G₂ → G₁$
  • $ψ$ takes an element from G₂ and converts it to an element in G₁
  • $ψ$ preserves group structure: $ψ(Q_1 * Q_2) = ψ(Q_1) * ψ(Q_2)$

The existence of isomorphism $ψ$ is the most important distinction between Type 2 and Type 3.

The function $e: G_1 × G_2 → G_T$ still includes three properties, with the isomorphism affecting bilinearity:

Bilinearity

• With $g_1$ as generator of $G_1$ and $g_2$ as generator of $G_2$: $e(g_1^a, g_2^b) = e(g_1, g_2)^{ab}$
• Due to isomorphism $ψ$, relationships like $ψ(g_2) = g_1$ (or a power of $g_1$) hold

Vulnerability Due to $ψ$ Property

The existence of $ψ$ can create vulnerabilities to specific attacks, limiting its use in certain security models. Consider the following attack scenario:

Attack Scenario: $ψ$ Attack

• Assumption: The attacker knows $ψ$

• Goal: Break hash function $H_{G_2}$. For example, given $Q = H_{G_2}(m)$, the attacker wants to find $Q$'s discrete log—i.e., find $x$ where $Q = g_2^x$

• Scenario:

  1. First use a secure hash function $H_{G_1}$ that hashes to group G₁. The attacker computes $P = H_{G_1}(m)$. P is an element of G₁.
  2. Attempt to find P's discrete log $x$—i.e., find $x$ where $P = g_1^x$. This is the discrete logarithm problem (DLP), which is very hard. But what if the attacker somehow learns this x? (e.g., if the protocol is designed to reveal x for certain messages)
  3. (Attack): The attacker now directly computes $Q' = g_2^x$. This $Q'$ is an element of G₂.
  4. Apply isomorphism $ψ$ to $Q'$ to compute $ψ(Q')$. Since $ψ$ preserves group structure, $ψ(Q') = ψ(g_2^x) = (ψ(g_2))^x$. If $ψ(g_2) = g_1$, then $ψ(Q') = g_1^x = P$.
  5. The attacker can establish the relationship $ψ(g_2^x) = H_{G_1}(m)$. This means $g_2^x$ becomes a (preimage) by transferring the relationship of $H_{G_1}(m)$ in G₁ to G₂, breaking the independence between the two groups.

• G₁ and G₂ should originally be separate groups. What happens in G₁ shouldn't affect G₂, and vice versa

• But due to ψ's existence, relationships in G₁ (e.g., $P = g_1^x$) can be easily transferred to relationships in G₂ (e.g., $ψ(g_2^x) = P$)

• This means the discrete logarithm problems in groups G₁ and G₂ are not independent, and information from one side can leak to the other

Type 3: Asymmetric Pairing

To address the $ψ$ vulnerability of Type 2, Type 3 is used. Like Type 2, the two input values come from different groups G₁ and G₂. However, no efficiently computable isomorphism exists between G₁ and G₂. That is, we can assume that converting an element from one group to an element in the other group is as hard as the discrete logarithm problem.

3. Cryptographic Assumptions

Before diving into the KZG polynomial commitment scheme, I'll discuss the assumptions used in the security proofs of the PolyCommit_DL and PolyCommit_Ped schemes.

Discrete Logarithm Assumption

Let me remind you of the DL assumption:

$\Pr[A_{DL}(g, g^a)=a] = \varepsilon(\kappa)$

Given a generator $g$ of a cyclic group $G$ and a random element $h = g^x$ (where $x$ is a secret exponent), the probability that an attacker using a probabilistic polynomial-time (PPT) algorithm can find $x$ is a negligible function $\varepsilon(\kappa)$ that becomes arbitrarily small as the security parameter $\kappa$ grows sufficiently large.

What is the significance of the DL assumption?

While computing $g^a$ given $g$ and $a$ (modular exponentiation) can be performed efficiently in polynomial time (e.g., using "repeated squaring" or "Montgomery ladder exponentiation"), computing $a$ in reverse given $g$ and $g^a$ (finding the discrete log) has no known efficient general algorithm that can solve it in polynomial time with current computing resources. This assumption of "computational difficulty" serves as the core foundation supporting the security of many public-key cryptosystems like the Diffie-Hellman key exchange protocol. The Hiding property of the PolyCommit_DL scheme can be proven based on the DL assumption.

t-Polynomial Diffie-Hellman (t-polyDH) Assumption

This is a cryptographic assumption stating that certain computational problems are difficult to solve efficiently in specific group settings. This assumption is a generalized form of the t-Diffie-Hellman Inversion (t-DHI) assumption, and is considered stronger than the t-DHI assumption, especially for large values of t.

To understand this, let me explain step by step how t-polyDH works. For each step, I'll explain using three aspects: "Given", "Problem to solve", and "Meaning".

Step 1: Generalization - t-Diffie-Hellman Inversion Problem (t-DHI)

This explains t-DHI, the immediate predecessor of t-polyDH.

• Given: $g, g^{\alpha}, g^{\alpha^2}, ..., g^{\alpha^t}$ (t powers of α)
• Problem to solve: Compute $g^{1/\alpha}$
• Meaning: Even knowing polynomial values up to degree $t$ of $\alpha$ in the exponent, computing the inverse $(1/\alpha)$ in the exponent remains difficult.

Therefore, t-DHI quantifies the "difficulty of inversion attacks" as a basic assumption that can support the binding security of pairing-based schemes like polynomial commitments.

Polynomial Commitment Binding: In PolyCommit_DL (KZG), when ensuring that an attacker cannot extract $\phi(\alpha)$ or $\alpha$ from a polynomial $\phi$'s commitment value $C=g^{\phi(\alpha)}$ to arbitrarily modify $C$, we can prove binding using the t-DHI hardness ("the fraction $1/\alpha$ cannot be computed").

Step 2: Final - t-Polynomial Diffie-Hellman Problem (t-polyDH)

Looking at this assumption again, it extends the previous t-DHI problem to a more general polynomial form. In other words, t-polyDH is a hardened assumption that encompasses t-DHI.

• Given: $g, g^\alpha, g^{\alpha^2}, ..., g^{\alpha^t}$ (For a secret value $\alpha$, this is equivalent to receiving evaluations of polynomials $x, x^2, ..., x^t$ in the exponent of $g$)
• Problem to solve: Find the following pair $(φ(x), g^{φ(\alpha)})$
  • $φ(x)$: A freely chosen new polynomial
  • Condition: The degree of $φ(x)$ must be greater than $t$ (restricted to $t < \deg(φ) < 2^\kappa$)
  • $g^{φ(\alpha)}$: The value obtained by evaluating the chosen polynomial $φ(x)$ at the secret value $\alpha$ and placing it in the exponent of $g$

The conclusion is that even if an attacker freely chooses a polynomial $φ(x)$ of degree higher than $t$, it remains difficult to produce the correct computational result $g^{φ(\alpha)}$.

Role in KZG Polynomial Commitments

This assumption ensures the Strong Correctness property of KZG commitments—that the Committer cannot lie about the polynomial's degree.

Let's think about it:

1. The system's public key ($PK$) is $(g, g^\alpha, ..., g^{\alpha^t})$. This system is designed to handle polynomials up to degree $t$ only.
2. Assume an attacking Committer wants to commit to a polynomial $φ'(x)$ of degree higher than $t$ (e.g., degree $t+1$).
3. To compute the commitment, they need to calculate $C = g^{φ'(\alpha)}$.
4. However, since $φ'(x)$ is a degree $t+1$ polynomial, computing $g^{φ'(\alpha)}$ using its coefficients requires the term $g^{\alpha^{t+1}}$, which is not in the public key.
5. Therefore, the attacker faces the difficulty of computing $g^{φ'(\alpha)}$ using only the public key $(g, g^\alpha, ..., g^{\alpha^t})$.

t-Strong Diffie-Hellman (t-SDH) Assumption

This assumption states that certain computational problems are difficult for efficient attackers to solve. This assumption is more hardened than the t-Diffie-Hellman Inversion (t-DHI) assumption and has the characteristic that it can have "exponentially many non-trivially different solutions."

Please read the explanation from the t-SDH assumption onward with a focus on the security hardening perspective.

As a stronger assumption used to guarantee the binding property of the PolyCommit_DL/KZG scheme, it can be defined as follows:

• Select a cyclic group $G$ of order $p$ and generator $g$ according to security parameter $\kappa$
• Choose a secret trapdoor value $\alpha \in \mathbb{Z}_p$
• Distribute public parameters $(g, g^\alpha, g^{\alpha^2}, \dots, g^{\alpha^t})$

The assumption that the probability of an attacker finding both an arbitrary $c \in \mathbb{Z}_p$ and $g^{\frac{1}{\alpha+c}}$ pair simultaneously, given only the public $(g, g^\alpha, \dots, g^{\alpha^t})$, is negligible.

That is, $\Pr[\mathcal{A}_{t-SDH}(g, g^\alpha, \dots, g^{\alpha^t}) = \langle c, g^{1/(\alpha+c)} \rangle] = \varepsilon(\kappa)$

• $c$: An arbitrary value that the attacker can freely choose
• $g^{1/(\alpha+c)}$: A group element with the inverse of "$\alpha+c$" as the exponent

Why is it Harder than t-DHI?

• t-DHI assumes the difficulty of only the case where "c=0", i.e., finding only $g^{1/\alpha}$
• t-SDH prevents creating $g^{1/(\alpha+c)}$ for all values of c, thus covering a broader range where the attacker can freely choose c.

To arbitrarily forge a commitment $C=g^{\phi(\alpha)}$ in PolyCommit_DL (KZG)?

An attacker would need to create a form like $g^{1/(\alpha+c)}$ by choosing $c=-y$ with a polynomial like $\phi(x)-y$.

If the t-SDH assumption holds, all such forgery attempts become negligibly difficult.

Ultimately, t-SDH is the core security premise that ensures arbitrarily manipulating committed polynomial opening values (or evaluation proofs) cannot go undetected.

From the Attacker's Perspective

• Input
  • The attacker receives a (t+1)-tuple $\langle g, g^\alpha, g^{\alpha^2}, \ldots, g^{\alpha^t} \rangle \in G^{t+1}$ for a randomly selected $\alpha \in \mathbb{Z}^*_p$. Here, $g$ is the generator of group $G$.
• Attacker's Goal
  • Based on this input, the attacker must output a pair $\langle c, g^{1/(\alpha+c)} \rangle$ for an arbitrary value $c \in \mathbb{Z}_p \setminus \{-\alpha\}$. That is, they must find a specific form of inverse value without knowing $\alpha$.
• Success Probability
  • The probability that the attacker ($\mathcal{A}_{t-SDH}$) solves this problem must be negligibly small ($\varepsilon(\kappa)$), where $\varepsilon(\kappa)$ denotes a negligible function with respect to the security parameter $\kappa$.

What if the attacker chooses c=0?

If the attacker chooses c=0, the problem to solve becomes t-DHI itself. If t-SDH holds, then the t-DHI hardness is naturally satisfied as well.

t-Bilinear Strong Diffie-Hellman (t-BSDH) Assumption

This security assumption can be viewed as the bilinear pairing version of the previously explained t-SDH assumption. I'll explain this assumption through comparison with t-SDH.

As you can see, only the result the attacker must produce has changed from a power of $g$ to a power of $e(g, g)$—the fundamental structure of the problem remains the same.

In t-BSDH, one must find the following pair $(c, z)$:

• $c$: A chosen number (where $c \neq -\alpha$)
• $z$: A value satisfying $z = e(g, g)^{1/(\alpha+c)}$ (This value $z$ is an element of group G_T)

"Given $g, g^\alpha, ..., g^{\alpha^t}$, no attacker can efficiently compute a valid pair of the form $(c, e(g, g)^{1/(\alpha+c)})$ (the probability is negligibly small)."

This essentially assumes that if the t-SDH problem is hard, then finding the paired value of that result would also be hard.

Role in KZG Polynomial Commitments

The t-BSDH assumption guarantees the Binding property of Batch Opening in KZG commitments.

Batch Opening: An efficient method to bundle proofs for evaluations at multiple points $(i_1, y_1), (i_2, y_2), \dots$ into a single witness and verify them all at once.

Potential Attack Scenario

1. The Committer publishes the commitment $C$.
2. Subsequently, the Committer claims through Batch Opening that "the polynomial values at the set of points $B$ match $r(x)$."
3. If a malicious Committer attempts to deceive in this Batch Opening, it becomes a more complex attack than forging a single-value proof.
4. The Batch Opening verification equation involves multiple pairing terms, resulting in a more intricate form.
5. Successfully breaching this complex verification equation mathematically implies that the attacker can solve the t-BSDH problem.

Because the t-BSDH assumption holds—that is, solving the t-SDH problem in the pairing space is difficult—the attacker cannot deceive in Batch Opening. Therefore, even when opening multiple values at once, the contents remain bound.

In conclusion, t-SDH and t-BSDH can be understood as nearly identical assumptions. The key differences are as follows:

• t-SDH → Security for single opening
• t-BSDH → Security for batch opening

4. Polynomial Commitment Scheme

In this section, we'll explore how the six algorithms—Setup, Commit, CreateWitness, VerifyEval, and others—form the complete KZG system.

Building Blocks

The Committer generates a short commitment $C$ for their chosen secret polynomial $\phi(x)$ and publishes it. Later, they must prove to the Verifier that a specific evaluation $y = \phi(i)$ at point $i$ is correct using a witness $w$, without revealing the secret polynomial $\phi(x)$ itself.

In polynomial commitments, the Committer and Prover can be considered the same entity.

Committer

• Selects their secret polynomial $\phi(x)$.
• Uses the Commit algorithm to convert it into $C$ and publishes it.
• "I've set a certain polynomial inside this $C$, and I won't change my story later"—this is the commitment part.

Prover

• When the Verifier requests the evaluation at a specific point $i$,
• Computes $\phi(i)$ and generates witness $w_i$ using the CreateWitness algorithm to prove its correctness.
• Sends the tuple $(i, \phi(i), w_i)$ to the Verifier to prove it.

To achieve these goals, the polynomial commitment scheme consists of the following six algorithms.

Before explaining these six algorithms, I'll structure the discussion around the points of "Purpose," "Input," and "Output" for each.

1. $Setup(1^\kappa, t)$

• Purpose: Sets up the public environment needed to use the commitment scheme; this is executed only once for the entire system.
• Input:
  • $1^\kappa$: The security parameter (κ-bit), where a larger number increases the system's security level.
    • Takes the security parameter κ and the maximum polynomial degree $t$ as input → This generates the Structured Reference String (SRS).
  • $t$: The maximum degree of polynomials the system can handle.
• Output → $\langle PK, SK \rangle$ pair
  • Public Key (PK): Publicly available information needed for creating and verifying commitments ("Public Parameters") (e.g., $g, g^\alpha, \dots, g^{\alpha^t}$).
  • Secret Key (SK): A secret value used only during the Setup phase (e.g., $\alpha$). After Setup, this secret key is no longer needed in the scheme, so it can be discarded—this is known as a "trusted setup."
    • If the publicly agreed-upon values from the trusted setup are not discarded, it can lead to security issues, often referred to as "cryptographic toxic waste."

2. $Commit(PK, \phi(x))$

• Purpose: The Committer generates a commitment $C$ for their polynomial $\phi(x)$.
• Input:
  • $PK$: The public key generated from Setup.
  • $\phi(x)$: The polynomial to commit to (degree at most $t$).
• Output:
  • $C$: The commitment to the polynomial (e.g., $g^{\phi(\alpha)}$ → a single group element).
  • $d$: Additional information needed for commitment opening (not used in the basic configuration).

3. $Open(PK, C, \phi(x), d)$

• Input:
  • Public key $PK$, commitment $C$, polynomial $\phi(x)$, and related decryption information $d$.
• Output:
  • The committed polynomial $\phi(x)$ → Can be implemented as a public coin protocol between the Prover (PPC) and Verifier (VPC).

4. $VerifyPoly(PK, C, \phi(x), d)$

• Purpose: The Committer proves that commitment $C$ corresponds to the entire polynomial $\phi(x)$, and the Verifier confirms this. This is a stronger form of opening than revealing only specific values.
• Input:
  • Verifies whether $C$ is a commitment to $\phi(x)$ along with $d$.
• Output:
  • VerifyPoly returns 1 (success) or 0 (failure) as the verification result.

5. $CreateWitness(PK, \phi(x), i, d)$

• Purpose: Generates a 'witness' to reveal and prove only the evaluation $\phi(i)$ at a specific point $i$, without revealing the entire polynomial.
• Input:
  • $PK$: Public key.
  • $\phi(x)$: The original polynomial (known only to the Committer).
  • $i$: The point to evaluate (x-coordinate).
• Output:
  • $(i, \phi(i), w_i)$: The tuple to reveal.
    • $i$: Evaluation point.
    • $\phi(i)$: Evaluation value at $i$ (y-coordinate).
    • $w_i$: The witness proving that $\phi(i)$ is the correct evaluation value.

6. $VerifyEval(PK, C, i, y, w_i)$

• Purpose: The Verifier checks whether the evaluation value $y$ presented by the Committer is indeed the i-th evaluation ($\phi(i)$) of the polynomial corresponding to commitment $C$. The Verifier does this without knowing $\phi(x)$, using only $C$ and public information.
• Input:
  • $PK$: Public key.
  • $C$: The previously published commitment.
  • $i, y, w_i$: The (evaluation point, evaluation value, witness) presented by the Committer.
• Output: 1 (success) or 0 (failure).

Security Requirements

For the above algorithms to operate securely, they must satisfy the following three properties.

1. Correctness
   1. Honest users following the protocol must always succeed.
   2. If the Committer honestly generates $C$ and $w_i$, the Verifier must always return 1 (success) when executing VerifyPoly and VerifyEval. This is the most fundamental requirement of the system.
2. Binding
   1. Once committed, one cannot change their story later.
   2. This property prevents malicious Committers from cheating and is divided into two levels.
      • Polynomial Binding → Keeping protection
        • A malicious Committer cannot create a single commitment $C$ and later claim "This $C$ is for $\phi(x)$" while also successfully claiming "Actually, it's for a different polynomial $\phi'(x)$." In other words, $C$ must be fixed to one polynomial.
      • Evaluation Binding
        • This is more practically important: A malicious Committer cannot, for a single commitment $C$ and specific point $i$, claim "The evaluation is $y$" with a valid witness $w$ while also claiming "The evaluation is a different $y'$" with a valid witness $w'$. That is, the evaluation value for the pair $(C, i)$ must be unique.
3. Hiding
   • One cannot learn the original secret information just by looking at the commitment.
   • Even if a malicious Verifier sees the commitment $C$, they must not be able to extract any information about the original polynomial $\phi(x)$.
   • More specifically, even if fewer than the polynomial's degree (t) evaluation values $(i, \phi(i))$ are revealed, it must be impossible to guess the evaluation $\phi(j)$ at an unrevealed point $j$.
     • Computational Hiding: Attackers with limited computational power cannot extract the information.
     • Unconditional Hiding: Even attackers with unlimited computational power cannot extract the information (similar to Pedersen commitments).

Practical Implementation: Ethereum KZG Ceremony

The trusted setup described in the Setup algorithm, where the secret $\alpha$ must be securely discarded to prevent cryptographic vulnerabilities, is critical for KZG commitments. In practice, generating the Structured Reference String (SRS) without relying on a single trusted party is achieved through multi-party computation (MPC). A prominent example is Ethereum KZG Ceremony (2023), which supported the Dencun upgrade (EIP-4844) for scalable data availability in Layer 2 rollups. Over 140,000 participants globally contributed randomness via a public protocol (https://ceremony.ethereum.org/), ensuring $\alpha$ remains unknown as long as at least one contributor deletes their secret. This decentralized approach eliminates the "trusted authority" risk, aligning with the security requirements of PolyCommit_DL and enabling efficient, secure polynomial commitments in blockchain applications.

5. PolyCommit_DL Design Rationale

In this section, we'll explore how the abstract requirements of the polynomial commitment scheme defined earlier are implemented using concrete mathematical methods. I've implemented a Proof of Concept (POC) for this scheme and analyzed its operational process, which I'll explain here.

Concept

For any polynomial $\phi(x)$ and arbitrary constant $i$, $x - i$ always divides the new polynomial $\phi(x) - \phi(i)$ exactly.

(By the factor theorem for polynomials, when $x = i$, the value of $\phi(x) - \phi(i)$ is $\phi(i) - \phi(i) = 0$, so $(x - i)$ must be a factor.)

Therefore, the quotient polynomial $\psi_i(x) = (\phi(x) - \phi(i)) / (x - i)$ always exists.

PolyCommit_DL implements this property over groups where bilinear pairings are possible. That is, it is based on the algebraic attribute that $(x - i)$ perfectly divides $\phi(x) - \phi(i)$ for the polynomial $\phi(x)$.

1. $Setup(1^\kappa, t)$

1. Select groups $G$ and $G_T$ where a bilinear pairing $e: G \times G \to G_T$ is defined ($p$ is the prime order of the group).
2. Choose a generator $g$ of $G$.
3. A Trusted Authority randomly selects a secret value $\alpha \in \mathbb{Z}_p$ (alpha), and this $\alpha$ must remain unknown to everyone.
   • Computations and Outputs:
     • $SK$ (Secret Key): $\alpha$ (must be discarded immediately after generation).
     • $PK$ (Public Key): $(G, g, g^\alpha, g^{\alpha^2}, \dots, g^{\alpha^t})$.
       • This public key is a tuple of group elements where powers of $\alpha$ are placed in the exponent of $g$.
       • $\alpha$ cannot be recovered from these values alone (due to the hardness of the discrete logarithm problem).
       • This public key is shared by all participants in the system and constitutes a "trusted setup."

POC Implementation Notes

• For the initial environment, using a primitive root as the generator is preferable, but for this POC, we assume a value of 2.
  • Implements polynomial division over finite fields.
  • Uses modular arithmetic instead of actual elliptic curves.
• Setup($1^\kappa, t$) → ($\mathit{PK}, \mathit{SK}$):
  • Trusted setup: Computes powers of $\alpha$ and discards $\alpha$.
    • Args:
      • security_param: Security parameter $\kappa$.
      • max_degree: Maximum supported polynomial degree $t$.
    • Returns:
      • PK: Public key [$g, g^\alpha, g^{\alpha^2}, \dots, g^{\alpha^t}$].
      • SK: Secret key $\alpha$ (returned for simulation purposes; in practice, discarded immediately).
  • Randomly selects secret value $\alpha$ (avoiding 0 and 1).
  • Generates public key: [$g, g^\alpha, g^{\alpha^2}, \dots, g^{\alpha^t}$].
    • Exponents are computed modulo $(p-1)$ using Fermat's Little Theorem.

  def __init__(self, prime: int = 2**61 - 1):
      self.p = prime
      self.g = 2
      print(f"p = {self.p}")
      print(f"g = {self.g}")
 
  def mod_inverse(self, n: int) -> int:
      return pow(n, -1, self.p)
 
  def Setup(self, security_param: int, max_degree: int) -> Tuple[List[int], int]:
      print(f"\n[Setup] max degree t = {max_degree}")
      alpha = random.randint(2, self.p - 2)
      print(f"secret vlaue α = {alpha}")
      PK = []
      for i in range(max_degree + 1):
          alpha_i = pow(alpha, i, self.p - 1)
          g_alpha_i = pow(self.g, alpha_i, self.p)
          PK.append(g_alpha_i)
      
      print(f"generated Public Key: {len(PK)}")
      return PK, alpha

2. $Commit(PK, \phi(x))$

• Input: Public key $PK$, polynomial to commit $\phi(x) = \phi_0 + \phi_1 x + \dots + \phi_t x^t$.
• Computation:
  • The Committer needs to evaluate $\phi(x)$ at the secret value $\alpha$ to get $\phi(\alpha)$, but since they don't know $\alpha$, direct computation is impossible.
  • Instead, use the public key $PK$ to compute $g^{\phi(\alpha)}$.
    • $g^{\phi(\alpha)} = g^{\phi_0 + \phi_1 \alpha + \dots + \phi_t \alpha^t}$
    • $= g^{\phi_0} \cdot g^{\phi_1 \alpha} \cdot \dots \cdot g^{\phi_t \alpha^t}$
    • $= (g)^{\phi_0} \cdot (g^\alpha)^{\phi_1} \cdot \dots \cdot (g^{\alpha^t})^{\phi_t}$
  • Since $g, g^\alpha, \dots, g^{\alpha^t}$ are all publicly available in $PK$, the Committer can take these values, raise them to the powers of their coefficients $\phi_0, \dots, \phi_t$, and multiply them together to obtain $g^{\phi(\alpha)}$.
• Output:
  • Commitment $C = g^{\phi(\alpha)}$.
  • No matter how large the polynomial degree $t$ is, the commitment $C$ is a single element of group $G$. This achieves the "constant-size commitment."

POC Implementation Notes Commit($PK, \phi(x)$) → $C$

• Commits to the polynomial $\phi(x) = \phi_0 + \phi_1 x + \dots + \phi_t x^t$.
• Args:
  • PK: Public key.
  • coeffs: Polynomial coefficients $[\phi_0, \phi_1, \dots, \phi_t]$ (all less than $p$).
• Returns:
  • C: Commitment $g^{\phi(\alpha)}$.
• Initialize C=1, then implement $C = g^{\phi(\alpha)} = \prod (g^{\alpha^i})^{\phi_i} \pmod{p}$.

def Commit(self, PK: List[int], coeffs: List[int]) -> int:
    degree = len(coeffs) - 1
    print(f"\n[Commit] poly degree: {degree}")
    C = 1
    for i, coeff in enumerate(coeffs):
        if i >= len(PK):
            raise ValueError("exceed")
        term = pow(PK[i], coeff, self.p)
        C = (C * term) % self.p
    print(f"Commitment C = {C}")
    return C

3. $CreateWitness(PK, \phi(x), i)$

• Purpose: The process of creating evidence that the evaluation $y = \phi(i)$ at point $i$ is correct.
• Computation:
  1. The Committer first computes the quotient polynomial $\psi_i(x) = (\phi(x) - \phi(i)) / (x - i)$. Since $\phi(x)$ is represented by its coefficients, this computation can be easily performed through polynomial division.
  2. Using the exact same method as in Commit, compute $w_i = g^{\psi_i(\alpha)}$ for this new quotient polynomial $\psi_i(x)$.
• Output: $(i, \phi(i), w_i)$
  • $w_i$ is the "witness," and it too is a single element of group $G$.

POC Implementation Notes: CreateWitness(PK, \phi(x), i) → (i, \phi(i), w_i)

• Args:
  • PK: Public key.
  • coeffs: Polynomial coefficients.
  • i: Evaluation point.
• Returns: (i, y, w_i): Evaluation point, evaluation value, witness.

1. Compute $\phi(i)$ (polynomial evaluation over finite fields). 2. self._evaluate_poly(coeffs, i)
2. Compute quotient polynomial $\psi_i(x) = (\phi(x) - \phi(i)) / (x - i)$, with dividend: $\phi(x) - y$.

phi_minus_y = list(coeffs)
phi_minus_y[0] = (phi_minus_y[0] - y + self.p) % self.p

3. Compute divisor $(x - i)$ as coefficients $[-i, 1]$:

• x_minus_i = [(-i + self.p) % self.p, 1] to handle modular arithmetic.

4. Compute witness $w_i = g^{\psi_i(\alpha)}$:

• w_i = self.Commit(PK, psi_coeffs) using the Commit algorithm with the coefficients of $\psi_i(x)$.

def polynomial_division_field(self, dividend: List[int], divisor: List[int]) -> Tuple[List[int], List[int]]:
    rem = list(dividend)
    deg_rem = len(rem) - 1
    deg_div = len(divisor) - 1
 
    if deg_div < 0:
        raise ValueError("not zero.")
    
    quot = [0] * (deg_rem - deg_div + 1)
    lead_div_inv = self.mod_inverse(divisor[-1])
 
    for i in range(deg_rem - deg_div, -1, -1):
        if len(rem) - 1 < i + deg_div:
            continue
        
        coeff = (rem[i + deg_div] * lead_div_inv) % self.p
        quot[i] = coeff
        
        for j in range(deg_div + 1):
            rem[i + j] = (rem[i + j] - coeff * divisor[j]) % self.p
    while len(rem) > 1 and rem[-1] == 0:
        rem.pop()
    
    return quot, rem
 
def _evaluate_poly(self, coeffs: List[int], x: int) -> int:
    y = 0
    for i, coeff in enumerate(coeffs):
        y = (y + coeff * pow(x, i, self.p)) % self.p
    return y
 
def CreateWitness(self, PK: List[int], coeffs: List[int], i: int) -> Tuple[int, int, int]:
    print(f"\n[CreateWitness] evaluation point i = {i}")
 
    y = self._evaluate_poly(coeffs, i)
    print(f"φ({i}) = {y} (mod {self.p})")
 
    phi_minus_y = list(coeffs)
    phi_minus_y[0] = (phi_minus_y[0] - y + self.p) % self.p
 
    x_minus_i = [(-i + self.p) % self.p, 1]
    
    psi_coeffs, remainder = self.polynomial_division_field(phi_minus_y, x_minus_i)
 
    if not (len(remainder) == 1 and remainder[0] == 0):
         print(f"remainder is no zero : {remainder}")
    
    print(f"ψ_i(x) coeffs: {len(psi_coeffs)-1}")
 
    w_i = self.Commit(PK, psi_coeffs)
    
    print(f"Witness w_i = {w_i}")
    return i, y, w_i

4. $VerifyEval(PK, C, i, y, w_i)$

• Purpose: The Verifier uses the $(i, y, w_i)$ received from the Committer along with the previously received commitment $C$ to confirm whether $y = \phi(i)$ truly holds. The Verifier does not know $\phi(x)$ itself.
• Verification Logic:
  • The Verifier checks whether the following equation holds:

    $e(C, g) = e(w_i, g^\alpha / g^i) \cdot e(g, g)^y$

• Why Does This Equation Hold?
  1. The core idea is that evaluating $\phi(x) = \psi_i(x) \cdot (x - i) + \phi(i)$ at $\alpha$ gives $\phi(\alpha) = \psi_i(\alpha) \cdot (\alpha - i) + \phi(i)$.
  2. Raising this equation to the exponent of $g$ yields $g^{\phi(\alpha)} = g^{\psi_i(\alpha) \cdot (\alpha - i) + \phi(i)}$.
  3. Since $C = g^{\phi(\alpha)}$ and $w_i = g^{\psi_i(\alpha)}$, this resembles $C = w_i^{\alpha - i} \cdot g^y$ (by exponent rules).

  We cannot verify this relationship directly, so we apply the bilinear map $e$ to both sides to transform it into a verifiable form. Left Side: $e(C, g) = e(g^{\phi(\alpha)}, g) = e(g, g)^{\phi(\alpha)}$ Right Side: $e(w_i, g^\alpha / g^i) \cdot e(g, g)^y$ - $= e(g^{\psi_i(\alpha)}, g^{\alpha - i}) \cdot e(g, g)^y$ - $= e(g, g)^{\psi_i(\alpha) \cdot (\alpha - i)} \cdot e(g, g)^y$ - $= e(g, g)^{\psi_i(\alpha) \cdot (\alpha - i) + y}$ (assuming $y = \phi(i)$ is correct) - $= e(g, g)^{\psi_i(\alpha) \cdot (\alpha - i) + \phi(i)}$ - $= e(g, g)^{\phi(\alpha)}$ (by the core idea)

In conclusion, left side = right side holds. If the Committer fabricates the $y$ value or creates an incorrect $w_i$, this equation will fail to hold with very high probability.

POC Implementation Notes

• For VerifyEval testing, we verify the equation directly at the exponent level instead of using pairings. This function aims to recover the secret value $\alpha$ for verification purposes.
• Verification equation: $e(C, g) = e(w_i, g^\alpha / g^i) \cdot e(g, g)^y$
• Simplified → $g^{\phi(\alpha)} == (g^{\psi_i(\alpha)})^{(\alpha - i)} \cdot g^y$

Final Implementation Check

• Polynomial: $\phi(x) = 3x^2 + 2x + 1$
• Secret Value: $\alpha = 481184019$
• Evaluation Point: $i = 4$

1. Commitment $C$:
   • $C = g^{\phi(\alpha)} = 2^{(3\alpha^2 + 2\alpha + 1)} \pmod{p}$
   • $C = 348765865$
2. Evaluation $y = \phi(4)$:
   • $y = 3 \cdot 4^2 + 2 \cdot 4 + 1 = 3 \cdot 16 + 8 + 1 = 48 + 8 + 1 = 57$
   • $\phi(4) = 57$
3. Quotient Polynomial $\psi(x)$:
   • $\psi(x) = (\phi(x) - \phi(4)) / (x - 4)$
   • $= (3x^2 + 2x + 1 - 57) / (x - 4)$
   • $= (3x^2 + 2x - 56) / (x - 4)$
   • $= (3x + 14)(x - 4) / (x - 4) = 3x + 14$
   • The quotient polynomial $\psi_i(x)$ is of degree 1, confirming the output check.
4. Witness $w_i$:
   • $w_i = g^{\psi(\alpha)} = 2^{(3\alpha + 14)} \pmod{p}$
   • Re-calling the Commit function yields $w_i = 559735160$, matching this result.
5. Verification:
   • LHS (Left Side): $C = 348765865$
   • RHS (Right Side): $(w_i)^{(\alpha - i)} \cdot g^y = (559735160)^{(\alpha - 4)} \cdot 2^{57} \pmod{p}$
   • The output shows LHS and RHS values exactly match at 348765865.
   • Checked based on the equation $g^{\phi(\alpha)} == g^{(\psi(\alpha) \cdot (\alpha - i) + y)}$.

Attack Scenario Check

• Assume the commitment $C$ and witness $w_i$ are generated honestly.
• However, the Committer sends a fabricated $y = 58$ instead of 57 to the Verifier. Verification:
  • LHS (Left Side): $C = 348765865$ (unchanged).
  • RHS (Right Side): $(w_i)^{(\alpha - i)} \cdot g^{(\textit{fake\_y})} = (559735160)^{(\alpha - 4)} \cdot 2^{58} \pmod{p}$.
  • Since $y$ changed from 57 to 58, the $g^y$ term in the right side shifts from $g^{57}$ to $g^{58}$, effectively multiplying the original right side by an extra $g(=2)$.
    • $697531730 = 348765865 \cdot 2 \pmod{1000000007}$ → This relation holds.
  • As a result, LHS and RHS values differ, and the verification output is: failure. This confirms that the scheme's Binding property is functioning correctly.

In Summary

Since both the commitment and witness are constant size (O(1)), communication efficiency is very high. From a security perspective, not being able to recover $\phi(x)$ from just $C = g^{\phi(\alpha)}$ relies on the hardness of the discrete logarithm (DL) problem (specifically, when fewer than $t$ points are revealed). The inability of the Committer to use fakes relies on the hardness of the t-SDH assumption. In other words, creating two different valid evaluations $(y, w)$ and $(y', w')$ for a single $C$ is as difficult as solving the t-SDH problem.

The PolyCommit_DL construction is the most basic form of the KZG (or Kate) commitment used in modern zero-knowledge proof systems.

6. PolyCommit_Ped Design Rationale

As the name suggests, "Ped" indicates that this scheme draws inspiration from the Pedersen Commitment. While PolyCommit_DL provides computational hiding, PolyCommit_Ped goes a step further by offering unconditional hiding as its most prominent feature.

Why Is It Stronger...?

A commitment of the form $C = g^{\phi(\alpha)}$ makes it hard to compute $\phi(\alpha)$ from the pair $(g, C)$ alone (due to the discrete logarithm problem), but theoretically, it is fixed to a unique value $\phi(\alpha)$. The assumption is that an attacker with unlimited computational power could find this value. In contrast, the form $C = g^m \cdot h^r$ uses both a secret value $m$ and a random value $r$. Even given $g, h, C$, there are infinitely many possible $(m, r)$ pairs, so $m$ cannot be pinpointed—even by an attacker with unlimited computational power. This is unconditional hiding.

PolyCommit_Ped can be seen as applying this idea to polynomial commitments.

1. In addition to the original polynomial $\phi(x)$ to commit to, it uses another completely randomly selected polynomial $\psi(x)$.
2. Two different generators $g$ and $h$ are used to weave these two polynomials into a single commitment.

• Unconditional Hiding: It uses the same algebraic properties as PolyCommit_DL but achieves unconditional hiding by leveraging an additional random polynomial $\hat{\phi}(x)$.
• Homomorphic Utilization: Combines commitments to $\phi(x)$ and $\hat{\phi}(x)$ by exploiting the homomorphic properties of PolyCommit_DL.
• Commit: Computed as $C = g^{\phi(\alpha)} h^{\hat{\phi}(\alpha)}$.
  • Uses $PK = \langle G, g, g^\alpha, \dots, g^{\alpha^t}, h, h^\alpha, \dots, h^{\alpha^t} \rangle$.
• CreateWitness: Computes $\psi_i(x)$ and $\hat{\psi}_i(x)$ respectively, and outputs $w_i = g^{\psi_i(\alpha)} h^{\hat{\psi}_i(\alpha)}$ as the witness.
• VerifyEval: Verifies via $e(C, g) \stackrel{?}{=} e(w_i, g^\alpha / g^i) \cdot e(g^{\phi(i)} h^{\hat{\phi}(i)}, g)$.
• Security: Secure under the t-SDH assumption, with unconditional hiding.

Algorithm-Specific Implementation

1. $Setup(1^\kappa, t)$

1. Select bilinear map groups $G, G_T$ as in PolyCommit_DL.
2. In addition to generator $g$, select another generator $h$. The discrete logarithm relationship between $g$ and $h$ must remain unknown to everyone (i.e., if $h = g^x$, no one should know $x$).
3. A trusted authority randomly selects a secret value $\alpha \in \mathbb{Z}_p$.