zkMatrix: Batched Short Proof for Committed Matrix Multiplication

Mingshu Cong; Tsz Hon Yuen; Siu Ming Yiu

doi:10.1145/3634737.3645003

zkMatrix: Batched Short Proof for Committed Matrix Multiplication

Mingshu Cong
, Tsz Hon Yuen
, Siu Ming Yiu

Department of Software Systems & Cybersecurity

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

3 Citations (Scopus)

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²) prover time and O(n²) RAM usage for multiplying two n × 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.

Original language	English
Title of host publication	Proceedings of the 19th ACM Asia Conference on Computer and Communications Security
Editors	Debin Gao, Alvaro Cardenas
Place of Publication	New York NY USA
Publisher	Association for Computing Machinery (ACM)
Pages	289-305
Number of pages	17
ISBN (Electronic)	9798400704826
DOIs	https://doi.org/10.1145/3634737.3645003
Publication status	Published - 2024
Event	ACM Symposium on Information, Computer and Communication Security (ASIACCS) 2024 - Singapore, Singapore Duration: 1 Jul 2024 → 5 Jul 2024 Conference number: 19th https://dl.acm.org/doi/proceedings/10.1145/3634737 (Proceedings) https://asiaccs2024.sutd.edu.sg/ (Website)

Conference

Conference	ACM Symposium on Information, Computer and Communication Security (ASIACCS) 2024
Abbreviated title	AsiaCCS 2024
Country/Territory	Singapore
City	Singapore
Period	1/07/24 → 5/07/24
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3634737 (Proceedings) https://asiaccs2024.sutd.edu.sg/ (Website)

Keywords

matrix multiplication
zero-knowledge proof
zk-SNARK

Access to Document

10.1145/3634737.3645003

Cite this

@inproceedings{3c4dd347d1324067963a294d52dedad6,

title = "zkMatrix: Batched Short Proof for Committed Matrix Multiplication",

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(n2) prover time and O(n2) RAM usage for multiplying two n × 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.",

keywords = "matrix multiplication, zero-knowledge proof, zk-SNARK",

author = "Mingshu Cong and Yuen, \{Tsz Hon\} and Yiu, \{Siu Ming\}",

note = "Publisher Copyright: {\textcopyright} 2024 Copyright held by the owner/author(s).; ACM Symposium on Information, Computer and Communication Security (ASIACCS) 2024, AsiaCCS 2024 ; Conference date: 01-07-2024 Through 05-07-2024",

year = "2024",

doi = "10.1145/3634737.3645003",

language = "English",

pages = "289--305",

editor = "Debin Gao and Alvaro Cardenas",

booktitle = "Proceedings of the 19th ACM Asia Conference on Computer and Communications Security",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

url = "https://dl.acm.org/doi/proceedings/10.1145/3634737, https://asiaccs2024.sutd.edu.sg/",

}

Cong, M, Yuen, TH & Yiu, SM 2024, zkMatrix: Batched Short Proof for Committed Matrix Multiplication. in D Gao & A Cardenas (eds), Proceedings of the 19th ACM Asia Conference on Computer and Communications Security. Association for Computing Machinery (ACM), New York NY USA, pp. 289-305, ACM Symposium on Information, Computer and Communication Security (ASIACCS) 2024, Singapore, Singapore, 1/07/24. https://doi.org/10.1145/3634737.3645003

zkMatrix: Batched Short Proof for Committed Matrix Multiplication. / Cong, Mingshu; Yuen, Tsz Hon; Yiu, Siu Ming.
Proceedings of the 19th ACM Asia Conference on Computer and Communications Security. ed. / Debin Gao; Alvaro Cardenas. New York NY USA: Association for Computing Machinery (ACM), 2024. p. 289-305.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - zkMatrix

T2 - ACM Symposium on Information, Computer and Communication Security (ASIACCS) 2024

AU - Cong, Mingshu

AU - Yuen, Tsz Hon

AU - Yiu, Siu Ming

N1 - Conference code: 19th

PY - 2024

Y1 - 2024

N2 - 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(n2) prover time and O(n2) RAM usage for multiplying two n × 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.

AB - 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(n2) prover time and O(n2) RAM usage for multiplying two n × 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.

KW - matrix multiplication

KW - zero-knowledge proof

KW - zk-SNARK

UR - https://www.scopus.com/pages/publications/85199279653

U2 - 10.1145/3634737.3645003

DO - 10.1145/3634737.3645003

M3 - Conference Paper

AN - SCOPUS:85199279653

SP - 289

EP - 305

BT - Proceedings of the 19th ACM Asia Conference on Computer and Communications Security

A2 - Gao, Debin

A2 - Cardenas, Alvaro

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

Y2 - 1 July 2024 through 5 July 2024

ER -

zkMatrix: Batched Short Proof for Committed Matrix Multiplication

Abstract

Conference

Keywords

Access to Document

Other files and links

Cite this