Paper 2024/613

Hadamard Product Argument from Lagrange-Based Univariate Polynomials

Jie Xie, Shanghai Jiao Tong University
Yuncong Hu, Shanghai Jiao Tong University
Yu Yu, Shanghai Jiao Tong University

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.

Available format(s)
Cryptographic protocols
Publication info
interactive oracle proofsSNARKsHadamard product
Contact author(s)
xiejie1006 @ sjtu edu cn
huyuncong @ sjtu edu cn
yyuu @ sjtu edu cn
2024-04-24: revised
2024-04-22: received
See all versions
Short URL
No rights reserved


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.