Paper 2026/1561

LiftWHIR: A Prover-Efficient Polynomial Commitment with Short Proofs

Abstract

Polynomial commitment schemes allow a prover to commit to a large polynomial and later prove a claimed evaluation at a chosen point. They are a core component of many efficient SNARKs, and the cost of their evaluation phase directly affects SNARK prover time. Reed--Solomon-based schemes already offer small proofs and fast verification, but generating an evaluation proof for a large polynomial remains expensive. We present LiftWHIR, a Reed--Solomon-based polynomial commitment scheme that reduces prover time in the evaluation phase. LiftWHIR combines interleaved coding with the DEEP(ITCS'20) technique to reduce proving an evaluation of a large polynomial to two smaller tasks: a proximity test on a shorter codeword and evaluation of a smaller polynomial. The use of DEEP simultaneously reduces the number of queries required by the proximity test. We then use WHIR(EUROCRYPT'25) to prove both resulting tasks, keeping verification and communication costs low. LiftWHIR trades a modest increase in proof size and verifier time for a substantial reduction in prover time. At $n=2^{20}$ over a 255-bit prime field and code rate $1/2$ (resp., $1/4$), LiftWHIR reduces the evaluation phase to 167 ms (resp., 169 ms), yielding a $4.4\times$ (resp., $6.7\times$) speedup over WHIR. Including commitment, LiftWHIR achieves total prover times of 808 ms (resp., 1,474 ms), corresponding to overall prover speedups of $1.61\times$ (resp., $1.55\times$). Verification time increases from 0.55 ms to 0.76 ms (resp., 0.40 ms to 0.51 ms), while proof size is $1.46\times$ (resp., $1.33\times$) that of WHIR. We further instantiate Spartan(CRYPTO'20) with LiftWHIR and compare it with a Spartan variant instantiated with WHIR. LiftWHIR speeds up proving by $1.9\times$, while verification time increases only from 3.86ms to 4.62ms, at the cost of a $42\%$ increase in proof size.