Post-Quantum Multilinear Polynomial Commitments from FRI Folding in the Boolean-Kernel Basis

This is the authors' abstract. We don't add key points for this paper.

Hash-based multilinear polynomial commitment schemes in the BaseFold paradigm are candidates for post-quantum security, but over smooth multiplicative domains their FRI folding acts on monomial coefficients, so a prover holding a table of values must first convert it to coefficient form. We introduce the Boolean-kernel basis of the univariate polynomials of degree less than 2^n, whose change of basis to monomials is a Kronecker power of a 2 × 2 matrix computable with (n/2)·2^n additions. In this basis a normalised FRI fold is exactly the restriction of one variable of the multilinear extension of the coordinate table, so folding the encoding of a table evaluates its multilinear extension directly. On this fold dictionary we build a transparent, hash-based multilinear polynomial commitment scheme and prove it sound, evaluation binding and round-by-round knowledge sound, using only the correlated-agreement theorem for Reed–Solomon codes; with the compiler of Chiesa, Di, Hu and Zheng, the non-interactive scheme is knowledge sound against quantum adversaries. The core results are machine-checked in Lean 4. A Rust implementation proves an evaluation of a 20-variable polynomial at 100 bits of security in 0.84 s with a 237 KiB proof, about three times faster than the WHIR implementation on the same machine. Code, Lean 4 proofs and benchmark data: https://github.com/qoosmo/kbfold (release v0.3.0).Rust crate: https://crates.io/crates/kbfold