Hadamard Product Arguments and Their Applications
K.-K. Lee, Hankyung Ko, Donghwan Oh, Jihye Kim, Hyunok Oh · IEEE Access · 2025
The Hadamard product (also known as element-wise multiplication) is a fundamental operation in linear algebra, performed by multiplying corresponding elements of two matrices with the same dimensions. This operation plays a crucial role in various fields, including cryptography, where it enables efficient and parallelizable computations on large datasets—particularly in the design of cryptographic protocols such as zero-knowledge proofs. In this paper, we propose a transparent and efficient method for proving the Hadamard product between vectors that are independently committed in the groups G1and G2under a pairing operation e : G1×G2→ GT . For a vector of length n, the prover has a complexity ofOλ(n), while the proof size isOλ(logn). The verifier operates with a complexity ofOλ(logn), which includesO(logn) operations in GT and onlyO(1) pairing operations, making verification highly efficient. We prove the security of our scheme under the Symmetric External Diffie-Hellman (SXDH) assumption. Furthermore, we propose an aggregator for Groth16 (EUROCRYPT 2016) zk-SNARKs and a proof aggregation technique for the general case of the KZG polynomial commitment scheme (ASIACRYPT 2010), where all crs are distinct. Both applications do not require an additional trusted setup, support logarithmic-sized aggregated proofs, and significantly reduce the verifier’s pairing operations toO(1).