Received 1 March 2024 / Revised 1 August 2024 / Accepted 21 August 2024 | Tohru Kohrita - Patrick Towa
This paper introduces a new scheme for committing to multilinear polynomials and proving their evaluations, achieving zero-knowledge properties with significantly reduced prover costs. The scheme is generic and relies on the additive homomorphic property of univariate polynomial commitments and a protocol to verify that committed polynomials satisfy public degree bounds. The construction also includes a method to batch executions of degree-check protocols on homomorphic commitments. For an \( n \)-linear polynomial, the scheme, when instantiated with a hiding version of KZG commitments, requires only \( n + 5 \) extra first-group operations to achieve zero-knowledge, compared to the \( 2^n \) multi-scalar multiplications required by previous constructions. This improvement is achieved without compromising other performance measures compared to state-of-the-art techniques. The paper highlights the practical significance of this reduction in prover costs, especially when dealing with large numbers of evaluations.This paper introduces a new scheme for committing to multilinear polynomials and proving their evaluations, achieving zero-knowledge properties with significantly reduced prover costs. The scheme is generic and relies on the additive homomorphic property of univariate polynomial commitments and a protocol to verify that committed polynomials satisfy public degree bounds. The construction also includes a method to batch executions of degree-check protocols on homomorphic commitments. For an \( n \)-linear polynomial, the scheme, when instantiated with a hiding version of KZG commitments, requires only \( n + 5 \) extra first-group operations to achieve zero-knowledge, compared to the \( 2^n \) multi-scalar multiplications required by previous constructions. This improvement is achieved without compromising other performance measures compared to state-of-the-art techniques. The paper highlights the practical significance of this reduction in prover costs, especially when dealing with large numbers of evaluations.