Paper 2023/1257

Batchman and Robin: Batched and Non-batched Branching for Interactive ZK

Yibin Yang, Georgia Institute of Technology
David Heath, University of Illinois Urbana-Champaign
Carmit Hazay, Bar-Ilan University, Ligero Inc.
Vladimir Kolesnikov, Georgia Institute of Technology
Muthuramakrishnan Venkitasubramaniam, Ligero Inc.
Abstract

Vector Oblivious Linear Evaluation (VOLE) supports fast and scalable interactive Zero-Knowledge (ZK) proofs. Despite recent improvements to VOLE-based ZK, compiling proof statements to a control-flow oblivious form (e.g., a circuit) continues to lead to expensive proofs. One useful setting where this inefficiency stands out is when the statement is a disjunction of clauses L1 ∨ · · · ∨ LB. Typically, ZK requires paying the price to handle all B branches. Prior works have shown how to avoid this price in communication, but not in computation. Our main result, Batchman, is asymptotically and concretely efficient VOLE-based ZK for batched disjunctions, i.e. statements containing R repetitions of the same disjunction. This is crucial for, e.g., emulating CPU steps in ZK. Our prover and verifier complexity is only O(RB + R|C| + B|C|), where |C| is the maximum circuit size of the B branches. Prior works’ computation scales in RB|C|. For non-batched disjunctions, we also construct a VOLE-based ZK protocol, Robin, which is (only) communication efficient. For small fields and for statistical security parameter λ, this protocol’s communication improves over the previous state of the art (Mac′n′Cheese, Baum et al., CRYPTO’21) by up to factor λ. Our implementation outperforms prior state of the art. E.g., we achieve up to $6×$ improvement over Mac′n′Cheese (Boolean, single disjunction), and for arithmetic batched disjunctions our experiments show we improve over QuickSilver (Yang et al., CCS’21) by up to $70×$ and over AntMan (Weng et al., CCS’22) by up to $36×$.

Note: 9/26/2024: Correct minor formatting errors. 2/4/2024: Add the GitHub link for our implementation. Add a straightforward optimization for Batchman protocol to improve communication based on recent advanced ZK ROM.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. CCS 2023
DOI
10.1145/3576915.3623169
Keywords
Zero KnowledgeVOLE-based ZKZK for Disjunctions
Contact author(s)
yyang811 @ gatech edu
daheath @ illinois edu
Carmit Hazay @ biu ac il
kolesnikov @ gatech edu
muthu @ ligero-inc com
History
2024-09-26: last of 2 revisions
2023-08-20: received
See all versions
Short URL
https://ia.cr/2023/1257
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1257,
      author = {Yibin Yang and David Heath and Carmit Hazay and Vladimir Kolesnikov and Muthuramakrishnan Venkitasubramaniam},
      title = {Batchman and Robin: Batched and Non-batched Branching for Interactive {ZK}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1257},
      year = {2023},
      doi = {10.1145/3576915.3623169},
      url = {https://eprint.iacr.org/2023/1257}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.