zkMatrix: Batched Short Proof for Committed Matrix Multiplication

Mingshu Cong; Tsz Hon Yuen; Siu Ming Yiu

Paper 2024/161

zkMatrix: Batched Short Proof for Committed Matrix Multiplication

Mingshu Cong

, University of Hong Kong

Tsz Hon Yuen

, Monash University

Siu Ming Yiu

, University of Hong Kong

Abstract

Matrix multiplication is a common operation in applications like machine learning and data analytics. To demonstrate the correctness of such an operation in a privacy-preserving manner, we propose zkMatrix, a zero-knowledge proof for the multiplication of committed matrices. Among the succinct non-interactive zero-knowledge protocols that have an $O(\log n)$ transcript size and $O(\log n)$ verifier time, zkMatrix stands out as the first to achieve $O(n^2)$ prover time and $O(n^2)$ RAM usage for multiplying two $n \times n$ matrices. Significantly, zkMatrix distinguishes itself as the first zk-SNARK protocol specifically designed for matrix multiplication. By batching multiple proofs together, each additional matrix multiplication only necessitates $O(n)$ group operations in prover time.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. AsiaCCS 2024
Keywords: zero-knowledge proof matrix multiplication zk-SNARK
Contact author(s): mscong @ cs hku hk
john tszhonyuen @ monash edu
smyiu @ cs hku hk
History: 2024-02-07: last of 2 revisions; 2024-02-04: received; See all versions
Short URL: https://ia.cr/2024/161
License: CC BY

BibTeX

@misc{cryptoeprint:2024/161,
      author = {Mingshu Cong and Tsz Hon Yuen and Siu Ming Yiu},
      title = {zkMatrix: Batched Short Proof for Committed Matrix Multiplication},
      howpublished = {Cryptology ePrint Archive, Paper 2024/161},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/161}},
      url = {https://eprint.iacr.org/2024/161}
}