Paper 2021/1530

Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets

Alex Ozdemir and Dan Boneh

Abstract

A zk-SNARK is a powerful cryptographic primitive that provides a succinct and efficiently checkable argument that the prover has a witness to a public NP statement, without revealing the witness. However, in their native form, zk-SNARKs only apply to a secret witness held by a single party. In practice, a collection of parties often need to prove a statement where the secret witness is distributed or shared among them. We implement and experiment with *collaborative zk-SNARKs*: proofs over the secrets of multiple, mutually distrusting parties. We construct these by lifting conventional zk-SNARKs into secure protocols among $N$ provers to jointly produce a single proof over the distributed witness. We optimize the proof generation algorithm in pairing-based zk-SNARKs so that algebraic techniques for multiparty computation (MPC) yield efficient proof generation protocols. For some zk-SNARKs, optimization is more challenging. This suggests MPC "friendliness" as an additional criterion for evaluating zk-SNARKs. We implement three collaborative proofs and evaluate the concrete cost of proof generation. We find that over a 3Gb/s link, security against a malicious minority of provers can be achieved with *approximately the same runtime* as a single prover. Security against $N-1$ malicious provers requires only a $2\times$ slowdown. This efficiency is unusual since most computations slow down by orders of magnitude when securely distributed. This efficiency means that most applications that can tolerate the cost of a single-prover proof should also be able to tolerate the cost of a collaborative proof.

Note: Revised in alignment with camera-ready version. Updated with artifact evaluation.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
zero knowledgemulti-party computationimplementation
Contact author(s)
aozdemir @ cs stanford edu
dabo @ cs stanford edu
History
2022-04-08: last of 6 revisions
2021-11-22: received
See all versions
Short URL
https://ia.cr/2021/1530
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1530,
      author = {Alex Ozdemir and Dan Boneh},
      title = {Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1530},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1530}},
      url = {https://eprint.iacr.org/2021/1530}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.