CRHF ⇒ PCS

Random oracle model · BBHR18a

Statement

Collision-resistant hash functions yield a transparent polynomial commitment scheme: the commitment to a polynomial of degree $<d$ is the Merkle root of its Reed–Solomon codeword, and low-degreeness and openings are proved with the FRI proximity test of BBHR18b, with $O({\log }^{2}d)$ proof size and verification time; the non-interactive scheme, the BCS16 compilation of this interactive oracle proof, is secure in the random-oracle model — BBHR18a.

Sketch

FRI folds the committed codeword round by round: writing $f_i(x)=g_i(x^2)+x{h}_i(x^2)$, the verifier sends a uniform ${\alpha }_i$ and the prover commits to the codeword of $f_{i+1}(y)=g_i(y)+{\alpha }_i{h}_i(y)$, halving the degree; consistency between rounds is spot-checked at random points through Merkle openings.

Notes

• The polynomial-commitment abstraction of FRI, as a list polynomial commitment, is made explicit and used to build transparent SNARKs — KPV22.