Paper 2023/917

Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments

Tohru Kohrita, Aztec Labs
Patrick Towa, Aztec Labs

A multilinear polynomial is a multivariate polynomial of degree at most one in each variable. This paper introduces a new scheme to commit to multilinear polynomials and to later prove evaluations thereof. The scheme exponentially improves on the added prover costs for evaluation proofs to be zero-knowledge. The construction of the scheme is generic and relies only on the additive homomorphic property of any scheme to commit to univariate polynomials, and on a protocol to prove that committed polynomials satisfy public degree bounds. As the construction requires to check that several committed univariate polynomials do not exceed given, separate bounds, the paper also gives a method to batch executions of any degree-check protocol on homomorphic commitments. For an n-linear polynomial, the instantiation of the scheme with a hiding version of KZG commitments (Kate, Zaverucha and Goldberg at Asiacrypt 2010) leads to a scheme with an evaluation prover that performs only n + 5 extra (i.e., compared to the variant of the same scheme that is not zero-knowledge) first-group operations to achieve the zero-knowledge property. In contrast, previous constructions require an extra 2^n multi-scalar multiplication. The instantiation does so without any concessions on the other performance measures compared to the state of the art.

Note: Revised introduction.

Available format(s)
Cryptographic protocols
Publication info
Multilinear PolynomialsPolynomial CommitmentsZero-Knowledge Proofs
Contact author(s)
tohru kohrita @ gmail com
patrick towa @ gmail com
2024-06-19: last of 4 revisions
2023-06-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tohru Kohrita and Patrick Towa},
      title = {Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2023/917},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.