ZEROMORPH: ZERO-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments

ZEROMORPH: ZERO-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments

8 October 2024 | Tohru Kohrita · Patrick Towa
This paper introduces ZEROMORPH, a new scheme for committing to multilinear polynomials and proving their evaluations in a zero-knowledge manner. The scheme significantly reduces the prover cost for zero-knowledge evaluation proofs. It is based on the additive homomorphic property of polynomial commitment schemes and a protocol to verify that committed polynomials satisfy public degree bounds. The scheme allows for batch processing of degree-check protocols on homomorphic commitments, improving efficiency. When instantiated with a hiding version of KZG commitments, the scheme requires only $ n + 5 $ extra first-group operations to achieve zero-knowledge, compared to $ 2^n $ multi-scalar multiplications in previous constructions. This makes it more efficient without compromising other performance measures. The paper also discusses the sum-check protocol, which is central to many efficient proof systems for arithmetic circuit satisfiability. It shows that proving circuit satisfiability can be reduced to proving evaluations of input polynomials at random points. However, evaluating large polynomials can be expensive, so the paper proposes using polynomial commitment schemes to allow the prover to commit to the polynomial before the sum-check protocol. This enables the prover to compute and verify evaluations later, reducing the verifier's computational burden. If the commitment is hiding and the evaluation does not reveal information about the polynomial's values, the proof becomes zero-knowledge. The paper also discusses the practical cost of achieving zero-knowledge, noting that while it increases the number of group operations, it is often manageable due to the smaller size of witness data compared to the field size. Overall, ZEROMORPH provides an efficient and practical approach to zero-knowledge proofs for multilinear polynomials.This paper introduces ZEROMORPH, a new scheme for committing to multilinear polynomials and proving their evaluations in a zero-knowledge manner. The scheme significantly reduces the prover cost for zero-knowledge evaluation proofs. It is based on the additive homomorphic property of polynomial commitment schemes and a protocol to verify that committed polynomials satisfy public degree bounds. The scheme allows for batch processing of degree-check protocols on homomorphic commitments, improving efficiency. When instantiated with a hiding version of KZG commitments, the scheme requires only $ n + 5 $ extra first-group operations to achieve zero-knowledge, compared to $ 2^n $ multi-scalar multiplications in previous constructions. This makes it more efficient without compromising other performance measures. The paper also discusses the sum-check protocol, which is central to many efficient proof systems for arithmetic circuit satisfiability. It shows that proving circuit satisfiability can be reduced to proving evaluations of input polynomials at random points. However, evaluating large polynomials can be expensive, so the paper proposes using polynomial commitment schemes to allow the prover to commit to the polynomial before the sum-check protocol. This enables the prover to compute and verify evaluations later, reducing the verifier's computational burden. If the commitment is hiding and the evaluation does not reveal information about the polynomial's values, the proof becomes zero-knowledge. The paper also discusses the practical cost of achieving zero-knowledge, noting that while it increases the number of group operations, it is often manageable due to the smaller size of witness data compared to the field size. Overall, ZEROMORPH provides an efficient and practical approach to zero-knowledge proofs for multilinear polynomials.
Reach us at info@study.space
[slides and audio] Zeromorph%3A Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments