DLOG ⇒ PCS

Fully-black-box reduction · random oracle model · BCCGP16

Statement

If DLOG is hard in a prime-order group, a transparent polynomial commitment scheme exists: commit to the coefficient vector of a degree-$d$ polynomial $f$ with a Pedersen vector commitment and prove $f(z)=y$ with the recursive inner-product argument, giving $O(\log d)$-size openings and $O(d)$ verifier time — BCCGP16. The non-interactive scheme ${\mathrm{PC}}_{\mathrm{DL}}$ applies Fiat–Shamir to the public-coin protocol and is secure under DLOG in the ROM — BCMS20.

Sketch

The claim $f(z)=y$ is the inner product $⟨\vec{f},(1,z,\dots ,z^d)⟩=y$. Each round folds both vectors in half with a random challenge; after $\log d$ rounds the prover reveals the last entry of the folded $\vec{f}$, and the verifier, which folds the public vector and the generators itself in $O(d)$ time, checks one commitment equation. The extractor rewinds each round to build a tree of accepting transcripts, and two openings of one commitment to distinct polynomials give a nontrivial discrete-log relation among the public generators.

Notes

• Bulletproofs halve the communication of the inner-product argument — BBB+18.