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 that is linear in each variable. This paper presents a scheme to commit to multilinear polynomials and to later prove evaluations of committed polynomials. The construction of the scheme is generic and relies on additively homomorphic schemes to commit to univariate polynomials. 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 a multilinear polynomial in n ≥ 2 variables, the instantiation of the scheme with a hiding version of KZG commitments (Kate, Zaverucha and Goldberg at Asiacrypt 2010) gives a pairing-based scheme with evaluations proofs in which the prover sends n + 3 first-group elements, performs at most 5 · 2n−1 + 1 first-group scalar multiplication and uses only n+2 random field elements to achieve the zero-knowledge property. Verification requires at most 2n + 2 first-group scalar multiplications, two second-group scalar multiplications and three pairing computations.

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-06-15: revised
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.