MERCURY: A multilinear Polynomial Commitment Scheme with constant proof size and no prover FFTs

Liam Eagen; Ariel Gabizon

Paper 2025/385

MERCURY: A multilinear Polynomial Commitment Scheme with constant proof size and no prover FFTs

Liam Eagen, Alpen Labs

Ariel Gabizon, Aztec Labs

Abstract

We construct a pairing-based polynomial commitment scheme for multilinear polynomials of size $n$ where constructing an opening proof requires $O (n)$ field operations, and $2 n + O (\sqrt{n})$ scalar multiplications. Moreover, the opening proof consists of a constant number of field elements. This is a significant improvement over previous works which would require either 1. field operations; or 2. size opening proof. The main technical component is a new method of verifiably folding a witness via univariate polynomial division. As opposed to previous methods, the proof size and prover time remain constant *regardless of the folding factor*.

Note: typo

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: SNARKs Polynomial Commitment Schemes
Contact author(s): liameagen @ protonmail com
ariel @ aztec-labs com
History: 2025-03-13: last of 8 revisions; 2025-02-28: received; See all versions
Short URL: https://ia.cr/2025/385
License: CC0

BibTeX

@misc{cryptoeprint:2025/385,
      author = {Liam Eagen and Ariel Gabizon},
      title = {{MERCURY}: A multilinear Polynomial Commitment Scheme with constant proof size and no prover {FFTs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/385},
      year = {2025},
      url = {https://eprint.iacr.org/2025/385}
}