Paper 2023/917
Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate Commitments
, Aztec LabsAbstract
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
-
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}
}
