Paper 2024/613
Hadamard Product Argument from Lagrange-Based Univariate Polynomials
, Shanghai Jiao Tong UniversityAbstract
Hadamard product is a point-wise product for two vectors. This paper presents a new scheme to prove Hadamard-product relation as a sub-protocol for SNARKs based on univariate polynomials. Prover uses linear cryptographic operations to generate the proof containing logarithmic field elements. The verification takes logarithmic cryptographic operations with constant numbers of pairings in bilinear group. The construction of the scheme is based on the Lagrange-based KZG commitments (Kate, Zaverucha, and Goldberg at Asiacrypt 2010) and the folding technique. We construct an inner-product protocol from folding technique on univariate polynomials in Lagrange form, and by carefully choosing the random polynomials suitable for folding technique, we construct a Hadamard-product protocol from the inner-product protocol, giving an alternative to prove linear algebra relations in linear time, and the protocol has a better concrete proof size than previous works.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- interactive oracle proofsSNARKsHadamard product
- Contact author(s)
-
xiejie1006 @ sjtu edu cn
huyuncong @ sjtu edu cn
yyuu @ sjtu edu cn - History
- 2024-04-24: revised
- 2024-04-22: received
- See all versions
- Short URL
- https://ia.cr/2024/613
- License
-
CC0
BibTeX
@misc{cryptoeprint:2024/613,
author = {Jie Xie and Yuncong Hu and Yu Yu},
title = {Hadamard Product Argument from Lagrange-Based Univariate Polynomials},
howpublished = {Cryptology ePrint Archive, Paper 2024/613},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/613}},
url = {https://eprint.iacr.org/2024/613}
}
