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!
|
| _version_ | 1850136621372932096 |
|---|---|
| author | Kyeongtae Lee Hankyung Ko Donghwan Oh Jihye Kim Hyunok Oh |
| author_facet | Kyeongtae Lee Hankyung Ko Donghwan Oh Jihye Kim Hyunok Oh |
| author_sort | Kyeongtae Lee |
| collection | DOAJ |
| description | 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>. |
| format | Article |
| id | doaj-art-2a21b02c6453401ea6ca2290d2da1609 |
| institution | OA Journals |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-2a21b02c6453401ea6ca2290d2da16092025-08-20T02:31:04ZengIEEEIEEE Access2169-35362025-01-0113797367975610.1109/ACCESS.2025.356610410981717Hadamard Product Arguments and Their ApplicationsKyeongtae Lee0Hankyung Ko1https://orcid.org/0000-0001-9430-1768Donghwan Oh2https://orcid.org/0009-0001-2728-9460Jihye Kim3https://orcid.org/0000-0003-2953-7883Hyunok Oh4https://orcid.org/0000-0002-9044-7441Department of Information Systems, Hanyang University, Seoul, South KoreaDepartment of Information Systems, Hanyang University, Seoul, South KoreaDepartment of Information Systems, Hanyang University, Seoul, South KoreaDepartment of Electronics and Information System Engineering, Kookmin University, Seoul, South KoreaDepartment of Information Systems, Hanyang University, Seoul, South KoreaThe 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>.https://ieeexplore.ieee.org/document/10981717/Zero-knowledge proofpairing-based cryptographySNARKprivacy |
| spellingShingle | Kyeongtae Lee Hankyung Ko Donghwan Oh Jihye Kim Hyunok Oh Hadamard Product Arguments and Their Applications IEEE Access Zero-knowledge proof pairing-based cryptography SNARK privacy |
| title | Hadamard Product Arguments and Their Applications |
| title_full | Hadamard Product Arguments and Their Applications |
| title_fullStr | Hadamard Product Arguments and Their Applications |
| title_full_unstemmed | Hadamard Product Arguments and Their Applications |
| title_short | Hadamard Product Arguments and Their Applications |
| title_sort | hadamard product arguments and their applications |
| topic | Zero-knowledge proof pairing-based cryptography SNARK privacy |
| url | https://ieeexplore.ieee.org/document/10981717/ |
| work_keys_str_mv | AT kyeongtaelee hadamardproductargumentsandtheirapplications AT hankyungko hadamardproductargumentsandtheirapplications AT donghwanoh hadamardproductargumentsandtheirapplications AT jihyekim hadamardproductargumentsandtheirapplications AT hyunokoh hadamardproductargumentsandtheirapplications |