Hadamard Product Arguments and Their Applications - Kyeongtae Lee; Hankyung Ko; Donghwan Oh; Jihye Kim; Hyunok Oh (IEEE Access)
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 $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$ under a pairing operation $ e: \mathbb {G}_{1} × \mathbb {G}_{2} → \mathbb {G}_{T} $ . For a vector of length n, the prover has a complexity of ${\mathcal {O}}_{λ }(n)$ , while the proof size is ${\mathcal {O}}_{λ }(\log n)$ . The verifier operates with a complexity of ${\mathcal {O}}_{λ }(\log n)$ , which includes $\mathcal {O}(\log n)$ operations in $\mathbb {G}_{T}$ and only $\mathcal {O}(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 to $\mathcal {O}(1)$ .