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 transcript size and verifier time, zkMatrix stands out as the first to achieve prover time and RAM usage for multiplying two 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 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},
      url = {https://eprint.iacr.org/2024/161}
}