Paper 2023/917

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

Tohru Kohrita, Aztec Labs
Patrick Towa, Aztec Labs
Abstract

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 a criterion of crucial relevance in practice but that is often overlooked in theoretical performance evaluations: the costs of generating prover randomness in zero-knowledge evaluation proofs. 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 uses only n + 2 random field elements to compute zero-knowledge proofs. In contrast, previous constructions require 2n random field elements, which is too costly to prove the satisfiability of arithmetic circuits used in practice. The instantiation does so without any concessions on the other performance measures compared to the state of the art.

Note: Revised abstract and introduction. Explicit, fast computation of quotient polynomials added to the appendix.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Multilinear PolynomialsPolynomial CommitmentsZero-Knowledge Proofs
Contact author(s)
tohru kohrita @ gmail com
patrick towa @ gmail com
History
2023-10-09: last of 2 revisions
2023-06-12: received
See all versions
Short URL
https://ia.cr/2023/917
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/917,
      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{https://eprint.iacr.org/2023/917}},
      url = {https://eprint.iacr.org/2023/917}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.