[Resource Topic] 2024/827: Multivariate Multi-Polynomial Commitment and its Applications

Welcome to the resource topic for 2024/827

Multivariate Multi-Polynomial Commitment and its Applications

Authors: Xiao Yang, Chengru Zhang, Mark Ryan, Gao Meng


We introduce and formally define Multivariate Multi-Polynomial (MMP) commitment, a commitment scheme on multiple multivariate polynomials, and illustrate the concept with an efficient construction, which enjoys constant commitment size and logarithmic proof size. We further enhance our MMP scheme to achieve the zero-knowledge property.

Additionally, combined with a novel zero-knowledge range proof for Pedersen subvector commitment, we present a Zero-Knowledge Range Proof (ZKRP) for MMP commitment.

We present two sample applications. Firstly, our MMP commitment can be used for efficient aggregation of SNARK based on multivariate polynomial commitments. As a showcase, we apply MMP commitment to HyperPlonk and refer to this variant of HyperPlonk as aHyperPlonk. For k instances, each with circuit size n, the communication and verification complexity is reduced from O(k \cdot \log n) to O(\log k + \log n), while the prover complexity remains the same. Secondly, we propose a novel zero-knowledge proof for vehicle GPS traces based on ZKRP for MMP, which allows vehicle owners to prove if a vehicle has/hasn’t passed through some location during a specific time interval.

ePrint: https://eprint.iacr.org/2024/827

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .