Hadamard Product Arguments and Their Applications
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 eff...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10981717/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 <inline-formula> <tex-math notation="LaTeX">$\mathbb {G}_{1}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\mathbb {G}_{2}$ </tex-math></inline-formula> under a pairing operation <inline-formula> <tex-math notation="LaTeX">$ e: \mathbb {G}_{1} \times \mathbb {G}_{2} \to \mathbb {G}_{T} $ </tex-math></inline-formula>. For a vector of length n, the prover has a complexity of <inline-formula> <tex-math notation="LaTeX">${\mathcal {O}}_{\lambda }(n)$ </tex-math></inline-formula>, while the proof size is <inline-formula> <tex-math notation="LaTeX">${\mathcal {O}}_{\lambda }(\log n)$ </tex-math></inline-formula>. The verifier operates with a complexity of <inline-formula> <tex-math notation="LaTeX">${\mathcal {O}}_{\lambda }(\log n)$ </tex-math></inline-formula>, which includes <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(\log n)$ </tex-math></inline-formula> operations in <inline-formula> <tex-math notation="LaTeX">$\mathbb {G}_{T}$ </tex-math></inline-formula> and only <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(1)$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$\textsf {crs}$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(1)$ </tex-math></inline-formula>. |
|---|---|
| ISSN: | 2169-3536 |