Bilinear pairing + q-SDH ⇒ PCS

Fully-black-box reduction · CRS model · KZG10 · security loss: tight: one call to the binding adversary yields a $q$-SDH solution

Statement

In a bilinear group with a trusted structured reference string $(g,g^{\tau },\dots ,g^{{\tau }^d})$, the KZG scheme is a polynomial commitment for polynomials of degree at most $d$ whose commitments and opening proofs are single group elements and whose verification is two pairings. It is evaluation binding under q-SDH with $q=d$, and its Pedersen variant is unconditionally hiding — KZG10.

Sketch

\begin{algorithm}
\algname{Algorithm}
\caption{KZG polynomial commitment}
\begin{algorithmic}
\State $\Setup(1^\secpar, d)$: $\tau \getsr \ZZ_p^{*}$; $\mathsf{srs} \gets (g, g^{\tau}, \ldots, g^{\tau^{d}})$; discard $\tau$
\State $\mathsf{Commit}(\mathsf{srs}, f)$ for $f = \sum_{i=0}^{d} f_{i} X^{i}$: $C \gets \prod_{i=0}^{d} (g^{\tau^{i}})^{f_{i}} = g^{f(\tau)}$; $\mathsf{aux} \gets f$
\State $\Open(\mathsf{srs}, C, z, y, \mathsf{aux})$: $\psi(X) \gets (f(X) - y)/(X - z)$; $\pi \gets g^{\psi(\tau)}$
\State $\Vrfy(\mathsf{srs}, C, z, y, \pi) := [\, e(C/g^{y}, g) = e(\pi, g^{\tau}/g^{z}) \,]$
\end{algorithmic}
\end{algorithm}

Two accepting openings $(y,\pi )$, $(y^{\prime },{\pi }^{\prime })$ at one point $z$ with $y\ne y^{\prime }$ give $(\pi /{\pi }^{\prime }{)}^{1/(y^{\prime }-y)}=g^{1/(\tau -z)}$, a $q$-SDH solution with $c=-z$.