# Kate Polynomial Commitments

SRC: [[KZG10]](https://doi.org/10.1007/978-3-642-17373-8_11)

Also called “KZG” Polynomial Commitment Scheme, this is a cryptographic commitment scheme for any given polynomial $f(x) \in \mathbb{F}_p^{\leq d}[X]$. The efficiency of this scheme is due to the expressive power granted by pairings, which, based on a prior trusted setup, can extend our partially homomorphic groups into fully homomorphic, up to the given degree $d$.

- **trusted setup(d)** given $gk = (p, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T), \langle g \rangle = \mathbb{G}_1, \langle h \rangle = \mathbb{G}_2$:

$$
\begin{align*}
\alpha &\overset{\$}\gets \mathbb{F} &\textit{ (toxic waste)}\\
ck &= \{g^{\alpha^i}\}_{i\in [d]} &\textit{ (commitment key)}\\
vk &= h^\alpha &\textit{ (verification key)}
\end{align*}
$$

- **commit(f)** given commitment key $ck$:

$$
C_f = g^{f(\alpha)} = \prod g^{f_i \alpha^i} = \prod ({g^{\alpha^i}})^{f_i}
$$

- **open(f, x, y)** given commitment key $ck$**:**

$$
\begin{align*}
q(X) &:= \frac{f(X) - y}{X- x}\\
C_q &= g^{q(\alpha)} = \prod g^{q_i \alpha^i} = \prod (g^{\alpha^i})^{q_i}
\end{align*}
$$

- **check(Cf, Cq, x, y)** given verification key $vk$**:**

$$
\begin{align*}
&& e(C_f \cdot g^{-y}, h) &\overset{?}= e(C_q, vk \cdot h^{-x})\\
&\overset{?}\iff& e(g^{f(\alpha)} \cdot g^{-y}, h) &= e(g^{q(\alpha)}, h^\alpha \cdot h^{-x}) \\
&\overset{?}\iff& e(g, h)^{f(\alpha) - y} &= e(g, h)^{\frac{f(\alpha) - y}{\alpha - x}(\alpha - x)}
\end{align*}
$$

**Soundness Explanation:** The core idea, in short, is to simply check whether $C_q$, or $q(\alpha)$, is “correct” (i.e. somehow consistent with $C_f$ and already previously “represented” by it). Because if it is, then that means that $q(X)$ also very likely exists as a polynomial, which implies that $(x,y) \in f(X)$ must be valid (with overwhelming probability), otherwise there would have been no way to obtain an existing polynomial through division with one of its roots, as $q(X)$ claims to do by removing the pair $(x,y)$ from $f(X)$. We check that $q(X)$ actually must have performed that division by using bilinear mappings to perform a one-time multiplication between $C_q$ and the polynomial’s root $(X-x) = (\alpha - x)$ in the exponent of $h$, and checking that it leads us back to the previously committed $C_f$. The trusted setup, along with other standard bilinear pairing exponent assumptions in such contexts, of course, ensures there is no possible cheating involved other than with negligible probability (i.e. really a lot of luck).

## Perfectly Hiding Variant

relevant for Zero-Knowledge extensions (makes construction of Proofs with ZK property slightly easier), works like Pedersen commitments…

# Extensions: …

- Batched Opening

- nearly-ZK Sets
mario is in SecretSET
hash(mario) is in SecretSET
i have an address = there is an address that is in SecretSET

mario + bob is in Set1
… is in Set1, the other is in Set2

list = [a,b,c…] → secretlist = [commitment of (a,b,c), …]
… AND the key to … is correct

- nearly-ZK Databases (key-value pairs)
- Multi-Polynomial Opening

- Multi-Polynomial Batched Opening
- Updatable nearly-ZK Sets

“can the delegated updater know all of the other owners?”